Thanks for the pointers Andy. I had a look at the ordered-map and indeed is a smart and fast implementation. However it relies on continuously growing a backing array, filling dissoc-iated values with nil and hoping that at one point the user will call (compact map) to free all the unused positions. In theory my implementation should scale better as it only uses the space that it needs.
However after more benchmarking I observed the following: - (assoc with multiple key-vals) does indeed slow down the operations. But calling transient and persistent! only makes things worse with bigger maps (I guess the whole map is copied before making it transient). - There is quite a bottleneck due to querying 'head' and 'tail' on every insertion. I thought the performance of a standard hash-map was definitely better :) I could speed up the assoc performance avoiding the insertion of head and tail inside the delegate-map and keeping those two nodes as class fields. That won't make dissoc better but it seems like a reasonable compromise. Out of curiosity, is anybody using ordered-map in their projects? Since performance is comparable to a standard hash-map I would always prefer to use it for the deterministic ordering of the keys. Makes reproducing and catching bugs/errors easier imho. On Monday, April 14, 2014 10:48:48 PM UTC+2, Andy Fingerhut wrote: > > You may also want to take a look at the 'ordered' library, intended to > achieve a similar affect as you describe of remembering elements in the > order they were inserted. I don't know which of the two Github repos below > is the current latest one, but it should be one of them: > > https://github.com/flatland/ordered > https://github.com/amalloy/ordered > > Andy > > > On Mon, Apr 14, 2014 at 12:36 PM, Andy Fingerhut > <[email protected]<javascript:> > > wrote: > >> I don't have time right now to look at the details of your >> implementation, but can answer at least one of your questions. >> >> Clojure's normal PersistentHashMap data structure does create a new >> object for every key you remove (with dissoc), add, or modify the value for >> (with assoc). So if a single assoc call is made that adds/changes the >> values for 5 keys, 5 new PersistentHashMap objects will be created. >> >> That can be avoided if you call transient first, then assoc! N times >> (each time on the result returned by the previous assoc!), then >> persistent. There the assoc! calls still can create new objects, but they >> will often simply edit the existing transient data structure in place. >> These are a bit trickier to implement, so if I were you I would focus on >> getting the persistent version correct and as fast as you can before >> worrying about a transient version. Either that, or do not even both >> creating a transient version at all. >> >> Andy >> >> >> On Mon, Apr 14, 2014 at 11:59 AM, Frankie Sardo >> <[email protected]<javascript:> >> > wrote: >> >>> I'm on a mission to implement an ordered map and set structure for >>> Clojure. Much like LinkedHashMap for Java but as a persistent data >>> structure. >>> The idea is that instead of saving a simple [k v] MapEntry we can save >>> [k v left-node-key right-node-key] plus a global head-node-key to walk >>> through the chains of nodes. >>> Adding a new element creates a new node with a reference on the current >>> tail and the head node and updates the tail and head node to reference the >>> new key in the middle. >>> Removing an element dissociates the selected node and associates the >>> newly updated nodes at the left and the right of the removed one. >>> >>> What puzzles me is the overall performance of this data structure. While >>> Big-O complexity is the same I knew it would be slower due to extra >>> accesses to the inner map, but I expected to be close to the performance >>> of a normal hash-map. Instead insertion is about 5x slower while the >>> removal is 2x slower. So I wonder: is assoc-ing multiple keys at a time >>> generating multiple persistent maps? Or am I doing something blatantly >>> wrong here? >>> >>> However, if somebody'd like to have a look at it I pushed an initial >>> version here https://github.com/frankiesardo/linked. Any help is much >>> appreciated as I'm still a Clojure newbie. >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Clojure" group. >>> To post to this group, send email to [email protected]<javascript:> >>> Note that posts from new members are moderated - please be patient with >>> your first post. >>> To unsubscribe from this group, send email to >>> [email protected] <javascript:> >>> For more options, visit this group at >>> http://groups.google.com/group/clojure?hl=en >>> --- >>> You received this message because you are subscribed to the Google >>> Groups "Clojure" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected] <javascript:>. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to [email protected] Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
