mutable list iterators - a proposal

[Jess Austin]

hi Terry,

Thanks for your thoughtful response.  I've tried to address the points
you made, but I could have missed something.  b-)


"Terry Reedy" <tjreedy at udel.edu> wrote in message news:<mailman.21.1079366957.12241.python-list at python.org>...
> Replacing items, which is by far the most common need, works fine.

Fair enough.


> > That is, if you change the length of a section of the list
> > through which the iterator has already passed, it will lose track of
> > where it is.
> 
> Same is true of dicts.  The limitation is documented.  The need is

Actually, dicts just give up at that point.  The fact that lists don't
implied to me that *someone* thought modification should work with
iterators.  Your "other algorithm" suggestions all seem to
specifically avoid the idiom that I'm proposing, which is iteration
over a list that can be modified, such that the loop body can feel the
logical effects of that modification.

All of your suggestions are valid ways to deal with the current
system, by deliberately building more machinery on top of it.  But
none of them allow me to simply code a loop that assumes it will get
the item that is now after the last one it got, even if it may have
made changes to the list in the interim.  The class I posted does
allow that.


> Note that filter is O(n) timewise.  Simply deleting items in place and
> closing up the gap, one at a time, as your approach would appear to do, is
> O(n**2).  Applying an edit list in a batch after the initial scan may also
> be O(n) for typical cases.
.
.
.
> Bottom line: because of the O(n**2) trap, insertion and deletion are
> trickier than mere replacement.

I'm not handling the deletion myself; every method of my class besides
__iter__ calls the corresponding method of list right away.  I'll
grant you that the methods other than __iter__ shouldn't spend so much
time building sequences to record what their actions were.  I think
that instead they should just save a reference to their index value
(which is either a number or a slice), and the iterator can deal with
interpreting the meaning whenever it gets called.  I doubt that saving
a reference to an already existing object would slow any of these
methods down that much.  And of course the methods could make sure
that there are existing iterators before doing anything else.  As for
the iterator, if coded correctly it only has to go through the work of
interpreting the mutation records if there are actually mutation
records.  That is, the slowdown that has to be somewhere here would
only occur if the user specifically coded a loop that modified its
list.

I think I'll spend some time implementing some of the above changes to
see if I can get them to work.


> The listobject.c code is being reworked to make common list operations
> quite noticeably faster.  A slowdown to enable doing something that is
> better done elsewise will not be accepted.  In most cases, the limitation
> protects people from making a bad algorithm choice.

I understand what you're saying here.  Most of the community doesn't
care about this.  The only way to get something like this into core is
to prove it won't cost anyone anything, and then get real lucky.  I
wouldn't put it as "protecting people" so much as I would put it "not
eating their cycles when they're not looking".  I did actually have an
algorithm in mind when I started down this road.  After inputting the
following code, calling tourney(n) builds and returns a tournament
with fair pairings for a number of parties seeded 1 through n.  For
example:

tourney(35)
(((((1, (32, 33)), (16, 17)), ((8, 25), (9, 24))), (((4, 29), (13,
20)), ((5, 28), (12, 21)))), ((((2, (31, 34)), (15, 18)), ((7, 26),
(10, 23))), (((3, (30, 35)), (14, 19)), ((6, 27), (11, 22)))))

It uses the list code I posted before.  It appears to me to be O(n),
which seems like the best possible for this problem.

thanks,
Jess


import math
from itertools import izip, chain, repeat
from mutable_iterable_list import mutable_iterable_list as mil

class tree(object):
    def __repr__(self):
        return '('+repr(self.top)+', '+repr(self.bottom)+')'
    def SetTop(self, top):
        self.top = top
    def SetBottom(self, bottom):
        self.bottom = bottom

class seed(object):
    """trees grow from seeds"""
    def __init__(self, setter, value):
        self.setter, self.value = setter, value
    def __call__(self, value):
        t = tree()
        t.SetTop(seed(t.SetTop, self.value))
        t.SetBottom(seed(t.SetBottom, value))
        self.setter(t)
        self.setter = t.SetTop
        return t
    def __repr__(self):
        return repr(self.value)

def tourney(n):
    """Return a tree structure that reflects a tournament of n
parties"""
    tournament = tree()
    tournament.SetTop(seed(tournament.SetTop, 1))
    seeds = mil((tournament.top,))
    for x, s in izip(range(2, n+1), 
                     chain(*repeat(seeds, int(math.log(n, 2))+1))):
        seeds[:0] = [s(x).bottom]
    return tournament.top