4 ms·
Is there a way to implement cdr more efficiently? (I don't know PHP.)
by jimbokun 16y ago
Is there a way to implement cdr more efficiently? (I don't know PHP.)
- koenigdavidmj 16y agoIn more traditional lists, the main data structure over which car and cdr munched was a linked list. car and cdr were just accessors for the two fields (usually used as a data container and a 'next' pointer).
- jimbokun 16y agoI mean, is there any way to get that efficiency from PHP data structures? I guess you could implement a linked list data structure from scratch, but that would likely limit inter-operability with the rest of PHP.
- tiles 16y agocdr could return an array "object" where it references the entire array, and a pointer where it should start indexing. Instead of using linked-lists as the fundamental datatype, it could use array subsets.
- Scriptor 16y agoSomething like this could be very feasible, especially when combined with the array interfaces so that the fact it's an object with a moving pointer isn't even noticed.
- koenigdavidmj 16y agoIf I recall correctly, Clojure does something like this on most of its basic types. Since it wants users to avoid in-place modifications, it provides data structures that have modification functions that return new instances of the data structure with the changes made. These also do not regenerate the whole structure; they only use memory to point to the one modified/added element. Please correct me if this is false.
- gtani 16y agoThat's correct, except for performance tweaks like transients http://technomancy.us/132 http://technomancy.us/132 http://fupeg.blogspot.com/2009/11/persistent-data-structures.html http://fupeg.blogspot.com/2009/11/persistent-data-structures... http://groups.google.com/group/clojure/msg/99d1cfcc3a9b520b http://groups.google.com/group/clojure/msg/99d1cfcc3a9b520b