Extreme Cleverness: Functional Data Structures in Scala
Written by Eric Normand. Published: August 11, 2012. Updated: August 21, 2018.
Eric Normand's Newsletter
Software design, functional programming, and software engineering practices
Over 5,000 subscribers
Reference: Extreme Cleverness: Functional Data Structures in Scala
According to Daniel Spiewak, Clojure's vec requires, in the worst case, 7 array accesses and 14 bit operations.
On really large datasets---this just astonished me when I discovered it---on really large datasets this data structure [Clojure vec] beats java.util.ArrayList for lookup. It beats java.util.ArrayList for datasets that are in the 2 billion range. That is incredibly fast. java.util.ArrayList is an array, right? And we're beating an array.