[Haskell-cafe] trees and pointers

[Jan-Willem Maessen]

2010/7/16 wren ng thornton <wren at freegeek.org>:
> Jake McArthur wrote:
>>
>> On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
>>>>
>>>> From the docs, lookup is O(min(n,W))
>>>
>>> Actually worse than O(log n).
>>
>> Perhaps I am misunderstanding you, but O(min(n,W)) is either better than
>> or the same as O(log n), depending on how you look at things, but I don't
>> see any way that the former could be *worse* than the latter.
>
> For n < W: min(n,W) > log n
>
> So, when you can guarantee that n < W ---which is almost always the case for
> IntMap---, then O(min(n,W)) is linear and therefore worse than O(log n).

Indeed---though you see worst-case behavior only for carefully-chosen
key sets (eg successive powers of 2).  If the n values in an IntMap
are, say, consecutive or nearly-consecutive, we obtain a log n bound.
I suspect in practice most programmers will see logarithmic behavior.

>> But even so, if your constant factors are k << c, then k*n < c*log n is
> perfectly possible for all n < W, and therefore what matters in the real
> world here is the constant factors. The reason why is that for asymptotic
> purposes O(min(n,W)) and O(log n) belong to the same class of functions
> between constant and linear, so they're effectively the same (in
> asymptotic-land).

The argument for constant-time IntMap performance is essentially
similar to the following argument:

There are balanced trees that provide an O(lg n) bound on tree depth
for a tree containing n elements.  Our computer has only k bits of
address space and therefore the number of elements in any in-memory
tree is O(k).  Thus there is a constant (and smallish) upper bound on
tree depth, O(lg k).  Therefore every balanced tree implementation
offers constant-time access.

As you observe, it's really down to constant factors.  The reason
IntMap (or any digital trie) is so interesting is that it is simple
enough that the constant factors are quite good---in particular we
don't waste a lot of time figuring out if we're going to need to
rearrange the tree structure on the fly.  That turns out to amortize
quite a few extra level traversals in a lot of settings.

It also offers really elegant implementations of union and unions.
Whether that means they're quickish I leave to the benchmarkers.

-Jan-Willem Maessen

>
> --
> Live well,
> ~wren
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>