5 ms·
New Grad: I'd use a linked list here because insertion into the middle is O(1) rather than O(n). Senior Dev: Linked lists have very many more cache misses than
by bitwize 7y ago
New Grad: I'd use a linked list here because insertion into the middle is O(1) rather than O(n).
Senior Dev: Linked lists have very many more cache misses than do vectors, and the difference between hitting cache and hitting main memory is such a huge constant factor that for most reasonable list sizes it never makes sense to use a linked list. Use a vector. Checkmate, smug Lisp weenies.
- erik_seaberg 7y agoYeah, the Lisp world figured out cdr-coding in the 1970s and had moved on to chains of vectors by 1985 according to https://cpsc.yale.edu/sites/default/files/files/tr362.pdf https://cpsc.yale.edu/sites/default/files/files/tr362.pdf. Fortunately they avoided changing the API to make this tradeoff.
- bitwize 7y agoAfaik the only modern Lisp implementation that actually uses these techniques is Clojure.