Re: Time complexity of operations on collections

[Timothy Baldridge]

A few corrections:

Lists are single linked lists, so nth on them (as well as last) is O(n). Get on lists is unsupported.

Cons on a vector is O(1) since cons converts things to seqs (O(1)) before constructing the cons. 

Count on everything but Cons and LazySeq is O(1). For those two it's O(n) until it hits something in the list that implements Counted (normally PersistentList), then it's O(1) from there on. You might want to list Cons/LazySeq separate from PersistentList for this reason. 

So, cons on a String. That's a interesting question. Cons on anything is O(1). For a string it's the cost of creating a StringSeq on the Java String, then creating a Cons cell who's next pointer references the StringSeq. So that's O(1). But you're now left with a seq, not a string. If you're looking for something like this (str "c" "bar") then yes, that is O(n). 

Timothy 

On Wed, May 22, 2013 at 8:05 AM, John Jacobsen <eigen...@gmail.com> wrote:

I'm studying for an interview and thought it might be nice to know the time complexity of primitive operations on collections in Clojure.  A quick googling didn't turn up a definitive resource.  I would be happy to put one together.  What I had in mind was something like:

Collections: strings, sets, maps, Java arrays, lists, vectors

Operations: peek, pop, conj, cons, assoc/dissoc, get, nth, count

What I have in mind is to fill out this table with the appropriate average big-O (my *guesses* from googling/experimenting/thinking are entered, and may be completely wrong!; sorry for any formatting problems due to varying type styles, perhaps I should have used s-expressions :-) - should be OK with fixed width font):

Collection   get    nth   cons  conj  assoc   pop  peek  count

List         "1"?   "1"?   1     1      X      1    1     1

Vector       "1"    "1"?   n     1     "1"?    1    1     1

Set          "1"    X     "1"    "1"    X      X    X     1?

Map          "1"    X      1     "1"?  "1"?    X    X     1?

String        1     1      n     X      X      X    X     1

Java Array    1     1      n     X      X      X    X     1

Where O("1") is really O(log_{32}(n)), "effectively constant time" as opposed to "true" O(1).  X obviously means you can't do the operation on that type.  Some operations involve casting e.g. a string to a seq; I assume O(n) in that case (?).

(It's probably obvious to everyone else, but it's cool that there are so few 'n's in the table.)

Any corrections, operations to add, data structures to add?  I imagine between all the readers of the list, correcting this table will be trivial.  I am happy to post the resulting table on my blog or anywhere else.

Thanks!

John

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
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 clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
“One of the main causes of the fall of the Roman Empire was that–lacking zero–they had no way to indicate successful termination of their C programs.”
(Robert Firth)

[John Jacobsen]

I should probably also have added sorted-map to the table, though the complexity for each operation is less clear to me.

[Timothy Baldridge]

You might also want to switch "cons" to "conj". This is a super ugly part of the Java api that no one really ever sees. PersistentVector.cons is actually called by clojure.core/conj. clojure.core/cons is something else completely. When talking about how the java code performs it might be best to specify which one you mean. 

Yes it's confusing, I'm sure there is a historical reason for it. 

Timothy

On Wed, May 22, 2013 at 8:24 AM, John Jacobsen <eigen...@gmail.com> wrote:

I should probably also have added sorted-map to the table, though the complexity for each operation is less clear to me.

--

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
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 clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[John Jacobsen]

I am indeed confused.  I have both cons and conj operations in my table.  Are you saying (conj coll item) and (cons item coll) are implemented the same way under the hood?  That wasn't my understanding.  Can you clarify?

[John Jacobsen]

Updated draft of table in more readable form here: http://bit.ly/big-o-clojure

Thanks to Timothy for corrections/additions!  Will keep updating as other replies come in.

[Timothy Baldridge]

No, what I'm saying is that in each persistent collection there is a method called "cons":

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java#L167

However, this is the function called by clojure.core/conj:

https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L75
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L562

Compare this to what clojure.core/cons calls:
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L22
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/RT.java#L565

Basically, clojure.core/cons always converts the collection to a seq, then creates a Cons cell. Conj dispatches to coll.cons and runs whatever code the collection considers best. 

Timothy

[Matthew]

http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html

[John Jacobsen]

Exactly what I was looking for, thanks!!!

John

On Thursday, May 23, 2013 7:06:39 PM UTC-5, Matthew wrote:

http://www.innoq.com/blog/st/2010/04/clojure_performance_guarantees.html