Message 219492 - Python tracker

➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author	scoder
Recipients	alex, ezio.melotti, scoder, steven.daprano, terry.reedy, thomasahle, tim.peters, vajrasky
Date	2014-06-01.07:27:53
SpamBayes Score	-1.0
Marked as misclassified	Yes
Message-id	<1401607674.94.0.247718876699.issue21592@psf.upfronthosting.co.za>
In-reply-to

Content
I tried the same with a Cython compiled version of select.py in the latest CPython 3.5 build. It pretty clearly shows that select2 is pretty much always faster than sorting, by a factor of 2-5x or so. I'll also attach the annotated source file that Cython generates. * CPython 3.5 (de01f7c37b53) == Single call mode == N sort select7 select23 select47 select97 select select2 -------- -------- -------- -------- -------- -------- -------- -------- 5000 0.000 0.001 0.001 0.001 0.001 0.001 0.001 10000 0.001 0.003 0.002 0.002 0.002 0.003 0.002 50000 0.005 0.015 0.010 0.010 0.010 0.013 0.008 100000 0.012 0.032 0.023 0.023 0.023 0.027 0.017 500000 0.085 0.174 0.131 0.129 0.155 0.167 0.103 1000000 0.190 0.375 0.300 0.272 0.311 0.456 0.292 2000000 0.422 0.828 0.588 0.579 0.689 0.865 0.560 3000000 0.680 1.187 0.918 0.906 0.915 1.427 0.801 4000000 0.948 1.574 1.180 1.146 1.177 1.659 1.004 5000000 1.253 2.027 1.684 1.523 1.598 1.874 1.085 6000000 1.577 2.441 1.892 1.754 1.787 2.659 1.055 7000000 1.934 2.870 2.128 2.062 2.093 3.289 1.274 8000000 2.279 3.304 2.430 2.421 2.471 2.569 2.449 9000000 2.560 3.767 2.835 2.768 2.771 3.089 2.348 10000000 2.790 4.123 3.153 3.044 3.097 4.366 3.764 11000000 3.199 4.605 3.658 3.467 3.383 3.867 4.599 Total elapsed time: 9.13 minutes * Cython / CPython 3.5 == Single call mode == N sort select7 select23 select47 select97 select select2 -------- -------- -------- -------- -------- -------- -------- -------- 5000 0.000 0.001 0.000 0.000 0.001 0.000 0.000 10000 0.001 0.001 0.001 0.001 0.001 0.000 0.000 50000 0.006 0.006 0.005 0.005 0.006 0.001 0.001 100000 0.013 0.014 0.011 0.012 0.013 0.004 0.004 500000 0.089 0.091 0.073 0.075 0.079 0.048 0.049 1000000 0.200 0.192 0.156 0.158 0.194 0.081 0.073 2000000 0.451 0.417 0.324 0.355 0.404 0.210 0.135 3000000 0.678 0.614 0.496 0.501 0.530 0.291 0.277 4000000 0.980 0.835 0.720 0.680 0.718 0.402 0.441 5000000 1.276 1.197 0.846 0.857 0.905 0.491 0.425 6000000 1.535 1.274 1.067 1.040 1.087 0.534 0.451 7000000 1.842 1.500 1.226 1.214 1.279 0.549 0.507 8000000 2.168 1.726 1.384 1.398 1.491 0.557 0.535 9000000 2.438 1.987 1.566 1.582 1.660 0.966 0.544 10000000 2.768 2.187 1.747 1.773 1.911 1.116 0.640 11000000 3.116 2.417 1.922 1.950 2.063 1.283 1.024 Total elapsed time: 5.48 minutes

I tried the same with a Cython compiled version of select.py in the latest CPython 3.5 build. It pretty clearly shows that select2 is pretty much always faster than sorting, by a factor of 2-5x or so. I'll also attach the annotated source file that Cython generates.

*** CPython 3.5 (de01f7c37b53)

== Single call mode ==
N        sort     select7  select23 select47 select97 select   select2
-------- -------- -------- -------- -------- -------- -------- --------
    5000    0.000    0.001    0.001    0.001    0.001    0.001    0.001
   10000    0.001    0.003    0.002    0.002    0.002    0.003    0.002
   50000    0.005    0.015    0.010    0.010    0.010    0.013    0.008
  100000    0.012    0.032    0.023    0.023    0.023    0.027    0.017
  500000    0.085    0.174    0.131    0.129    0.155    0.167    0.103
 1000000    0.190    0.375    0.300    0.272    0.311    0.456    0.292
 2000000    0.422    0.828    0.588    0.579    0.689    0.865    0.560
 3000000    0.680    1.187    0.918    0.906    0.915    1.427    0.801
 4000000    0.948    1.574    1.180    1.146    1.177    1.659    1.004
 5000000    1.253    2.027    1.684    1.523    1.598    1.874    1.085
 6000000    1.577    2.441    1.892    1.754    1.787    2.659    1.055
 7000000    1.934    2.870    2.128    2.062    2.093    3.289    1.274
 8000000    2.279    3.304    2.430    2.421    2.471    2.569    2.449
 9000000    2.560    3.767    2.835    2.768    2.771    3.089    2.348
10000000    2.790    4.123    3.153    3.044    3.097    4.366    3.764
11000000    3.199    4.605    3.658    3.467    3.383    3.867    4.599
Total elapsed time: 9.13 minutes


*** Cython / CPython 3.5

== Single call mode ==
N        sort     select7  select23 select47 select97 select   select2
-------- -------- -------- -------- -------- -------- -------- --------
    5000    0.000    0.001    0.000    0.000    0.001    0.000    0.000
   10000    0.001    0.001    0.001    0.001    0.001    0.000    0.000
   50000    0.006    0.006    0.005    0.005    0.006    0.001    0.001
  100000    0.013    0.014    0.011    0.012    0.013    0.004    0.004
  500000    0.089    0.091    0.073    0.075    0.079    0.048    0.049
 1000000    0.200    0.192    0.156    0.158    0.194    0.081    0.073
 2000000    0.451    0.417    0.324    0.355    0.404    0.210    0.135
 3000000    0.678    0.614    0.496    0.501    0.530    0.291    0.277
 4000000    0.980    0.835    0.720    0.680    0.718    0.402    0.441
 5000000    1.276    1.197    0.846    0.857    0.905    0.491    0.425
 6000000    1.535    1.274    1.067    1.040    1.087    0.534    0.451
 7000000    1.842    1.500    1.226    1.214    1.279    0.549    0.507
 8000000    2.168    1.726    1.384    1.398    1.491    0.557    0.535
 9000000    2.438    1.987    1.566    1.582    1.660    0.966    0.544
10000000    2.768    2.187    1.747    1.773    1.911    1.116    0.640
11000000    3.116    2.417    1.922    1.950    2.063    1.283    1.024
Total elapsed time: 5.48 minutes

History
Date	User	Action	Args
2014-06-01 07:27:55	scoder	set	recipients: + scoder, tim.peters, terry.reedy, ezio.melotti, steven.daprano, alex, thomasahle, vajrasky
2014-06-01 07:27:54	scoder	set	messageid: <1401607674.94.0.247718876699.issue21592@psf.upfronthosting.co.za>
2014-06-01 07:27:54	scoder	link	issue21592 messages
2014-06-01 07:27:53	scoder	create