Skip to content

Instantly share code, notes, and snippets.

@mpenet
Last active February 4, 2022 08:01
Show Gist options
  • Save mpenet/e72d6e8f1a4916e157b6ad9a1d33a85d to your computer and use it in GitHub Desktop.
Save mpenet/e72d6e8f1a4916e157b6ad9a1d33a85d to your computer and use it in GitHub Desktop.

Old but still relevant, and since innoq link-rots.

Jarkko Oranen a.k.a. Chousuke posted an excellent table summarizing the performance characteristics of functions operating on different Clojure data structures:

hash-mapsorted-maphash-setsorted-setvectorqueuelistlazy seq
conjnear-constantlogarithmicnear-constantlogarithmicconstant (tail)constant (tail)constant (head)constant (head)
assocnear-constantlogarithmic--near-constant---
dissocnear-constantlogarithmic------
disj--near-constantlogarithmic----
nth----near-constantlinearlinearlinear
getnear-constantlogarithmicnear-constantlogarithmicnear-constant---
pop----constant (tail)constant (head)constant (head)constant (head)
peek----constant (tail)constant (head)constant (head)constant (head)
countconstantconstantconstantconstantconstantconstantconstantlinear
He also provided an explanation of the terminology used; I've expanded it a little for the big-O-challenged (such as me):
  • constant means O(1) complexity, in other words, the time required for the operation is constant and independent of the number of elements contained in the collection. If you think of s simple linked list, you can imagine that adding something to its front always involves the same number of steps, regardless of the number of elements. This is the fastest you can hope for.
  • linear is the slowest that can happen (in the Clojure libs, that is): This is O(n) complexity, meaning that the time required for applying this function on a list with 1000 elements will take a 100 times as long as applying it to a list of 10. In other words: this is slow.
  • logarithmic means that the time required requires log n hops, which is pretty fast (e.g. doing this operation on a list of 1,000,000 items takes 6 times as long as doing it on a list with 10)
  • near-constant performance characteristics refer to the places where the underlying tree structure for most (all?) of Clojure's collections shows its benefits: The number of hops required (as Rich puts it) is log32 n. (Update: I've erased the naïve explanation I had here, will follow up with a better one soon.)

Some operations are, of course not supported on some structures.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment