OSDir


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Python-Dev] Issue?


python used the "timsort" sorting routine:

https://en.wikipedia.org/wiki/Timsort

So you can look at that and confirm that this is correct behaviour (I'm
betting it is :-)

But in general, sorting is O(n log(n)) -- there are going to be more than n
comparisons.

If comparing is slow, you want to use a key function, to reduce your
comparison to a simple and fast one:

sorted(L, key=lambda i: (i.name, i.score))

or something like that.

personally, I advocate adding a "key_fun" attribute to classes you want to
make efficiently sortable, so you'd have:

sorted(L, key=Student.key_fun)

There was a discussion on python-ideas about adding a __sort_key__ protocol
to python, but there were too many downsides.

-CHB




On Wed, Aug 22, 2018 at 3:40 AM, ??? <1520306395 at qq.com> wrote:

>
> *Why compare twice?*
>
> class Student(object):
>
>     def __init__(self, name, score):
>         self.name = name
>         self.score = score
>
>     def __str__(self):
>         return '(%s: %s)' % (self.name, self.score)
>
>     __repr__ = __str__
>
>     def __lt__(self, s):
>         #print(self, '--', s)
>         if(self.score<s.score):
>             print(self, '<', s)
>             return True
>         if(self.score>s.score):
>             print(self, '>', s)
>             return False
>         if(self.score==s.score):
>             if(self.name>s.name):
>                 print(self, '>', s)
>                 return False
>             if(self.name<s.name):
>                 print(self, '<', s)
>                 return True
>             if(self.name==s.name):
>                 print(self, '==', s)
>                 return False
>
>     def __eq__(self, s):
>         return (self.score == s.score) and (self.name == s.name)
>     def __gt__(self, s):
>         return not ((self == s) or (self < s))
>     def __le__(self, s):
>         return ((self == s) or (self < s))
>     def __ge__(self, s):
>         return ((self == s) or (self > s))
>     def __nq__(self, s):
>         return not (self == s)
>
> L = [Student('Tim', 22), Student('Bob', 33), Student('Kevin', 11),
> Student('Alice', 11)]
> print(sorted(L))
>
> Output:
> (Bob: 33) > (Tim: 22)
> *(Kevin: 11) < (Bob: 33)*
> *(Kevin: 11) < (Bob: 33)*
> (Kevin: 11) < (Tim: 22)
> (Alice: 11) < (Tim: 22)
> (Alice: 11) < (Kevin: 11)
> [(Alice: 11), (Kevin: 11), (Tim: 22), (Bob: 33)]
>
> *Best regards,*
> *Xiaofeng*
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: https://mail.python.org/mailman/options/python-dev/
> chris.barker%40noaa.gov
>
>


-- 

Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR&R            (206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115       (206) 526-6317   main reception

Chris.Barker at noaa.gov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20180822/6807e711/attachment.html>