[Haskell-cafe] trees and pointers
jake.mcarthur at gmail.com
Thu Jul 15 23:26:22 EDT 2010
On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
>> 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.
Excluding DiffArray under certain usage patterns of course, but
DiffArray is slow for unknown reasons besides algorithmic complexity.
>> 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.
More information about the Haskell-Cafe