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