2.3 list reverse() bug?

A

Alex Martelli

Bjorn Pettersen wrote:
...
ambigous when I stated it. If you look at my response to Alex, you'll see
that I really do mean that copies are virtually never needed [in the
aesthetic, not the Turing complete sense], and if you do use them you're

BTW, the reason copy.copy exists is to make _polymorphic_ (shallow) copies:
copying without needing to know what object you're copying. E.g., consider:

def remove_baddies(container, badp):
for x in copy.copy(container):
if badp(x): del container[x]

do I hear you cringing? OK, this code is _polymorphic_: it works just
as well whether container is a list (applies badp on the items) or a
dict (applies badp on the keys) or any other container which implements
the needed protocols (copyable, iterable, indexable by the items you
get when iterating, supports item-deletion).

Can you show us how to obtain this level of polymorphism w/o copy?

Or, don't you consider polymorphism elegant? Personally, I do!


Alex
 
P

Paul Rubin

Andrew MacIntyre said:
list(x) is my favourite way to make a shallow copy of list x, but x[:]
and copy.copy(x) are essentially equivalent.

Behaviourally yes, performance wise no.

Eh? Last time I looked at the copy module, x[:] is exactly what it did.
 
D

Dennis Lee Bieber

Bjorn Pettersen fed this fish to the penguins on Saturday 27 December
2003 13:26 pm:
Of course not, this is USENET <wink>. I was going to put something
here about the quote from Winnie the Pooh about "when I say ___ I mean
___", but googling for "Winnie the Poo" is not something anyone should
do before lunch... seriously.
That sounds more like something Humpty-Dumpty would say. (Alice's
Adventures in Wonderland, I believe, though it could have been Through
the Looking Glass and What Alice Found There).

--
 
A

Alex Martelli

list(x) is my favourite way to make a shallow copy of list x, but x[:]
and copy.copy(x) are essentially equivalent.

Behaviourally yes, performance wise no.

[alex@lancelot x]$ timeit.py -c -s 'x=range(999)' 'x[:]'
100000 loops, best of 3: 18.3 usec per loop

[alex@lancelot x]$ timeit.py -c -s 'x=range(999)' 'list(x)'
10000 loops, best of 3: 22 usec per loop

[alex@lancelot x]$ timeit.py -c -s 'x=range(999)' -s'import copy'
'copy.copy(x)'
10000 loops, best of 3: 22 usec per loop

Close enough, for me, that the words "essentially equivalent" appear
to be quite justified. How much of your program's time is spent doing
shallow copies of lists, that these tiny differences in overhead are, to
you, ESSENTIAL to your program's performance?


Alex
 
A

Andrew MacIntyre

Close enough, for me, that the words "essentially equivalent" appear
to be quite justified.

I realised after sending that I should have qualified my comment, as the
performance differential of course disappears into the noise as the number
of elements increases. For lists of 10s of elements and fewer, the slice
has a noticeable advantage over the other 2.

It is also a fair question whether any useful algorithm would be
noticeably affected by the performance difference.

Raymond Hettinger's work on a function/method for returning sorted lists
will further reduce the need for the shallow copy as a specific operation.

Regards,
Andrew.
 
A

Alex Martelli

Paul said:
Andrew MacIntyre said:
list(x) is my favourite way to make a shallow copy of list x, but x[:]
and copy.copy(x) are essentially equivalent.

Behaviourally yes, performance wise no.

Eh? Last time I looked at the copy module, x[:] is exactly what it did.

copy.copy(x) will have two extra name look-ups at the start (one for
the outer 'copy' name, one for the 'copy' name inside the module), a
function call, and inside that function a type(x) and a dispatch via
a type-to-function dictionary. list(x) has roughly similar overhead.
Apparently, these miniscule extra bits of overhead appear to be enough
for Andrew to reject the "essentially equivalent" evaluation.


Alex
 
A

Arthur

[posted and mailed]



[...]
But this is also my approach, I guess. Not exactly writing Universe
Critical code, I tend to proceed with a light reading of the docs, and
learn by having my naive intuitions corrected - as necessary when
necessary, by finding something broken.

My late boss approached languages and other problems the same way, and I
never could understand how he dealt with what for me would be continous
frustration.

There is of course the "take it out on other people" option for
dealing with the frustration.) Particularly popular option among the
population of bosses, in my experience. ;)

Or else, better - simply considering it the cost of doing busniess in
the manner in which one chooses to being do business. And consider
oneself net, net ahead of the game - for oneself - when comparing it
to the full cost of doing business in some fundamentally different
way.
Doing language theory in grad school, while not always the most immediately useful, is a wonderful
way to develop passionate ideas about how things ought to be (you should
have heard the lunch discussions when Java came out <grin>).

Well of course *my* passionate ideas about language design resolve to
how well that design faciliates *my* chosen way of doing business.
And of course expect everyone to agree.

They don't?
But there is I feel a valid point implicit in my original question.

The "I have been using Python 42 years and never imported copy" is a
very ambiguous assertion,made time and again.

You're most certainly correct, although I don't believe it was very
ambigous when I stated it. If you look at my response to Alex, you'll see
that I really do mean that copies are virtually never needed [in the
aesthetic, not the Turing complete sense], and if you do use them you're
likely to (a) do more work, sometimes potentially _much_ more work, (b)
complexificate the algorithm making it harder to visually verify, (c) make
it _much_ harder to _prove_ correct, and (d) you're adding another entity
that you'll have to keep in memory when you're visualizing the system.

But...

