Re: Q: sort's key and cmp parameters

[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 memor

Re: Q: sort's key and cmp parameters

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

Re: Q: sort's key and cmp parameters

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

Re: Q: sort's key and cmp parameters

Bearophile 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 stable sort has addition

Re: Q: sort's key and cmp parameters

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 cl

Re: Q: sort's key and cmp parameters

On Tue, 06 Oct 2009 23:20:13 -0700, Paul Rubin wrote: > Bearophile 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 p

Re: Q: sort's key and cmp parameters

Bearophile 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 hope that clears things up

Re: Q: sort's key and cmp parameters

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

Re: Q: sort's key and cmp parameters

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

Re: Q: sort's key and cmp parameters

Raymond Hettinger 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 also a > co

Re: Q: sort's key and cmp parameters

[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

Re: Q: sort's key and cmp parameters

Bearophile 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 "consenting adults" as justif

Re: Q: sort's key and cmp parameters

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 SQ

Re: Q: sort's key and cmp parameters

On Mon, 05 Oct 2009 19:34:27 -0700, Paul Rubin wrote: > Raymond Hettinger 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 was not o

Re: Q: sort's key and cmp parameters

Raymond Hettinger 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. I'm also

Re: Q: sort's key and cmp parameters

> > >  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=

Re: Q: sort's key and cmp parameters

Raymond Hettinger writes: > FWIW, you could also just flatten it to: [(1,3,7,5), (19,23)]. > > The point is that the tree comparisons you presented have a > predetermined order of values to compare, so they either be recast a > flattened list of comparison values or the tree itself can be cast >

Re: Q: sort's key and cmp parameters

> > 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,

Re: Q: sort's key and cmp parameters

Raymond Hettinger 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 origin

Re: Q: sort's key and cmp parameters

[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, ...}}}, >

Re: Q: sort's key and cmp parameters

kj 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 will never be as

Re: Q: sort's key and cmp parameters

In <7xtyyhikrl@ruckus.brouhaha.com> Paul Rubin 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

Re: Q: sort's key and cmp parameters

Paul Rubin 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

Re: Q: sort's key and cmp parameters

Paul Rubin 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'], tree

Re: Q: sort's key and cmp parameters

Raymond Hettinger 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, 'left':{'value':3,'left':None,'r

Re: Q: sort's key and cmp parameters

[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:

Re: Q: sort's key and cmp parameters

[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 >

Re: Q: sort's key and cmp parameters

Raymond Hettinger 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, and an order

Re: Q: sort's key and cmp parameters

[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 funct

Re: Q: sort's key and cmp parameters

Scott David Daniels 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 written as a > recip

Re: Q: sort's key and cmp parameters

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 run

Re: Q: sort's key and cmp parameters

Paul Rubin wrote: > Duncan Booth 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

Re: Q: sort's key and cmp parameters

Bearophile 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 involved with. --

Re: Q: sort's key and cmp parameters

In alex23 writes: >kj 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 this exercise was to get other >people to confirm your bias for you. The only problem with this

Re: Q: sort's key and cmp parameters

kj 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 this exercise was to get other people to confirm your bias for you. -- http://mail.python.org/mailman/listinfo/python-list

Re: Q: sort's key and cmp parameters

Raymond Hettinger writes: > If you're assuming a consistent sort-order (transitivity, not > evolving over time, etc), then the cmp method and key method > are mathematically equivalent (you could always do a compare > sort first, record the order produced, and assign the position > number as a key

Re: Q: sort's key and cmp parameters

Duncan Booth 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 original wrapper such

Re: Q: sort's key and cmp parameters

In <7x1vln2bzh@ruckus.brouhaha.com> Paul Rubin writes: >kj 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

Re: Q: sort's key and cmp parameters

In Raymond Hettinger writes: Thanks for an extremely helpful reply! >If you need to sort by an ascending primary key and a descending >secondary key, you may find it easiest to sort in two passes >(taking advantage of guaranteed sort stability): >sorted(s, key=secondary, reversed=3DTrue

Re: Q: sort's key and cmp parameters

On Oct 1, 10:08 am, 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. If you're assuming a consistent

Re: Q: sort's key and cmp parameters

kj 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 that comparing th

Re: Q: sort's key and cmp parameters

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

Re: Q: sort's key and cmp parameters

kj 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 sort with key=... you

Re: Q: sort's key and cmp parameters

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 developers

Re: Q: sort's key and cmp parameters

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 co

Re: Q: sort's key and cmp parameters

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 is

Re: Q: sort's key and cmp parameters

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 > s

Re: Q: sort's key and cmp parameters

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 defin

Q: sort's key and cmp parameters

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 = some_list.sort(c