On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>Thorsten Froehlich <tho### [at] trfde> wrote:
>: Now set a breakpoint at i++  and step into the function.  Go down until you
>: find a loop.   If you can't find a loop, I would really like to know which
>: data structure your library uses to store maps (I assume it is a tree
>: structure).
>
>  It's true that the operator++ has to make several steps in some cases but
>only when it has to go backwards in the tree. When going forward it has to
>make just one step. It has to make log(n) steps backwards only once (when
>going from the largest item which is smaller than the root item to the
>root item). It has to make log(n)/2 steps two times. And so on.
>  What is the amortized O()-time for ++ then?

amortized time is still O(log(n)) in that case, unless I missed something.

>  Btw, using some extra memory it could be possible to avoid all extra steps:
>By putting a pointer to the next item in the walk in each item.

This is precisely what my implementation does.  The only thing I find lacking
in my implementation is the interface; the iterator is not separate and the
usage is confusing at best.  Neither of those two flaws are my doing, however;
I was writing a more robust and efficient implementation of a class that was
designed by a drooling moron on crack (spelled consultant) before I started 
here.  The exact depth of the consultant's stupidity is unplumbed, but suffice
to say that they thought the best implementation was an unsorted array, with
O(1) insertion, O(n) deletion, and O(n) lookup per element.  When this proved
to be too slow for the purpose, they "fixed" the problem by adding a cache to 
keep the five (no, the cache size was not configurable) most recent results.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message