On Friday, 29 January 2016 at 22:47:44 UTC, Andrei Alexandrescu
wrote:
http://dpaste.dzfl.pl/05a82699acc8
While thinking of MoM and the core reasons of its being slow
(adds nice structure to its input and then "forgets" most of it
when recursing), I stumbled upon a different algorithm. It's
much simpler, also deterministic and faster than MoM for many
(most?) inputs. But it's not guaranteed to be linear. After
having pounded at this for many hours, it is clear that I am in
need of some serious due destruction. I call it a "quick median
of medians" or in short "quick mom".
The code does not compile when I try to use topN, as medianOfUpTo
is not present. Please include it.
Anyway, for now, I just wanted to quickly check whether my
previous attack on topN would have any effect here.
I've replaced the line
if (r.length <= 5) return medianOfUpTo!(5, lp)(r);
with a quick fix:
if (r.length == 2)
{
if (!less (r.front, r.back)) swap (r.front, r.back);
return 0;
}
if (r.length == 1) return 0;
Here is the code (just glued together the two snippets):
http://dpaste.dzfl.pl/f648a600a11d
Turns out like maybe it does have its effect (size = 5 million):
building Element array: 2442 msecs
checking Element array: 2432 msecs
checking int array: 388 msecs
checking random int array: 140 msecs
checking increasing int array: 41 msecs
checking decreasing int array: 42 msecs
The int array built by the attack makes the program run slower
than a random array, and the ratio increases with size.
