Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast insert into the beginning and end of a clojure seq?

Tags:

clojure

In clojure lists grow from the left and vectors grow from the right, so:

user> (conj '(1 2 3) 4)
(4 1 2 3)

user> (conj [1 2 3] 4)
[1 2 3 4]

What's the most efficient method of inserting values both into the front and the back of a sequence?

like image 764
toofarsideways Avatar asked Dec 12 '11 17:12

toofarsideways


2 Answers

You need a different data structure to support fast inserting at both start and end. See https://github.com/clojure/data.finger-tree

like image 108
Joost Diepenmaat Avatar answered Nov 11 '22 02:11

Joost Diepenmaat


As I understand it, a sequence is just a generic data structure so it depends on the specific implementation you are working with.

For a data structure that supports random access (e.g. a vector), it should take constant time, O(1).

For a list, I would expect inserting at the front of the list with a cons operation to take constant time, but inserting to the back of the list will take O(n) since you have to traverse the entire structure to get to the end.

There is, of course, a lot of other data structures that can theoretically be a sequence (e.g. trees) that will have their own O(n) characteristics.

like image 1
Julien Chastang Avatar answered Nov 11 '22 03:11

Julien Chastang