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] 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.
