On 12/26/05, Josiah Carlson [EMAIL PROTECTED] 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.
___
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
