Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > sublist copies result in behavioural anomoly

Reply
Thread Tools

sublist copies result in behavioural anomoly

 
 
Paul Whipp
Guest
Posts: n/a
 
      11-07-2003
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


 
Reply With Quote
 
 
 
 
Alex Martelli
Guest
Posts: n/a
 
      11-07-2003
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[i]:
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
finding sublist giampiero mu Python 5 08-03-2005 04:52 PM
1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds Michael Tan Ruby 32 07-21-2005 03:23 PM
inner sublist positions ? Bernard A. Python 2 04-21-2005 08:39 AM
Interesting anomoly with 3750 EMI version.... Scooby Cisco 0 05-18-2004 08:39 PM
XP Explorer Tree Anomoly Phil McKraken Computer Support 2 01-30-2004 09:07 PM



Advertisments