www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Array, AA Implementations

reply dsimcha <dsimcha yahoo.com> writes:
Since there has been a lot of discussion here lately about how AAs and
ArrayBuilders should be implemented, we should set up a website where people
can contribute different candidate implementations and comment on them.  It's
much easier to know whether something is a good idea when you have a working
implementation of it than when you're discussing it in the abstract.  Also,
the act of actually implementing something forces you to think of details that
get missed when talking about it in the abstract.

Especially for AAs, I think the best thing to do would be for everyone who has
a good idea to post their code in some central place for comment.  If
containers are to be added to Phobos, we could even post AA types that are
meant to handle some special case and aren't intended to be general
implementations.

I already have three AA implementations that I've been prototyping and would
like to have reviewed, and I'm sure others have more:

1.  An open-addressed linear chaining AA that's designed for pure speed in the
common cases.  Somewhat similar to the current implementation but sacrifices
worst-case performance to allow lazy range-based iteration with no additional
allocations and more space efficiency and speed in the common cases.
2.  An implementation that uses linear congruential randomized probing,
designed with conservative GC and space efficiency in mind.
3.  An implementation I call StaticAA, which does not allow the addition or
removal of keys after it is constructed, but in exchange has almost zero space
overhead and is very GC-efficient.  It works by maintaining sorted parallel
arrays and using binary search.
Oct 19 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:

 Since there has been a lot of discussion here lately about how AAs and
 ArrayBuilders should be implemented, we should set up a website where people
 can contribute different candidate implementations and comment on them.  It's
 much easier to know whether something is a good idea when you have a working
 implementation of it than when you're discussing it in the abstract.  Also,
 the act of actually implementing something forces you to think of details that
 get missed when talking about it in the abstract.
 
 Especially for AAs, I think the best thing to do would be for everyone who has
 a good idea to post their code in some central place for comment.  If
 containers are to be added to Phobos, we could even post AA types that are
 meant to handle some special case and aren't intended to be general
 implementations.
 
 I already have three AA implementations that I've been prototyping and would
 like to have reviewed, and I'm sure others have more:
 
 1.  An open-addressed linear chaining AA that's designed for pure speed in the
 common cases.  Somewhat similar to the current implementation but sacrifices
 worst-case performance to allow lazy range-based iteration with no additional
 allocations and more space efficiency and speed in the common cases.
 2.  An implementation that uses linear congruential randomized probing,
 designed with conservative GC and space efficiency in mind.
 3.  An implementation I call StaticAA, which does not allow the addition or
 removal of keys after it is constructed, but in exchange has almost zero space
 overhead and is very GC-efficient.  It works by maintaining sorted parallel
 arrays and using binary search.


That's a great idea. I suggest you to find some comprehensive benchmarks 
against which the performance of AAs can be evaluated.


Andrei
Oct 19 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article

 dsimcha wrote:

 Since there has been a lot of discussion here lately about how AAs and
 ArrayBuilders should be implemented, we should set up a website where people
 can contribute different candidate implementations and comment on them.  It's
 much easier to know whether something is a good idea when you have a working
 implementation of it than when you're discussing it in the abstract.  Also,
 the act of actually implementing something forces you to think of details that
 get missed when talking about it in the abstract.

 Especially for AAs, I think the best thing to do would be for everyone who has
 a good idea to post their code in some central place for comment.  If
 containers are to be added to Phobos, we could even post AA types that are
 meant to handle some special case and aren't intended to be general
 implementations.

 I already have three AA implementations that I've been prototyping and would
 like to have reviewed, and I'm sure others have more:

 1.  An open-addressed linear chaining AA that's designed for pure speed in the
 common cases.  Somewhat similar to the current implementation but sacrifices
 worst-case performance to allow lazy range-based iteration with no additional
 allocations and more space efficiency and speed in the common cases.
 2.  An implementation that uses linear congruential randomized probing,
 designed with conservative GC and space efficiency in mind.
 3.  An implementation I call StaticAA, which does not allow the addition or
 removal of keys after it is constructed, but in exchange has almost zero space
 overhead and is very GC-efficient.  It works by maintaining sorted parallel
 arrays and using binary search.


 That's a great idea. I suggest you to find some comprehensive benchmarks
 against which the performance of AAs can be evaluated.
 Andrei


I'll work on it.  I don't know much about how/where to host a such a website (my
web programming skills are lacking), so I'll ask for volunteers to set this up.
As far as the benchmark, so far the obvious ones seem to be speed and space
efficiency under the following combinations of attributes:

