[issue21592] Make statistics.median run in linear time

[Stefan Behnel]

Stefan Behnel added the comment:

Here's also the pathological "average of three calls" case. As Steven suggests, it shows that select() suffers quite heavily (algorithmically), but select2() also suffers enough to jump up to about 2/3 of the runtime of sorting (so it's still 1/3 faster even here). This sounds like select2 should be much faster on random data (run 1) and about as fast on sorted data (runs 2+3). Not unexpected, given the algorithmical characteristics of Timsort.

== Average of three calls mode ==
N        sort     select7  select23 select47 select97 select   select2
-------- -------- -------- -------- -------- -------- -------- --------
    5000    0.000    0.002    0.001    0.001    0.002    0.001    0.000
   10000    0.001    0.004    0.003    0.003    0.003    0.001    0.001
   50000    0.006    0.018    0.017    0.016    0.016    0.011    0.003
  100000    0.013    0.037    0.029    0.031    0.037    0.016    0.009
  500000    0.091    0.246    0.204    0.216    0.227    0.218    0.057
 1000000    0.205    0.535    0.443    0.434    0.459    0.530    0.156
 2000000    0.458    1.137    0.917    0.922    1.052    2.124    0.328
 3000000    0.734    1.743    1.448    1.510    1.607    2.805    0.500
 4000000    1.010    2.400    1.888    2.029    2.157    3.039    0.655
 5000000    1.278    3.021    2.458    2.404    2.717    4.789    0.853
 6000000    1.571    3.629    2.873    3.094    3.279    4.136    1.030
 7000000    1.884    4.258    3.520    3.621    3.530    7.788    1.312
 8000000    2.198    4.977    4.042    4.175    4.080    9.035    1.446
 9000000    2.525    5.555    4.539    4.723    4.633   10.933    1.608
10000000    2.844    6.345    4.929    5.035    5.588   10.398    1.852
11000000    3.194    7.081    5.822    5.973    6.183    8.291    2.111
Total elapsed time: 13.33 minutes

----------

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