Not sure if it helps, but I believe the immutable hashes are currently
implemented as AVL trees and they will probably become hash-mapped
tries at some point. (I think that change is on a fork of Matthew's
somewhere and still being explored.)
Robby
On Thu, Apr 9, 2015 at 8:49 AM, Alexey Cherkaev
The following is quite probably at worst O(n log n):
(define (hash-merge h1 h2)
(for/fold ([h h1])
([(k v) (in-hash h2)])
(hash-set h1 k v)))
And as the docs say:
Immutable hash tables actually provide O(log N) access and update. Since N
is limited by the address space so that
Yes, it's O(log n * n): n for iteration and (log n) for each insertion. It
should be possible to do it linearly: Haskell's Data.Map.union is O(N+M)
where N and M are the sizes of maps (or Data.HashMap.union). Also,
MIT-Scheme's weight-balanced trees can do O(N+M): I can't see the reason
why Racket
Hi all,
Is it possible to union/merge two immutable hash-maps in linear time? I could
implement it myself if I could have linear time constructor of hashmap from a
sorted list (and assuming converting hash-map-list is i) linear and ii)
produces sorted list).
Regards,
Alexey
--
You received
4 matches
Mail list logo