key size/hashing cost:  small vs. large

size of AA:  Small (<100 elements), medium (100-10,000),
large(10,000-1,000,000),
enormous(1,000,000+)

hashing performance:  well-behaved/near uniform vs. poorly behaved/worst-case

usage:  insert/remove-heavy vs. read-heavy

If anyone can think of any more, please let me know.  Also, just thought of this
now:  I wonder if it would make sense to use some polymorphism tricks (AA
operations are slow enough that an extra pointer dereference or virtual function
call isn't going to make or break their performance) to allow implementations to
be automatically and dynamically changed depending on some of the attributes
listed above.

For example, maybe binary trees are fastest for small N.  (Hypothetical, haven't
tested it.)  Obviously for sufficiently large N hash tables will be fastest.  We
could create an abstract AA type that automatically switches from binary trees
to
hash tables when it makes sense, make this the default builtin AA, and expose
both
of the underlying implementations in std.containers for when the user wants more
control over the details rather than DWIM.
Oct 19 2009
parent reply Jerry Quinn <jlquinn optonline.net> writes:
dsimcha Wrote:


 If anyone can think of any more, please let me know.  Also, just thought of
this
 now:  I wonder if it would make sense to use some polymorphism tricks (AA
 operations are slow enough that an extra pointer dereference or virtual
function
 call isn't going to make or break their performance) to allow implementations
to
 be automatically and dynamically changed depending on some of the attributes
 listed above.


This is not necessarily true.  If you are hammering a map of int to int,
function call overhead will matter a great deal and you would like the compiler
to be able to inline it.  Size will also matter for huge AA tables.

On the other hand, perhaps you're willing to say that built-in AA's will not be
suitable for every case.


 For example, maybe binary trees are fastest for small N.  (Hypothetical,
haven't
 tested it.)  Obviously for sufficiently large N hash tables will be fastest. 
We
 could create an abstract AA type that automatically switches from binary trees
to
 hash tables when it makes sense, make this the default builtin AA, and expose
both
 of the underlying implementations in std.containers for when the user wants
more
 control over the details rather than DWIM.



One thing I think is important is to codify the interface to the AA
implementation, so that files built with different compilers could be linked
together.

I'd also like to see a way  to allow the user to implement a custom AA for some
uses and still be able take advantage of the nice syntactic sugar the language
provides.
Oct 19 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Jerry Quinn (jlquinn optonline.net)'s article

 dsimcha Wrote:

 If anyone can think of any more, please let me know.  Also, just thought of
this
 now:  I wonder if it would make sense to use some polymorphism tricks (AA
 operations are slow enough that an extra pointer dereference or virtual
function
 call isn't going to make or break their performance) to allow implementations
to
 be automatically and dynamically changed depending on some of the attributes
 listed above.


 This is not necessarily true.  If you are hammering a map of int to int,


function call overhead will matter a great deal and you would like the compiler
to
be able to inline it.  Size will also matter for huge AA tables.

 On the other hand, perhaps you're willing to say that built-in AA's will not be


suitable for every case.

Yes.  The builtin should handle the most common 90-95% of cases, "special" AA
types in Phobos can handle another few percent, and for the last 1-2%, your
problem is so specialized that you understand it way better than the
language/std.
lib designer that you should probably just roll your own or use some
hyper-specialized 3rd party lib.


 For example, maybe binary trees are fastest for small N.  (Hypothetical,
haven't
 tested it.)  Obviously for sufficiently large N hash tables will be fastest. 
We
 could create an abstract AA type that automatically switches from binary trees
to
 hash tables when it makes sense, make this the default builtin AA, and expose
both
 of the underlying implementations in std.containers for when the user wants
more
 control over the details rather than DWIM.


 One thing I think is important is to codify the interface to the AA


implementation, so that files built with different compilers could be linked
together..

I was thinking define an interface (a runtime, OO interface, the kind you can
inherit from), and then define a bunch of final classes that implement that
interface.  This way, you can have either polymorphism (use the interface) or
speed (instantiate one of the final classes directly).
Oct 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
On 19/10/2009 21:20, dsimcha wrote:

 == Quote from Jerry Quinn (jlquinn optonline.net)'s article

 dsimcha Wrote:

 If anyone can think of any more, please let me know.  Also, just thought of
this
 now:  I wonder if it would make sense to use some polymorphism tricks (AA
 operations are slow enough that an extra pointer dereference or virtual
function
 call isn't going to make or break their performance) to allow implementations
to
 be automatically and dynamically changed depending on some of the attributes
 listed above.


 This is not necessarily true.  If you are hammering a map of int to int,


 function call overhead will matter a great deal and you would like the
compiler to
 be able to inline it.  Size will also matter for huge AA tables.

 On the other hand, perhaps you're willing to say that built-in AA's will not be


 suitable for every case.

 Yes.  The builtin should handle the most common 90-95% of cases, "special" AA
 types in Phobos can handle another few percent, and for the last 1-2%, your
 problem is so specialized that you understand it way better than the
language/std.
 lib designer that you should probably just roll your own or use some
 hyper-specialized 3rd party lib.


 For example, maybe binary trees are fastest for small N.  (Hypothetical,
haven't
 tested it.)  Obviously for sufficiently large N hash tables will be fastest. 
We
 could create an abstract AA type that automatically switches from binary trees
to
 hash tables when it makes sense, make this the default builtin AA, and expose
both
 of the underlying implementations in std.containers for when the user wants
more
 control over the details rather than DWIM.


 One thing I think is important is to codify the interface to the AA


 implementation, so that files built with different compilers could be linked
 together..

 I was thinking define an interface (a runtime, OO interface, the kind you can
 inherit from), and then define a bunch of final classes that implement that
 interface.  This way, you can have either polymorphism (use the interface) or
 speed (instantiate one of the final classes directly).


this is a good idea, but shouldn't such an API be designed as part of a 
collections API for phobos?

here's an example of a well designed, consistent API:
http://www.gobosoft.com/eiffel/gobo/structure/index.html
Oct 19 2009
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Yigal Chripun (yigal100 gmail.com)'s article

 On 19/10/2009 21:20, dsimcha wrote:

 == Quote from Jerry Quinn (jlquinn optonline.net)'s article

 dsimcha Wrote:

 If anyone can think of any more, please let me know.  Also, just thought of
this
 now:  I wonder if it would make sense to use some polymorphism tricks (AA
 operations are slow enough that an extra pointer dereference or virtual
function
 call isn't going to make or break their performance) to allow implementations
to
 be automatically and dynamically changed depending on some of the attributes
 listed above.


 This is not necessarily true.  If you are hammering a map of int to int,


 function call overhead will matter a great deal and you would like the
compiler to
 be able to inline it.  Size will also matter for huge AA tables.

 On the other hand, perhaps you're willing to say that built-in AA's will not be


 suitable for every case.

 Yes.  The builtin should handle the most common 90-95% of cases, "special" AA
 types in Phobos can handle another few percent, and for the last 1-2%, your
 problem is so specialized that you understand it way better than the
language/std.
 lib designer that you should probably just roll your own or use some
 hyper-specialized 3rd party lib.


 For example, maybe binary trees are fastest for small N.  (Hypothetical,
haven't
 tested it.)  Obviously for sufficiently large N hash tables will be fastest. 
We
 could create an abstract AA type that automatically switches from binary








trees to

 hash tables when it makes sense, make this the default builtin AA, and








expose both

 of the underlying implementations in std.containers for when the user wants
more
 control over the details rather than DWIM.


 One thing I think is important is to codify the interface to the AA


 implementation, so that files built with different compilers could be linked
 together..

 I was thinking define an interface (a runtime, OO interface, the kind you can
 inherit from), and then define a bunch of final classes that implement that
 interface.  This way, you can have either polymorphism (use the interface) or
 speed (instantiate one of the final classes directly).


 this is a good idea, but shouldn't such an API be designed as part of a
 collections API for phobos?
 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html


Well, we've got ranges for iteration.  Other than that, AAs don't have much in
common with any other collection, so I don't see much need to standardize and
do a
big design up front.
Oct 19 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:

 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html


This is a solid framework, unlike Java's containers which are a joke. I 
disagree with some of Gobo's abstractions (e.g. I believe all containers 
must be traversable and that primitives such as count() have no place in 
a general container) but generally the framework seems to be very well 
put together. It's a great source of inspiration for Phobos. Thanks very 
much for the link.

Andrei
Oct 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
On 19/10/2009 23:42, Andrei Alexandrescu wrote:

 Yigal Chripun wrote:

 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html


 This is a solid framework, unlike Java's containers which are a joke. I
 disagree with some of Gobo's abstractions (e.g. I believe all containers
 must be traversable and that primitives such as count() have no place in
 a general container) but generally the framework seems to be very well
 put together. It's a great source of inspiration for Phobos. Thanks very
 much for the link.

 Andrei


My understanding of this design is that they identified all the 
orthogonal properties relevant to containers and that specific 
containers are a composition of a specific set of such properties.
Eiffel has MI (different from the c++ implementation) which is helpful 
if you already have suitable default implementations for these properties.

regarding "traversable" property:
what if I want a container for a non-ordered type? an example would be a 
container of complex numbers, how would you traverse it?

what about hash tables?
Oct 21 2009
next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 22 Oct 2009 01:35:49 +0400, Yigal Chripun <yigal100 gmail.com>  
wrote:


 On 19/10/2009 23:42, Andrei Alexandrescu wrote:

 Yigal Chripun wrote:

 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html


 This is a solid framework, unlike Java's containers which are a joke. I
 disagree with some of Gobo's abstractions (e.g. I believe all containers
 must be traversable and that primitives such as count() have no place in
 a general container) but generally the framework seems to be very well
 put together. It's a great source of inspiration for Phobos. Thanks very
 much for the link.

 Andrei


 My understanding of this design is that they identified all the  
 orthogonal properties relevant to containers and that specific  
 containers are a composition of a specific set of such properties.
 Eiffel has MI (different from the c++ implementation) which is helpful  
 if you already have suitable default implementations for these  
 properties.

 regarding "traversable" property:
 what if I want a container for a non-ordered type? an example would be a  
 container of complex numbers, how would you traverse it?

 what about hash tables?


What's wrong with iterating over a hash table? An order is just unreliable  
(but still deterministic).
Oct 21 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:

 On 19/10/2009 23:42, Andrei Alexandrescu wrote:

 Yigal Chripun wrote:

 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html


 This is a solid framework, unlike Java's containers which are a joke. I
 disagree with some of Gobo's abstractions (e.g. I believe all containers
 must be traversable and that primitives such as count() have no place in
 a general container) but generally the framework seems to be very well
 put together. It's a great source of inspiration for Phobos. Thanks very
 much for the link.

 Andrei


 
 My understanding of this design is that they identified all the 
 orthogonal properties relevant to containers and that specific 
 containers are a composition of a specific set of such properties.
 Eiffel has MI (different from the c++ implementation) which is helpful 
 if you already have suitable default implementations for these properties.
 
 regarding "traversable" property:
 what if I want a container for a non-ordered type? an example would be a 
 container of complex numbers, how would you traverse it?
 
 what about hash tables?


Well as others mentioned, a hash table is traversable, just not in a 
particularly ordered manner.

IMHO any container must offer at the very least (I'll use stylized 
signatures):

1. Got any?

bool empty();

2. Iterate using at least a one-pass range

OnePassRange!E opSlice();

3. Remove some element from the container and give it to me

E removeAny();

4. Add an element to the container is possible

bool add(E);

5. Nuke

void clear();

I think any container must support these primitives in O(1), and I find 
it difficult to think of a significant category of containers that can't 
support them (but then there may as well be, so please join me in 
thinking of that). A lot of stuff can be done with only these few methods.

Note that even though length() is not part of the interface (as is in 
Gobo's library), it can be computed through iteration with a generic 
algorithm. The idea is to not force containers to write that themselves 
or ungainly cache the length.

Please let me know of any thoughts.


Andrei
Oct 21 2009
next sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:

 IMHO any container must offer at the very least (I'll use stylized
 signatures):
 
 2. Iterate using at least a one-pass range
 
 OnePassRange!E opSlice();


Requiring this to be O(1) seems silly, since the actual iteration will
never be O(1) and can't even be guaranteed to be O(n).


 3. Remove some element from the container and give it to me
 
 E removeAny();


IIRC, C++ had a good reason (related to exception safety) for separating
retrieval and removal operations.


 Note that even though length() is not part of the interface (as is in
 Gobo's library), it can be computed through iteration with a generic
 algorithm. The idea is to not force containers to write that themselves
 or ungainly cache the length.


If the length is often needed, caching is much more efficient than
recalculating from scratch.


-- 
Rainer Deyke - rainerd eldwood.com
Oct 21 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Rainer Deyke wrote:

 Andrei Alexandrescu wrote:

 IMHO any container must offer at the very least (I'll use stylized
 signatures):

 2. Iterate using at least a one-pass range

 OnePassRange!E opSlice();


 
 Requiring this to be O(1) seems silly, since the actual iteration will
 never be O(1) and can't even be guaranteed to be O(n).


The idea is that the cost of creating the iterator should not be 
significant. The cost of the iteration should be O(n) (not greater).


 3. Remove some element from the container and give it to me

 E removeAny();


 
 IIRC, C++ had a good reason (related to exception safety) for separating
 retrieval and removal operations.


C++ does not have D's latitude to relocate objects.


 Note that even though length() is not part of the interface (as is in
 Gobo's library), it can be computed through iteration with a generic
 algorithm. The idea is to not force containers to write that themselves
 or ungainly cache the length.


 
 If the length is often needed, caching is much more efficient than
 recalculating from scratch.


Yah, client code or a refined container may cache it. This has been a 
long discussion in the C++ community. Short version: you can't 
reasonably require O(1) length.


Andrei
Oct 21 2009
prev sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:


 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);



 I think any container must support these primitives in O(1), and I find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in thinking
 of that). A lot of stuff can be done with only these few methods.


I think balanced trees generally take O(lg N) to add and remove elements.

--bb
Oct 21 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:

 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);


 

 I think any container must support these primitives in O(1), and I find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in thinking
 of that). A lot of stuff can be done with only these few methods.


 
 I think balanced trees generally take O(lg N) to add and remove elements.


