sublist copies result in behavioural anomoly

Discussion in 'Python' started by Paul Whipp, Nov 7, 2003.

  1. Paul Whipp

    Paul Whipp Guest

    Hi there,

    I'm new to Python so apologies if this is too naive...

    I wanted to recurse down a list to do an ordered insert. All was well
    until...

    def splung(l,x):
    if l[1:]==[]:
    l[1:]=[x]
    elif x>l[1]:
    splung(l[1:],x)
    else:
    l[1:1]=[x]


    >>> foo=[1]
    >>> splung(foo,2)
    >>> foo

    [1, 2]
    >>> splung(foo,3)
    >>> foo

    [1, 2]
    >>>


    It took me a while to divine that the l[1:] is destroyed if its an lvalue
    but returns a copy when used as an argument parameter. If that is the case,
    then is there an effective way to recurse and destructively do an ordered
    insert on a list?

    Cheers,
    Paul
    Paul Whipp, Nov 7, 2003
    #1
    1. Advertising

  2. Paul Whipp wrote:

    > Hi there,
    >
    > I'm new to Python so apologies if this is too naive...


    Not at all, it's a subtle trap. SOME sequences have slices that
    "share" the data with the underlying sequence -- Numeric.array are
    the classic examples of that. Most sequences treat slices as
    (shallow) copies, so your code doesn't work on those, as you saw.
    [[ _assigning_ to a slice of a mutable sequence does always mutate
    the underlying sequence -- the problem is with _accessing_ ]]

    So, basically, instead of "passing down" a slice such as L[1:], which
    might easily be a copy, you want to pass L and the start index
    separately. Doing that overtly in your case gives us:

    def splung(L, x, i=1):
    if L[i:] == []:
    L[i:] = [x]
    elif x > L:
    splung(L, x, i+1)
    else:
    L[i:i] = [x]

    Now, this, of course, is still extremely inefficient (see standard
    library module bisect for an O(log N) way to do the job you're doing
    in O(N) time here; even within the compass of O(N), that tail recursion,
    which Python does NOT optimize away, kills your performance compared
    with that of a simple loop). But at least it does work.

    If you find yourself doing a lot of work with list slices that must NOT
    be copies (but rather share the underlying sequence at all times), you
    may want to wrap them into a 'delegating wrapper' class, whose instances
    hold a reference to the underlying list and a set of indices on it that
    they must affect. It _is_ a somewhat delicate job, and it's not clear
    what should happen to outstanding slices when the underlying list mutates,
    so I'm not going to pursue this idea further for now.


    Alex
    Alex Martelli, Nov 7, 2003
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Bernard A.

    inner sublist positions ?

    Bernard A., Apr 20, 2005, in forum: Python
    Replies:
    2
    Views:
    339
    tiissa
    Apr 21, 2005
  2. giampiero mu

    finding sublist

    giampiero mu, Aug 2, 2005, in forum: Python
    Replies:
    5
    Views:
    377
    Johan Lindberg
    Aug 3, 2005
  3. Richard Lionheart
    Replies:
    12
    Views:
    220
    Richard Lionheart
    Jul 10, 2004
  4. Michael Tan
    Replies:
    32
    Views:
    931
    Ara.T.Howard
    Jul 21, 2005
  5. Victor H. Goff III
    Replies:
    4
    Views:
    104
    Victor H. Goff III
    Sep 7, 2008
Loading...

Share This Page