7

I am looking for a persistent sequential datastructure that allows efficient random insertions and deletions. I found the following implementations:

Since there was not much activity in clojure.data.finger-tree for the last two years, and the others are relatively new, I was wondering if someone has experince of using any of these in production, and whether there are alternatives that I have overlooked.

Inshallah
  • 4,804
  • 28
  • 24
  • Why is clojure's PersistentVector not good enough? Can you add details on your use case? – ordnungswidrig May 08 '13 at 12:56
  • @ordnungswidrig, in response to your request for my use case: I have a document that is represented as an array. In response to events, the document is updated with inserts and deletes at a particular offset within the document. Usually there will be only one or two inserts or deletes in a relatively large document. With clojure's persistent vector implementation I have to re-create the document on each event. With a finger-tree, for example, I would be able to split and join the document along the modified offsets. – Inshallah May 09 '13 at 09:31
  • Because of structual shareing this should not impose a big cost. Or do you need access to the split parts, e.g. for optimized on disk persistence? – ordnungswidrig May 13 '13 at 11:44
  • @ordnungswidrig if you re-create the vector that represents the document, there will be no structural sharing of that vector. The problem is, you can't insert or delete elements inside a vector with constant time operations. – Inshallah May 14 '13 at 07:26

1 Answers1

1

Another implementation clojure/core.rrb-vector was announced. Since it's in the clojure github account, it seems like it's going to be the de-facto implementation.

Inshallah
  • 4,804
  • 28
  • 24