Good point, thanks. Logarithmic of better.

Andrei
Oct 21 2009
parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:

 Bill Baxter wrote:

 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);



 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.


 I think balanced trees generally take O(lg N) to add and remove elements.


 
 Good point, thanks. Logarithmic of better.
 
 Andrei


Can it be amortized O(lg N) ?
Oct 22 2009
next sibling parent =?ISO-8859-1?Q?Pelle_M=E5nsson?= <pelle.mansson gmail.com> writes:
Don wrote:

 Andrei Alexandrescu wrote:

 Bill Baxter wrote:

 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);



 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.


 I think balanced trees generally take O(lg N) to add and remove 
 elements.


 Good point, thanks. Logarithmic of better.

 Andrei


 Can it be amortized O(lg N) ?


Amortized logarithmic is equivalent to logarithmic.
Oct 22 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:

 Andrei Alexandrescu wrote:

 Bill Baxter wrote:

 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);



 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.


 I think balanced trees generally take O(lg N) to add and remove 
 elements.


 Good point, thanks. Logarithmic of better.

 Andrei


 Can it be amortized O(lg N) ?


Don't see why not. Also, it turns out that iteration over a tree may 
cost O(log n) per step.

Andrei
Oct 22 2009
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Oct 2009 09:07:47 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 Don wrote:

 Andrei Alexandrescu wrote:

 Bill Baxter wrote:

 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:


 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);



 I think any container must support these primitives in O(1), and I  
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in  
 thinking
 of that). A lot of stuff can be done with only these few methods.


 I think balanced trees generally take O(lg N) to add and remove  
 elements.


 Good point, thanks. Logarithmic of better.

 Andrei


 Can it be amortized O(lg N) ?


 Don't see why not. Also, it turns out that iteration over a tree may  
 cost O(log n) per step.


Yes, but it's actually O(n) to traverse the entire tree, because you  
traverse 2n edges in the tree (one left and one right) twice (once to go  
down, and once to go back).

-Steve
Oct 22 2009
prev sibling parent reply Piotrek <starpit tlen.pl> writes:
dsimcha pisze:

 3.  An implementation I call StaticAA, which does not allow the addition or
 removal of keys after it is constructed, but in exchange has almost zero space
 overhead and is very GC-efficient.  It works by maintaining sorted parallel
 arrays and using binary search.


Can immutable attribute be used for it? I mean for determine when create 
StaticAA like array.

Cheers
Piotrek
Oct 19 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Piotrek (starpit tlen.pl)'s article

 dsimcha pisze:

 3.  An implementation I call StaticAA, which does not allow the addition or
 removal of keys after it is constructed, but in exchange has almost zero space
 overhead and is very GC-efficient.  It works by maintaining sorted parallel
 arrays and using binary search.


 Can immutable attribute be used for it? I mean for determine when create
 StaticAA like array.
 Cheers
 Piotrek


I thought of that, but no, because immutable is transitive.  StaticAA would be
strictly a niche library type.  Not even sure, it may be too niche for the std.
lib., but it's incredibly useful specifically for the type of work I do.
Oct 19 2009