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

[Martin Blais]

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 *
> > some_constant.  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 + some_other_constant) * (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.