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