[Python-Dev] Issue?
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.scores.score): print(self, '>', s) return False if(self.score==s.score): if(self.name>s.name): print(self, '>', s) return False if(self.name (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 [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Issue?
On Wed, Aug 22, 2018 at 06:40:42PM +0800, 楼晓峰 wrote: > Why compare twice? This is not a mailing list for asking for help with your own code. You can try this list instead: https://mail.python.org/mailman/listinfo/python-list -- Steve ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [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, 楼晓峰 <[email protected]> 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 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 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 > [email protected] > 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 [email protected] ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Starting to use gcc-8 on upstream Python project CI
So is the request simply to use gcc 8 instead of what Travis uses as the default gcc? IOW change https://github.com/python/cpython/blob/28853a249b1d0c890b7e9ca345290bb8c1756446/.travis.yml#L71 somehow to use gcc8 specifically? Since it's only used for the code coverage build I don't think anyone would mind if you changed it. Just open an issue on bugs.python.org and then submit a PR to change it. On Tue, 21 Aug 2018 at 08:35 Jun Aruga wrote: > Hi Miro, > > Thanks for forwarding to python-dev. > > Jun > > > On Mon, Aug 20, 2018 at 8:31 PM, Miro Hrončok wrote: > > On 20.8.2018 20:02, Jun Aruga wrote: > >> > >> Dear Python sig. > >> > >> Someone can you help to promote for the upstream Python project to use > >> gcc-8 on the Travis CI test? > >> Right now the project has 4 test cases [1] including defaut gcc > >> version 4.8 cases on Travis CI. > >> > >> However technically it is possible to use gcc-N (4.8, 5, 6, 7, 8, and > >> etc) on Travis CI. > >> I think that using the latest version gcc-8 on the upstream project is > >> quite beneficial for us. > >> Because maybe we Fedora people are working to fix new version gcc's > >> issues. > >> When the python project start to use gcc-8, it is easy to share the > >> situation publicly outside of Fedora, and of course they can help to > >> check the issues. > >> As I checked the Python project's .travis.yml, I had no idea about how > >> to add gcc-8 case. ;( > >> > >> I can show you 2 cases to use the technique as an example. [2][3] > >> > >> > >> [1] Python > >>https://travis-ci.org/python/cpython > >>https://github.com/python/cpython/blob/master/.travis.yml > >> > >> [2] Ruby > >>https://travis-ci.org/junaruga/ruby/builds/418242410 > >>https://github.com/junaruga/ruby/blob/feature/ci-new-gcc/.travis.yml > >>https://github.com/ruby/ruby/pull/1937 > >> > >> [3] A project I am working as a hobby. > >>https://travis-ci.org/trinityrnaseq/trinityrnaseq > >> > https://github.com/trinityrnaseq/trinityrnaseq/blob/master/.travis.yml > > > > > > > > I'm taking this to [email protected] which is more appropriate > place to > > discuss this. I think Victor is involved in the CIs, is that right? > > > > -- > > Miro Hrončok > > -- > > Phone: +420777974800 <+420%20777%20974%20800> > > IRC: mhroncok > > > > -- > Jun Aruga [email protected] > IRC: jaruga, Office: TPB(Technology Park Brno) Building C 1F, Brno, > Czech Republic > ___ > Python-Dev mailing list > [email protected] > https://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: > https://mail.python.org/mailman/options/python-dev/brett%40python.org > ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Starting to use gcc-8 on upstream Python project CI
Hi Brett, > So is the request simply to use gcc 8 instead of what Travis uses as the > default gcc? Yes, you are right. > IOW change > https://github.com/python/cpython/blob/28853a249b1d0c890b7e9ca345290bb8c1756446/.travis.yml#L71 > somehow to use gcc8 specifically? If we just change only the test case of the gcc version from 4.8 (default) to 8, that's not difficult. I wanted to know how we implement the case if we need it. > Since it's only used for the code coverage build I don't think anyone would > mind if you changed it. Just open an issue on bugs.python.org and then submit > a PR to change it. Okay, as I have not join the Python development, I did not know how the core developers are using the CI. > Just open an issue on bugs.python.org and then submit a PR to change it. Sure, later if anyone does not open the ticket, I will do it submitting the PR. Thanks for the explanation. Jun On Wed, 22 Aug 2018 at 19:04, Brett Cannon wrote: > > So is the request simply to use gcc 8 instead of what Travis uses as the > default gcc? IOW change > https://github.com/python/cpython/blob/28853a249b1d0c890b7e9ca345290bb8c1756446/.travis.yml#L71 > somehow to use gcc8 specifically? Since it's only used for the code coverage > build I don't think anyone would mind if you changed it. Just open an issue > on bugs.python.org and then submit a PR to change it. > > On Tue, 21 Aug 2018 at 08:35 Jun Aruga wrote: >> >> Hi Miro, >> >> Thanks for forwarding to python-dev. >> >> Jun >> >> >> On Mon, Aug 20, 2018 at 8:31 PM, Miro Hrončok wrote: >> > On 20.8.2018 20:02, Jun Aruga wrote: >> >> >> >> Dear Python sig. >> >> >> >> Someone can you help to promote for the upstream Python project to use >> >> gcc-8 on the Travis CI test? >> >> Right now the project has 4 test cases [1] including defaut gcc >> >> version 4.8 cases on Travis CI. >> >> >> >> However technically it is possible to use gcc-N (4.8, 5, 6, 7, 8, and >> >> etc) on Travis CI. >> >> I think that using the latest version gcc-8 on the upstream project is >> >> quite beneficial for us. >> >> Because maybe we Fedora people are working to fix new version gcc's >> >> issues. >> >> When the python project start to use gcc-8, it is easy to share the >> >> situation publicly outside of Fedora, and of course they can help to >> >> check the issues. >> >> As I checked the Python project's .travis.yml, I had no idea about how >> >> to add gcc-8 case. ;( >> >> >> >> I can show you 2 cases to use the technique as an example. [2][3] >> >> >> >> >> >> [1] Python >> >>https://travis-ci.org/python/cpython >> >>https://github.com/python/cpython/blob/master/.travis.yml >> >> >> >> [2] Ruby >> >>https://travis-ci.org/junaruga/ruby/builds/418242410 >> >>https://github.com/junaruga/ruby/blob/feature/ci-new-gcc/.travis.yml >> >>https://github.com/ruby/ruby/pull/1937 >> >> >> >> [3] A project I am working as a hobby. >> >>https://travis-ci.org/trinityrnaseq/trinityrnaseq >> >>https://github.com/trinityrnaseq/trinityrnaseq/blob/master/.travis.yml >> > >> > >> > >> > I'm taking this to [email protected] which is more appropriate place to >> > discuss this. I think Victor is involved in the CIs, is that right? >> > >> > -- >> > Miro Hrončok >> > -- >> > Phone: +420777974800 >> > IRC: mhroncok >> >> >> >> -- >> Jun Aruga [email protected] >> IRC: jaruga, Office: TPB(Technology Park Brno) Building C 1F, Brno, >> Czech Republic >> ___ >> Python-Dev mailing list >> [email protected] >> https://mail.python.org/mailman/listinfo/python-dev >> Unsubscribe: >> https://mail.python.org/mailman/options/python-dev/brett%40python.org > > ___ > Python-Dev mailing list > [email protected] > https://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: > https://mail.python.org/mailman/options/python-dev/happy%40oh4u.net -- Jun Aruga ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Issue?
I wrote Python's sort, so I may know something about it ;-) To my
eyes, no, there's not "an issue" here, but a full explanation would be
very involved.
For some sorting algorithms, it's possible to guarantee a redundant
comparison is never made. For example, a pure insertion sort.
But Python's sort is quite complex, using a number of distinct
strategies dynamically adapting to structure found in the data as it
goes along. There's a possibility for a small bit of redundant work
whenever switching from one strategy to another. That's typical of
"hybrid" strategies.
Your case involves a switch between Python's sort's two simplest
strategies. Let's just look at what matters:
[22, 33, 11, 11]
The first step is searching for "a natural run", an initial
sub-sequence that's already sorted. 22 < 33 says the first two
elements are already in order. Then 11 < 33 says that's the end of
the run.
That part is over now.
The next step is using a binary insertion sort to move 11 into the
already-sorted [22, 33] prefix. A binary search starts looking "in
the middle" first, but a 2-element run is so short that 33 "is the
middle", so it first compares 11 to 33 _again_. So it goes. Code to
detect that special case could be added, but it would probably cost
more than it saves (it always costs time to test for it, but that time
is pure waste unless the tests succeed).
This is specific to an ascending natural run of length 2, so is quite
a special case. For example, in
[22, 33, 44, 11, 11]
11 < 44 ends the natural run, and then the binary search first
compares 11 to 33 ("the middle" of the 3-element natural run), and no
redundant comparison gets made. But in
[22, 33, 44. 43, 11]
43 gets compared to 44 again on the _second_ iteration of the binary
search loop.
In general, this particular strategy switch ends up doing at most one
redundant comparison only if the first element after an ascending
natural run belongs immediately before the last element of the run.
For technical reasons, this can happen at most
min(len(the_list) / 32, number_of_natural_runs_in_the_list)
times, so it's generally trivial in an average-case O(N log N)
process. It's so rare it would be minor in an O(N) process too,
unless N is very small.
A principled way to avoid this would be to skip the "find a run" step
if N is very small, leaving the whole thing to binary insertion sort.
Then a redundant comparison would never be done for small N. But that
would end up doing more comparisons _overall_ in common cases where a
short list starts with a relatively (compared to N) sizable ascending
or descending run.
So I'm happy enough with the tradeoffs already in place.
On Wed, Aug 22, 2018 at 10:37 AM 楼晓峰 <[email protected]> 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 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 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
> [email protected]
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe:
> https://mail.python.org/mailman/options/python-dev/tim.peters%40gmail.com
___
Python-Dev mailing list
[email protected]
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Let's change to C API!
On 2018-07-31, Victor Stinner wrote: > I would be nice to be able to use something to "generate" C > extensions, maybe even from pure Python code. But someone has to > work on a full solution to implement that. Perhaps a "argument clinic on steroids" would be the proper approach. So, extensions would mostly be written in C. However, we would have a pre-processor that does some "magic" to make using the Python API cleaner. Defining new types using static structures, for example, is not the way to build a good API. The other approach would be something like mypyc + cffi. I agree with others that Cython is not the right tool. Regards, Neil ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Let's change to C API!
Neil Schemenauer wrote: Perhaps a "argument clinic on steroids" would be the proper approach. So, extensions would mostly be written in C. However, we would have a pre-processor that does some "magic" to make using the Python API cleaner. You seem to have started on the train of thought that led me to create Pyrex (the precursor to Cython). It went like this: I was getting frustrated with SWIG because it wasn't powerful enough to do what I wanted. I thought about something that would let me write functions with Python headers and C bodies. Then I realised that to really make the C API bearable it would need to take care of refcounting and exception handling, so the body couldn't just be plain C, it would need some Python semantics as well. Given that, it seemed more sensible to base all of the syntax on Python. Also, I wanted to avoid the problem you get with all preprocessors, that when something goes wrong you get error messages in terms of the expanded code rather than the original source. To fix that I would need to do a full parsing and type analysis job -- essentially it would need to be a full-blown compiler in its own right. So, "argument clinic on steroids" is actually a pretty good description of Pyrex. -- Greg ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Let's change to C API!
On Thu, 23 Aug 2018 13:34:02 +1200 Greg Ewing wrote: > Neil Schemenauer wrote: > > Perhaps a "argument clinic on steroids" would be the proper > > approach. So, extensions would mostly be written in C. However, we > > would have a pre-processor that does some "magic" to make using the > > Python API cleaner. > > You seem to have started on the train of thought that > led me to create Pyrex (the precursor to Cython). > > It went like this: I was getting frustrated with SWIG > because it wasn't powerful enough to do what I wanted. > I thought about something that would let me write functions > with Python headers and C bodies. > > Then I realised that to really make the C API bearable it > would need to take care of refcounting and exception handling, > so the body couldn't just be plain C, it would need some Python > semantics as well. Given that, it seemed more sensible to base > all of the syntax on Python. > > Also, I wanted to avoid the problem you get with all > preprocessors, that when something goes wrong you get > error messages in terms of the expanded code rather than > the original source. To fix that I would need to do a > full parsing and type analysis job -- essentially it > would need to be a full-blown compiler in its own right. > > So, "argument clinic on steroids" is actually a pretty > good description of Pyrex. Agreed, at least abstractly, Cython is the best existing solutiong to the problem. The issues to solve for Cython to be usable for the CPython stdlib are IMHO the following: - the bootstrap problem (Cython self-compiles with CPython) - the dependency / versioning problem (Cython is a large quick-evolving third-party package that we can't decently vendor) - the maintenance problem (how do ensure we can change small things in the C API, especially semi-private ones, without having to submit PRs to Cython as well) - the debugging problem (Cython's generated C code is unreadable, unlike Argument Clinic's, which can make debugging annoying) Regards Antoine. ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Let's change to C API!
On 2018-08-23 07:36, Antoine Pitrou wrote: - the bootstrap problem (Cython self-compiles with CPython) This is not a big problem: we can make sure that all stdlib dependencies of Cython either have PEP 399 pure Python implementations or we keep them in pure C. - the dependency / versioning problem (Cython is a large quick-evolving third-party package that we can't decently vendor) Is that a real problem? You're sort of doing the same thing with pip already. - the maintenance problem (how do ensure we can change small things in the C API, especially semi-private ones, without having to submit PRs to Cython as well) Why don't you want to submit PRs to Cython? If you're saying "I don't want to wait for the next stable release of Cython", you could use development versions of Cython for development versions of CPython. - the debugging problem (Cython's generated C code is unreadable, unlike Argument Clinic's, which can make debugging annoying) Luckily, you don't need to read the C code most of the time. And it's also a matter of experience: I can read Cython-generated C code just fine. Jeroen. ___ Python-Dev mailing list [email protected] https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
