3 ms·
This is esssentially CDR coding. Here's what a Lisp FAQ has to say about that: http://www.faqs.org/faqs/lisp-faq/part2/section-9.html http://www.faqs.org/faqs/
by derleth 15y ago
This is esssentially CDR coding. Here's what a Lisp FAQ has to say about that:
http://www.faqs.org/faqs/lisp-faq/part2/section-9.html http://www.faqs.org/faqs/lisp-faq/part2/section-9.html
Essentially, it says that it isn't as good an idea as you might imagine, because lists aren't often created all at once and they get chopped up and inserted into often enough the advantages of the scheme disappear.
- dpark 15y agoThese seem like like related but distinct ideas. From what I understand, CDR coding is basically an optimization that replaces the entire list with an array. This has the effect that inserting elements involves an ugly and expensive indirection hack. Unrolled linked list don't exhibit this behavior (though they have other drawbacks). Their behavior is closer to that of B-trees, where size-bounded multi-element nodes can be split and joined cheaply, which allows for cheap element insertion.