Bearophile bearophileh...@lycos.com writes:
sorting, and something that's surely not bug-prone. In such situation
having a 'key' argument is *better*. Such sort can be stable.
Nothing stops comparison sorting from being stable. Since the rest of
your post seems premised on the opposite, I
On Tue, 06 Oct 2009 23:20:13 -0700, Paul Rubin wrote:
Bearophile bearophileh...@lycos.com writes:
sorting, and something that's surely not bug-prone. In such situation
having a 'key' argument is *better*. Such sort can be stable.
Nothing stops comparison sorting from being stable. Since
Paul Rubin:
Bearophile:
sorting, and something that's surely not bug-prone. In such situation
having a 'key' argument is *better*. Such sort can be stable.
Nothing stops comparison sorting from being stable. Since the rest of
your post seems premised on the opposite, I hope that clears
Bearophile bearophileh...@lycos.com writes:
What I meant is that a general sorting routine, even in D, is better
to be first of all flexible. So I think it's better for the D built-in
sort to be stable, because such extra invariant allows you to use the
sort in more situations.
Note that
Hrvoje Niksic:
Note that stable sort has additional memory requirements. In situations
where you don't need stability, but do need memory-efficient in-place
sorting, an unstable sort might well be preferred. This is why
libraries such as C++'s STL offer both.
There are stable sorts that
On Tuesday 06 October 2009 02:40:46 pm Paul Rubin wrote:
The problem is that if you allow to use the cmp, lot of programmers
will use it straight away, not even bothering to know what that
strange 'key' argument may be useful for. And they miss the how much
handy 'key' is.
Given how
[Hrvoje Niksic]
Note that stable sort has additional memory requirements. In situations
where you don't need stability, but do need memory-efficient in-place
sorting, an unstable sort might well be preferred. This is why
libraries such as C++'s STL offer both.
FWIW, the additional memory
Raymond Hettinger:
Psychologically, the thing that I find to be interesting is
that beginners and intermediate users seem to take to key
functions more readily than old timers. The key function seems
to be an easy thing to teach (perhaps because that's the
way Excel sorts and the way SQL
Bearophile bearophileh...@lycos.com writes:
The problem is that if you allow to use the cmp, lot of programmers
will use it straight away, not even bothering to know what that
strange 'key' argument may be useful for. And they miss the how much
handy 'key' is.
Given how often we hear
[bearophile]
I love the 'key', it makes my code simpler and it's simpler to
understand. I am not opposed to the idea of keeping cmp, that in some
rare cases may be useful or more natural.
The problem is that if you allow to use the cmp, lot of programmers
will use it straight away, not even
Raymond Hettinger pyt...@rcn.com writes:
Once Kernighan and Ritchie put C's qsort() into the food supply,
we were doomed.
It was already too late. Knuth vol 3 came out in 1973(?) and its
sorting half is mostly about comparison sorting.
FWIW, I think the standard library's unittest module is
Paul Rubin:
bearophile:
I am having a very hard type (despite my implementation, explanations,
etc) explaining to D programmers why for a flexible general-purpose
function a key function argument is often better. They in the end have
added something like that in the std lib, but with a weird
On Tue, 06 Oct 2009 12:28:00 -0700, Raymond Hettinger wrote:
[bearophile]
I love the 'key', it makes my code simpler and it's simpler to
understand. I am not opposed to the idea of keeping cmp, that in some
rare cases may be useful or more natural.
The problem is that if you allow to use
Raymond Hettinger pyt...@rcn.com writes:
So, it looks like the relevant comparison values can be stored in
nested lists:
list_of_lists = \
[[1, [3, [], []],
[7, [5, [], []], []]],
[19, [23, [], []],
[]],
]
Now you've copied all the data out of the
So, it looks like the relevant comparison values can be stored in
nested lists:
list_of_lists = \
[[1, [3, [], []],
[7, [5, [], []], []]],
[19, [23, [], []],
[]],
]
Now you've copied all the data out of the original tree, which is even
Say you want to change the numeric comparisons so that
even numbers always sort before odd numbers, ie.
-4 -2 0 2 4 ... -999 ... -1 1 3 ...
This is too easy:
s = [-2, 4, 2, -1, -3, 1, -4, 0, 3]
s.sort()
s.sort(key=lambda x: x%2)
s
[-4,
Raymond Hettinger pyt...@rcn.com writes:
There were two sorts in my post and only one in yours.
That's why you didn't get the same answer.
Whoops, missed that.
When Guido made the final call, I'm sure he was balancing
a number of goals including language simplification and
one-way-to-do-it.
On Mon, 05 Oct 2009 19:34:27 -0700, Paul Rubin wrote:
Raymond Hettinger pyt...@rcn.com writes:
When Guido made the final call, I'm sure he was balancing a number of
goals including language simplification and one-way-to-do-it. I'm also
sure that sorting lazily evaluated infinite sequences
[Paul Rubin]
Example of list of trees (nested dicts). In practice you could get
such a list from the simplejson module:
list_of_trees = [{'value':1, 'left':{'value':3,'left':None,'right':None},
'right':{'value':7,'left':{'value':5, ...}}},
[Paul Rubin]
The idea was that you have a list of trees that you want to sort, and
an ordering relation between trees:
def gt(tree1, tree2): ...
where you recursively descend both trees until you find an unequal
pair of nodes. You're not trying to sort the nodes within a single
tree.
[Paul Rubin]
The idea was that you have a list of trees that you want to sort, and
an ordering relation between trees:
def gt(tree1, tree2): ...
Are the trees user defined classes? Can the gt() function be added
incorporated as __lt__ method so that you can just run a plain sort:
Raymond Hettinger pyt...@rcn.com writes:
Can you give an example of a list of trees and a cmp function
that recursively compares them?
Example of list of trees (nested dicts). In practice you could get
such a list from the simplejson module:
list_of_trees = [{'value':1,
Paul Rubin http://phr...@nospam.invalid writes:
Example comparison function:
def compare(tree1, tree2):
c = cmp(tree1['value'], tree2['value'])
if c != 0: return c
c = cmp(tree1['left'], tree2['left'])
if c != 0: return c
return cmp(tree1['right'],
Paul Rubin http://phr...@nospam.invalid writes:
c = compare(tree1['left'], tree2['left'])
Of course this recursive call crashes if either branch is None.
Oh well, I'll stop trying to correct it since I'm sure you get the idea.
--
http://mail.python.org/mailman/listinfo/python-list
In 7xtyyhikrl@ruckus.brouhaha.com Paul Rubin
http://phr...@nospam.invalid writes:
Python 2.x provides two ways
and you can use whichever one fits the application better. I have
never understood why Python 3.x finds it necessary to break one of
them. Maybe I can migrate to Haskell by the
kj no.em...@please.post writes:
!!!
Maybe Haskell is much handier than I give it credit for, but it's
hard for me to imagine that it is as convenient as Python 3, even
without the cmp sort option...
Heh, yeah, I was being a bit snarky/grouchy. Haskell has a very steep
learning curve and
Paul Rubin http://phr...@nospam.invalid wrote:
Duncan Booth duncan.bo...@invalid.invalid writes:
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and reverse?
There is no sorting task that *requires* cmp. If all
Paul Rubin wrote:
I still have never understood why cmp was removed. Sure, key is more
convenient a lot (or maybe most) of the time, but it's not always.
Not just more convenient. cmp will always be N log N, in that _every_
comparison runs your function, while key is linear, in that it is
Scott David Daniels scott.dani...@acm.org writes:
Most cases are moreeasily done with key, and it is
a good idea to make the most accessible way to a sort be the most
efficient one. In the rare case that you really want each comparison,
the cmp-injection function will do nicely (and can be
[Paul Rubin]
Yes, think of sorting tree structures where you have to recursively
compare them til you find an unequal pair of nodes.
I'm not sure what you mean by this. What are the semantics of
sorting a tree? Can you outline an example of tree that
could be sorted easily with a cmp
Raymond Hettinger pyt...@rcn.com writes:
I'm not sure what you mean by this. What are the semantics of
sorting a tree? Can you outline an example of tree that
could be sorted easily with a cmp function but not a key function?
The idea was that you have a list of trees that you want to sort,
Is this a homework?
Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.
Let me put up this question: how do you
kj wrote:
Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.
For example,
from random import random
scrambled
can be achieved (to a very good approximation at least) with
scrambled = some_list.sort(key=lambda x: random())
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?
The core developers don't think there
kj wrote:
Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.
Such a task can't exist, because any arbitrary
Laszlo Nagy wrote:
can be achieved (to a very good approximation at least) with
scrambled = some_list.sort(key=lambda x: random())
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?
The core
kj no.em...@please.post writes:
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?
Yes, think of sorting tree structures where you have to recursively
compare them til you find an unequal pair of nodes. To
Paul Rubin:
Yes, think of sorting tree structures where you have to recursively
compare them til you find an unequal pair of nodes.
That's cute. In what situations do you have to perform such kind of
sort?
Bye,
bearophile
--
http://mail.python.org/mailman/listinfo/python-list
kj no.em...@please.post wrote:
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and
reverse?
There is no sorting task that *requires* cmp. If all else fails you can
define a key class to wrap the original wrapper such
On Oct 1, 10:08 am, kj no.em...@please.post wrote:
Challenge: to come up with a sorting task that cannot be achieved
by passing to the sort method (or sorted function) suitable values
for its key and reverse parameters, but instead *require* giving
a value to its cmp parameter.
If you're
Duncan Booth duncan.bo...@invalid.invalid writes:
Is there a real-life sorting task that requires (or is far more
efficient with) cmp and can't be easily achieved with key and reverse?
There is no sorting task that *requires* cmp. If all else fails you can
define a key class to wrap the
In b8f7dea7-0fe3-4e25-9ffd-6796a6e2a...@a37g2000prf.googlegroups.com alex23
wuwe...@gmail.com writes:
kj no.em...@please.post wrote:
This example convinces me that it was a bad idea to
get rid of cmp in Python 3, even if situations like this one are
rare.
It sounds like the entire point of
Bearophile bearophileh...@lycos.com writes:
Yes, think of sorting tree structures where you have to recursively
compare them til you find an unequal pair of nodes.
That's cute. In what situations do you have to perform such kind of
sort?
It came up in a search engine application I've been
43 matches
Mail list logo
