[issue21592] Make statistics.median run in linear time

Alex Gaynor report at bugs.python.org
Sun Jun 1 06:39:07 CEST 2014


Alex Gaynor added the comment:

I ran the script (modified very slightly for python 2 support) under PyPy 2.3:

$ pypy  select.py
== Single call mode ==
N        sort     select7  select23 select47 select97 select   select2
-------- -------- -------- -------- -------- -------- -------- --------
    5000    0.000    0.010    0.000    0.000    0.000    0.003    0.003
   10000    0.000    0.001    0.001    0.001    0.001    0.000    0.000
   50000    0.002    0.007    0.004    0.002    0.002    0.000    0.000
  100000    0.004    0.010    0.004    0.004    0.005    0.000    0.001
  500000    0.026    0.030    0.019    0.020    0.024    0.004    0.004
 1000000    0.057    0.052    0.037    0.039    0.044    0.007    0.004
 2000000    0.113    0.092    0.069    0.078    0.087    0.017    0.014
 3000000    0.176    0.135    0.109    0.119    0.136    0.024    0.013
 4000000    0.243    0.180    0.137    0.162    0.177    0.024    0.022
 5000000    0.298    0.225    0.176    0.196    0.221    0.035    0.024
 6000000    0.373    0.266    0.207    0.236    0.266    0.051    0.038
 7000000    0.439    0.313    0.248    0.277    0.311    0.054    0.038
 8000000    0.506    0.360    0.282    0.317    0.356    0.039    0.039
 9000000    0.566    0.404    0.315    0.352    0.406    0.055    0.068
10000000    0.626    0.445    0.349    0.395    0.444    0.065    0.046
11000000    0.697    0.492    0.387    0.439    0.490    0.059    0.086
Total elapsed time: 0.96 minutes



$ pypy  select.py                                                                       🕙 57.7s
== Average of three calls mode ==
N        sort     select7  select23 select47 select97 select   select2
-------- -------- -------- -------- -------- -------- -------- --------
    5000    0.000    0.010    0.001    0.001    0.004    0.003    0.002
   10000    0.000    0.005    0.001    0.001    0.002    0.000    0.000
   50000    0.002    0.014    0.006    0.006    0.008    0.002    0.001
  100000    0.005    0.018    0.012    0.011    0.016    0.002    0.001
  500000    0.026    0.071    0.051    0.060    0.076    0.019    0.007
 1000000    0.055    0.135    0.102    0.124    0.148    0.046    0.013
 2000000    0.115    0.257    0.208    0.244    0.291    0.092    0.027
 3000000    0.181    0.396    0.301    0.347    0.383    0.097    0.044
 4000000    0.243    0.530    0.417    0.485    0.559    0.127    0.050
 5000000    0.312    0.656    0.522    0.570    0.688    0.172    0.072
 6000000    0.377    0.789    0.610    0.688    0.772    0.215    0.072
 7000000    0.448    0.927    0.715    0.850    0.978    0.315    0.087
 8000000    0.510    1.049    0.812    0.967    1.193    0.403    0.108
 9000000    0.575    1.191    0.929    1.088    1.241    0.462    0.107
10000000    0.641    1.298    1.070    1.217    1.310    0.470    0.128
11000000    0.716    1.464    1.121    1.343    1.517    0.401    0.147
Total elapsed time: 2.21 minutes

----------
nosy: +alex

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21592>
_______________________________________


More information about the Python-bugs-list mailing list