On 02/02/2016 05:14 PM, Ivan Kazmenko wrote:
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.
Thanks for looking into this. I've been working a lot more on this and
have an algorithm in testing that would be very interesting to develop
an attack input for. Please give me to the end of the week and I'll send
it along. Thx! -- Andrei
