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 [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/groups/opt_out.
