[Haskell-cafe] trees and pointers
me at rkit.pp.ru
Thu Jul 15 18:33:12 EDT 2010
> Thanks for an example! Probably, one can think about using Arrays
> instead of Map or IntMap in order to achieve 'true' O(1) in pure. But
> I suppose that there are some trouble with array expanding. Or
> somebody would already make it.
Pure arrays have O(n) modification time.
> From the docs, lookup is O(min(n,W))
Actually worse than O(log n).
B-tree with 4 or even 8 child nodes will be the best solution. This
trees have better lookup time and worse space efficiency, but we can
almost eliminate space overhead by using dense keys.
More information about the Haskell-Cafe