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