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 <alexey.cherk...@gmail.com> wrote: > 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 can't, but it would require some lower level programming. > > As a disclaimer, you are probably right: for practical purposes, when > dealing with smallish hash-maps, the initial overhead of construction or > element access is far more important. > > Best regards, > Alexey > > On 9 April 2015 at 15:24, Laurent <laurent.ors...@gmail.com> wrote: >> >> 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 log N is limited to less than 30 >> or 62 (depending on the platform), log N can be treated reasonably as a >> constant." >> >> I don't think you can do better than O(n log n) if you want to produce a >> hash in the end. >> >> Laurent >> >> >> On Thu, Apr 9, 2015 at 12:18 PM, Alexey Cherkaev >> <alexey.cherk...@gmail.com> wrote: >>> >>> 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 this message because you are subscribed to the Google Groups >>> "Racket Users" group. >>> To unsubscribe from this group and stop receiving emails from it, send an >>> email to racket-users+unsubscr...@googlegroups.com. >>> For more options, visit https://groups.google.com/d/optout. >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