I am going to perform an opertaion on a list or dictionary and need
the alternative to rollback to the pre-operation state. Restore
"initial". Why would that be a particularly uncommon or unwholesome
state of affairs, and why isn't leaving a copy behind a practical
approach?
mission critical subsystem as the 'data-structure' managing this
information we wouldn't use anything but a Python code generator,
generating over 380KLoc of C++ code, SQL schemas and stored procs, etc.)].

The world is safe from me attempting anything mission critical - for
the time being.
I can also categorically say that it's a really bad idea to walk to the
middle of a bridge, precariously climb up on the railing, before doing a
swan dive towards the dry riverbed several hundred feet below... but it's
really fun if you have a bungie-cord attached.

Preferably well attached.
I haven't encountered any rules that didn't come with their own list of
exceptions.

A mutable list, of course.
Sure it is weird to want to think of such trivialities when the code is
working, but clean code makes me happy <smile>, and hey, after 20+ years of
programming, I'm still excited when I go to work and I still program after
I come home...

I compulsively refactor. Til I have something that seems to me to be
nice. But nice based on the alternatives as I understand them. I
also know that there are alternatives I don't (yet) underestand.
Which when I do understand, will generate a new round of refactoring.

This is how I got so smart, by the way ;)
I sincerely do not grasp mentally however, how some people can "break path" in a new domain guided
mainly by their intuition? My intuition definitely doesn't work at that
level :) If you have any meta-analysis it would be very interesting to
contemplate...

Well isn't this something that high level languages, in general - have
made into a not totally unreasonable approach.

Its an expereince to approach things this way - in both the worst and
best sense.
Of course not, this is USENET <wink>.

Ain't it though.

Art
 
A

Andrew MacIntyre

Apparently, these miniscule extra bits of overhead appear to be enough
for Andrew to reject the "essentially equivalent" evaluation.

You have misconstrued the intent of my observation, which was simply to
highlight that there may be a reason other than aesthetics to choose one
of the 3 alternatives.
 
A

Alex Martelli

You have misconstrued the intent of my observation, which was simply to
highlight that there may be a reason other than aesthetics to choose one
of the 3 alternatives.

There can be several such reasons, and the performance differences among the
various constructs, which you singled out as the only thing worth mentioning,
are hardly ever interesting enough to reject the "essentially equivalent"
tag. To me, the most interesting issues arise in circumstances where
_polymorphism_ is in play -- in other words, where you want to code a
function so that it works with other types of sequences (or other iterables)
as arguments, _not_ just Python lists. Under such circumstances, list(x)
does ensure the type of its result (a list), whatever the type of x, as long
as x is iterable. copy.copy(x) should instead return an object of the same
type as x -- each of these two behaviours may be preferable, depending
on other circumstances. x[:] on the other hand guarantees just about
nothing -- in particular, it does not guarantee that a shallow copy is taken,
as it might well return a sequence that shares data with x (that's what it
does for Numeric arrays, a crucial sequence type for many applications
of Python).

If you're thinking of a programmer choosing among the various copy idioms,
in each and every case that presents itself, on the basis of a full grounds-up
analysis of all the considerations that apply to that specific case, then
there is no reason, except aesthetics, to prefer one idiom over the others
"in general". One may _recode_ a copy originally coded as list(x) into x[:],
for example, as an optimization under very special circumstances (i.e. after
ascertaning that the operation is a bottleneck and that it often occurs on
tiny enough lists to matter) -- but of course it would be suboptimal to
prematurely _prefer_ x[:] as a matter of course given that the performance
differences often won't matter (you know what they say about premature
optimization, yes?). The _functional_ advantages of list(x) and copy.copy(x)
will matter only when the type of x is not entirely certain -- for example
when one wants, as a rule, to write reusable code (optimizing it, at the
expense of reducing reusability, only if and when performance increase is
_demonstrably_ necessary)... but some people believe that "premature
generality" (including reusability) is almost as bad a trap as premature
optimization (MHO is that in theory it _might_ be, but in practice the latter
tends to be a far worse blight).

I believe, however, that much coding happens to "just use the idiom one
is most familiar with" for a given functionality -- rather than on the basis
of a specific, detailed, exhaustive analysis, with each line of code one
writes, of all the functional, robustness, and performance requirements
that apply to that exact set of circumstances. Because of this perfectly
natural occurrence, I further believe that it's important to _acquire good
idiomatic coding habits_ -- such good habits maximize the probability that
the code we write "by rote, without deep specific analysis" will be good
enough. Very rarely will the "goodness" of roughly equivalent idioms be
determined by performance issue, in my opinion; basically, almost only
cases where different idioms yield different big-O performance, as in the
notorious performance pitfall of "bigstring += smallstring" loops versus
''.join(sequence_of_smallstrings). One exception might be the use of
somelist.sort(comparison) versus DSU idioms -- they both have the same
big-O performance characteristics, but the multiplicative constants can be
SO much bigger, when passing a comparison function, that some care is
warranted in order to make DSU a habit.

Much more often than by performance considerations, the choice of
what idiom is a "good habit" to acquire may be guided by issues of
generality, robustness, functionality. In this light, I think that list(x) is
generally preferable to x[:], and more often than not slightly better
than copy.copy(x), as the habitual way to code for this functionality --
not, IMHO, a "premature generalization", because it _is_ essentially
equivalent to the alternatives... but, when the difference matters, it
tends to favour it more often than not (on axes other than ones which
relate directly to optimization).


Alex
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,772
Messages
2,569,593
Members
45,111
Latest member
VetaMcRae
Top