[Python-Dev] (back to): Linked lists -- (was: deque alternative) (original) (raw)

Martin Blais blais at furius.ca
Tue Dec 27 18:51:28 CET 2005

On 12/26/05, Josiah Carlson <jcarlson at uci.edu> wrote:

> A "flat" list or tuple would certainly be more space-efficient up to > this point. But when the graph branches, the 2-tuple representation > allows sharing the common path suffix (which may be very long!): ... > If there's an N-way branch, using 2-tuples allows recording the N new > paths back to the root with incremental memory burden N * > someconstant. You can't do this kind of sharing with a flat list or > tuple, and the incremental memory burden at an N-way branch zooms to > (N + someotherconstant) * (the amount of memory needed to record the > path from the branch point back to the root), due to duplicating the > back-to-the-root info N times. The potential memory saving from > using 2-tuples instead is unbounded.

But one doesn't need to use flat lists. If one were to combine cons cells with Python lists, you can get the space efficiency of lists with the reusability of the desired cons cells (or tuples as the case may be). How? (i, l), where i is the prefix of list l which is the desired portion of whatever l represents. You toss one of those anywhere in your 'flat list', and you have your stored/saved path with a couple dozen bytes. If you are not careful, you end up storing/saving paths which would be stored more efficiently by copying the contents, but at that point we are talking about a constant factor blowup, not the (potentially) exponential blowup of storing all paths as copies, and we can always copy to be more efficient if necessary. I have personally used this trick to construct a union-find data structure in which all unions are reversable regardless of find operation. [1]

Hmm using a single simple data type seems more elegant and less error-prone in this case than what you suggest. I would argue that such solutions come about exactly because lists aren't available. Sure your solution works, but IMO it's a case of raising the hammer with your arm, noticing that it's a screw and not a nail, and then using the hammer sideways to try to turn the screw. I want a screwdriver.

> > So, the list will generally be 1/8th of its size overallocated, or > > 112 elements plus 9 words overhead is 121 words. Better than any cons- > > linked list could be, and insanely better than a cons-linked list > > would be in python. > > You seem to be ignoring possiblities for sharing across lists, and > such sharing is natural in many graph algorithms.

Not necessarily so as I have pointed out above. You said yourself; practicality beats purity. While using cons cells are pure, as us using only flat lists are pure, flat lists are practically smaller than cons cells in certain cases (by a factor of ~4), and non-flat lists can be smaller than cons cells in the rest of the cases.

I don't know about "practicality beats purity" type of arguments. Such general principles don't always apply. Building lists and trees/graphs with cons cells seem very, very practical to me.

Now, it's not all about storage space. What about front-insertion? Everytime I have to type L.insert(0, bli), somewhere that I know runs "often" I cringe. If I had lists I would be able to express my thoughts more clearly in the computer program. Right now, I cringe, and then I just shrug.

More information about the Python-Dev mailing list