J
Jean-Michel Pichavant
That was known from the begining, was it ? Since key sort trades memorySteven said:
for CPU, you could expect that "masses of data" use cases may fail
because of memory shortage.
JM
for CPU, you could expect that "masses of data" use cases may fail
because of memory shortage.
JM
M
MRAB
You would have to do more than that.
For example, "" < "A", but if you "negate" both strings you get "" <
"\xBE", not "" > "\xBE".
C
Chris Angelico
Strings effectively have an implicit character at the end that's less
than any other character. Easy fix: Append a character that's greater
than any other. So "" < "A" becomes "\xFF" > "\xBE\xFF".
Still not going to be particularly efficient.
Chris Angelico
T
Terry Reedy
For anyone interested, the tracker discussion on removing cmp is at
http://bugs.python.org/issue1771
There may have been more on the old py3k list and pydev list.
One point made there is that removing cmp= made list.sort consistent
with all the other comparision functions,
min/max/nsmallest/nlargest/groupby that only have a key arg. How many
would really want cmp= added everywhere?
A minor problem problem with cmp is that the mapping between return
values and input comparisons is somewhat arbitrary. Does -1 mean a<b or
b<a? (That can be learned and memorized, of course, though I tend to
forget without constant use).
A bigger problem is that it conflicts with key=. What is the result of
l=[1,3,2]
l.sort(cmp=lambda x,y:y-x, key=lambda x: x)
print l
? (for answer, see http://bugs.python.org/issue11712 )
While that can also be learned, I consider conflicting parameters
undesireable and better avoided when reasonably possible. So I see this
thread as a discussion of the meaning of 'reasonably' in this particular
case.
http://bugs.python.org/issue1771
There may have been more on the old py3k list and pydev list.
One point made there is that removing cmp= made list.sort consistent
with all the other comparision functions,
min/max/nsmallest/nlargest/groupby that only have a key arg. How many
would really want cmp= added everywhere?
A minor problem problem with cmp is that the mapping between return
values and input comparisons is somewhat arbitrary. Does -1 mean a<b or
b<a? (That can be learned and memorized, of course, though I tend to
forget without constant use).
A bigger problem is that it conflicts with key=. What is the result of
l=[1,3,2]
l.sort(cmp=lambda x,y:y-x, key=lambda x: x)
print l
? (for answer, see http://bugs.python.org/issue11712 )
While that can also be learned, I consider conflicting parameters
undesireable and better avoided when reasonably possible. So I see this
thread as a discussion of the meaning of 'reasonably' in this particular
case.
I
Ian Kelly
Not to mention that it still has bugs:
"" < "\0"
"\xff" < "\xff\xff"
C
Chris Angelico
That's because \0 isn't less than any character, nor is \xff greater
than any. However, the latter is true if (for instance) your string is
in UTF-8; it may be possible to use some construct that suits your own
data.
ChrisA
M
MRAB
I
Ian Kelly
IOW:
cmp_to_key(lambda x, y: -cmp(x, y))
This is still just taking a cmp function and dressing it up as a key.
P
Paul Rubin
Ian Kelly said:
cmp_to_key(lambda x, y: cmp(y, x))
A
Antoon Pardon
I wouldn't have a problem with it.
I would also like to react to the following.
Guido van Rossum in msg95975 on http://bugs.python.org/issue1771 wrote:
| Also, for all of you asking for cmp back, I hope you realize that
| sorting N values using a custom cmp function makes about N log N calls
| calls to cmp, whereas using a custom key calls the key function only N
| times. This means that even if your cmp function is faster than the
| best key function you can write, the advantage is lost as N increases
| (which is just where you'd like it to matter most
.This is a play on semantics. If you need python code to compare
two items, then this code will be called N log N times, independently
of the fact how this code is presented, as a cmp function or as rich
comparison methods. So forcing people to write a key function in cases
where this will only result in the cmp code being translated to __lt__
code, accomplishes nothing.
As far as I can see, key will only produce significant speedups, if
comparing items can then be completly done internally in the python
engine without referencing user python code.
My rule of thumb is that a < b is equivallent with cmp(a, b) < 0
But what does this have to do with use cases? Does what is reasonable
depend on the current use cases without regard of possible future use
cases? Is the conflict between key and cmp a lesser problem in the
case of someone having a huge data set to sort on a computer that lacks
the resources to decorate as opposed to currently noone having such
a data set? Are we going to decide which functions/methods get a cmp
argument depening on which use cases we currently have that would need it?
This thread started with a request for use cases. But if you take this
kind of things into consideration, I don't see how use cases can then
make a big difference in the final decision.
S
Steven D'Aprano
Incorrect. You don't even need megabytes of data to see significant
differences. How about a mere 1000 short strings?
[steve@wow-wow ~]$ python2.6
Python 2.6.6 (r266:84292, Dec 21 2010, 18:12:50)
[GCC 4.1.2 20070925 (Red Hat 4.1.2-27)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
7.6032949066162109
That's almost ten times slower.
Of course, the right way to do that specific sort is:
0.64559602737426758
which is even easier and faster. But even comparing a pure Python key
function to the cmp function, it's obvious that cmp is nearly always
slower.
Frankly, trying to argue that cmp is faster, or nearly as fast, is a
losing proposition. In my opinion, the only strategy that has even a
faint glimmer of hope is to find a convincing use-case where speed does
not matter.
Or, an alternative approach would be for one of the cmp-supporters to
take the code for Python's sort routine, and implement your own sort-with-
cmp (in C, of course, a pure Python solution will likely be unusable) and
offer it as a download. For anyone who knows how to do C extensions, this
shouldn't be hard: just grab the code in Python 2.7 and make it a stand-
alone function that can be imported.
If you get lots of community interest in this, that is a good sign that
the solution is useful and practical, and then you can push to have it
included in the standard library or even as a built-in.
And if not, well, at least you will be able to continue using cmp in your
own code.
H
harrismh777
Greetings,Antoon said:
Not sure here, but thought you folks might want to have another
viewpoint from someone who is maybe not so close to the trees as to be
able to comment effectively on the forest.
Many of you (Guido included) have lost significant sight of a
critical object oriented philosophical pillar (but not all of you, thank
goodness). To cut right to the heart of it--- NEVER change an advertised
interface. Change the implementation to your little hearts desire, but
never alter an advertised interface (code is based on it, books are
based on it, tutorials are based on it, college comp sci courses are
based on it... etc). If cmp parm is utilized and is helpful or perceived
as useful and existing code requires it then for crying out loud leave
it alone. I think your overall worship of Guido as Python King has left
many of you with nobbled thinking.
On the other hand, this debate and constant bickering is a serious
rehash of an ancient discussion without any new points--- irritating.
Take a look at issue 1771 http://bugs.python.org/issue1771
particularly msg #s 95975 and 95982.... but no, read the whole
thing.... it is very clear that Guido wants to restructure the python
language for consistency and elegance (and who can blame him?). He makes
some very good arguments for the justification of removing the cmp
keyword from list.sort() and builtin.sorted()/ but, that is not the
point... he is breaking a fundamental law of object oriented
programming... don't break and advertised interface (particularly if it
is useful and people are actually making use of it!).
This is insane folks.
Python is one of the most elegant OO languages to gain popular
appeal and wide-spread use. This sad broken move from 2.x to 3.x has the
potential of ruining the language for everyone. Many of us dropped JAVA
(compile once debug everywhere) because it is complicated, a pita to
use, slow, and actually doesn't port too well on any platform... and
here we go again with python. How do the developers of python ever
expect folks to be able to make use of the language into the future when
every time we turn around the interface is broken or being debated in
flux? Many of us want to use the new 3.2+ version, but no one is going
to ship it pre-installed (probably for many years) because of this
issue. There is no way to easily migrate, nor backport, and everyone is
going to be forced to develop code (and have to maintain code) on two
distinct branches (for many years to come). I suspect that people are
just going to stick with back versions for a long time.
We need to get a grip on this, people.
Guido does not need a use case; he just needs to restore the
interface that everyone expects. Put up a message to start to use key=
instead, and plan deprecation for something like five years out... this
just seems like such a no-brainer to me. But then, maybe its just that
I'm too inexperienced to know any better. <sigh>
In the mean time... I'm playing around with 3.2 and really liking
it... hoping that the world will actually be using it someday.
Kind regards,
m harris
S
Steven D'Aprano
Thanks for your comments, M Harris, but I'm afraid you stumble right at
the first step. The difference between implementation and interface is
not specific to object-oriented code -- it is no more, or less, an
"object oriented philosophical pillar" than it is a pillar of functional
programming, procedural programming, or any other programming paradigm
(except perhaps spaghetti coding).
Nor should you say "NEVER". To put your advice in other words:
"Once you have added a feature, no matter how badly thought out, broken,
rarely used, or even actively hated by the entire programming community,
you must continue supporting it forever, adding more and more cruft
around it, just in case some obscure piece of software that hasn't been
maintained for ten years relies on it."
Nobody has forgotten the principle of separating interface from
implementation. This was not an accidental backwards incompatible
change, it was a deliberate decision made in the full knowledge that it
would be a painful move for some, but also in the expectation that *not*
removing cruft becomes even more painful over time.
Cruft has real costs: maintenance costs, development costs, runtime
costs, learning costs, and usability costs. Any language which does not
prune cruft from time to time will ossify and is doing its users a real
disservice. Just not too often.
Nobody is denying that the loss of list.sort(cmp=...) will hurt some
people, or some use-cases. The disagreement is over the question of
whether the pain from its loss outweighs the utility of its removal.
Python is about halfway through the expected migration period from 2.x to
3.x, and so far it has not been worse or more difficult than expected.
Support for Python 3 is about what was expected (probably better than
expected), uptake of Python 3 by users is about what was expected, the
number of nay-sayers, Negative Nellies and trolls claiming that Python 3
will destroy the language is about what was expected, and the number of
credible forks of the language promising to support Python 2 forever is
exactly what was expected: zero.
[...]
Perhaps that's because Java needs to drop some cruft.
Wrong. There is at least one Linux distro, Arch, which ships with Python3
as the system Python. Arch is pretty bleeding edge, but where they go,
others will follow.
Besides, "pre-installed" loses a lot of importance when installation is
as easy as "sudo apt-get python3".
Your FUD is outdated. There are now many major products which support
Python 2 and 3, and some of them out of the same code base. Here is a
small selection:
http://allanmcrae.com/2010/12/python-3-module-support/
http://mail.mems-exchange.org/durusmail/qp/441/
http://nedbatchelder.com/blog/200910/running_the_same_code_on_python_2x_and_3x.html
Note that last link is from 2009.
A
Antoon Pardon
But how does it contradict what I wrote above? Maybe I didn't make
myself clear but in your example, the key function produces ints.
With ints the comparison is completely done within the python engine
without the need to defer to user python code (through the rich
comparison functions). So this is the kind of key I described that
would produce a significant speedup.
But once your key produces user objects that need to be compared
through user python code with __lt__ methods, getting a speedup
through the use of key instead of cmp will not be obvious and
in a number of case you will loose speed.
I don't find that obvious at all.
I don't argue such a general statement. I just argue there are cases
where it is and I supporeted that statement with numbers. The only
way these numbers could be disputed was by focussing on specific details
that didn't generalize.
Now maybe providing a cmp_to_key function written in C, can reduce
the overhead for such cases as Raymond Hettinger suggested. If it
turns out that that works out, then I would consider this thread
usefull even if that will be the only result of this thread.
Something else the dev team can consider, is a Negation class.
This class would wrap itself around a class or object but reverse the ordering.
So that we would get Negation('a') > Negation('b'). That would make it
easy to create sort keys in which partial keys had to be sorted differently
from each other. This would have to be done by the dev team since I
guess that writing such a thing in Python would loose all the speed
of using a key-function.
I'll first let Raymond Hettinger rewrite cmp_to_key in C, as I understand he
suggested, and reevaluate after that.
P
Paul Rubin
Antoon Pardon said:
That is a good idea. SQL has something like it, I think, and Haskell
also has it. I thought about writing it in Python but it would slow
things down a lot. I hadn't thought of writing it in C for some reason.
T
Terry Reedy
Each x.y version (starting with 2.3) is feature stable: just bug fixes,
no additions (except as occasionally required to fix a bug), no
removals. 2.x had few feature changes or removals, as it was planned and
announced that all the big ones were being delayed to 3.x. 2.7 will be
polished for years, depending on how long anyone is willing to work on
it. I have been a bit surprised and disappointed that no 2.x fan has yet
come forward (that I know of) to specifically help fix 2.7 bugs.
Python 3 was announced and as a mildly code breaking version at least 5
years before it came out. Old-style classes were clearly doomed when the
new object. The int division change was also decided on about that time.
I agree that it would have been better if the developer group had been
large enough to make the transition more orderly, but ...
as it is, it was not until 2.7 was out that we took a really good look
at library interfaces and found that 'public interface' was not as well
defined as it should be for some modules. That is much clearer for many
in 3.2.
I already am and fully expect it to be the dominant version in not too
many years. Some linux distributions have already made it the default.
Others have and will hold back.
H
harrismh777
Steven said:
When I speak of implementation vs interface I am speaking from a
strictly object oriented philosophy, as pedigree, from Grady Booch, whom
I consider to be the father of Object Oriented Analysis and Design
(Booch, OO A&D with apps, 1994). He makes this remarkable statement:
"The interface of a class is the one place where we assert all of
the assumptions that a client may make about any instances [objects] of
the class; the implementation encapsulates details about which no client
may make assumptions" (Booch, p50, 1994).
The Class interface holds a "special" firmness which fosters the
client relationship of trust and assumption, without which OOA&D is
pointless. The interface of a Class must not change once advertised, and
once in production. This is specific to OOA&D.
Encapsulation of the abstractions must reside within the
implementation about which no one may make assumptions. This is also
where all of the "cruft" (if any) resides. Cruft never resides at the
interface, only in the encapsulation of the Class abstractions, and only
if the Class was poorly designed.
To put my advice in MY other words, here are my two rules about Class
interface based on Booch, but in terms that are mine, and which are way
simpler to put into practice:
Rule 1:
Never change an advertised Class interface.
Corollary 1)a The Class interface never encapsulates cruft.
Corollary 1)b The Class implementation usually encapsulates cruft.
Corollary 1)c Only the Class implementation may be changed.
Rule 2:
If an advertised Class interface must be changed to remove cruft,
please re-read Rule #1, and review corollaries 1)a, 1)b, and 1)c.
----
As an aside, but in response to your straw man argument regarding
obscure "cruft," none of the bickering regarding this cmp issue is about
obscure code. We are discussing one of the primary methods of one of the
primary Class objects are the lovely heart of Python--- the list.sort().
This is NOT obscure. Guido arbitrarily altered the interface to one of
the MOST important Class objects in all of the Python language. This is
not good, and it does violate the spirit of OOA&D.
If the interface changes had been left to type promotion on integer
divide, and the print() method, then folks would probably not be in such
an uproar over 3x. But Guido over reached the bounds of credulity by
altering a Class method that *many* people find useful, desirable,
efficacious and easy... they use it and the love it (right or wrong).
The client(s) are making assumptions about the List Class interface
and they have an OOA&D right to do so... and they are left with their
rear-ends handing out in the breeze because their assumptions are false.
Not good.
Kind regards,
m harris
C
Chris Angelico
Provably false. Even a well-designed interface, if it is asked to deal
with a changing implementation and changing requirements, will
eventually either acquire cruft, or be found too rigid to be of use.
The only interface immune to this is the transparent interface
(effectively: "just package up the parameters in a single string and
pass it through"), which isn't really an interface at all, it just
exposes something else. In everything else, cruft is a reality that
must be dealt with.
Chris Angelico
H
harrismh777
Terry said:
I appreciate the spirit of your arguments overall, and I do not
necessarily disagree with much of what you are saying. I would like to
challenge you to see this from a little different perspective, if I may.
There are two distinct ways for looking at this "mild code
breakage," and it might be good to think about how we approach changes
in the future based on an understanding of both perspectives, and
consideration for the clients.
In the possible perspective of the Python language developers 3x
changes are mild (in fact, overall, probably even insignificant
percentage-wise). Ok, we removed the cmp comparison keyword from
list.sort(), made the print() method consistent with the rest of the
language, and correctly promoted integer divide 1/2 to float so that the
answer is something greater than zero! Fine. Looks like just a couple
little changes, no big deal, stop your whining.
The perspective of the Class client is something quite different.
They do not look at the overall percentage of Python language definition
that has changed (tiny percentage, right) they look at the overall
percentage of their own projects that have just "broken" and need to be
rewritten to accommodate the disruption in the advertised Class
interface. And to the client-- these tiny changes are magna-bodacious!
(nobbled thinking) You guys have changed integer divide---! the PRINT
print() functionality is diff e r e n t ---! and for crying out loud....
you changed S O R T ( ) !!!
I wonder if folks like google need to do in-place sorts over lists
very often ...?
I wonder how mnay Python scripts call the list.sort() method with
the cmp keyword specified... ? (could it be thousands, or millions?)
All the hoorah you guys are getting, as well all of this incessant
bickering over cmp, is some of the answer to these questions.
When you get ready to change an advertised Class interface in the
future, please consider my interface rules (I gave them to Steven) and
please take into account your client base---the ones who are making
valid assumptions about your Class interfaces. Its easy, and its most
considerate.
king regards,
m harris
P
Paul Rubin
Chris Angelico said:
What happens then is you define a new interface. In Microsoft-speak if
the IWhatever interface needs an incompatible extension like new
parameters, they introduce IWhatever2 which supports the new parameters.
They change the implementation of IWhatever so it becomes a wrapper for
IWhatever2 setting the new parameters to default values, to keep
implementing the old behavior.
Removing cmp certainly isn't the most disruptive change of Python 3,
but it seems like the one with the least benefit.