[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