The Quick Mom Algorithm

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Wed Feb 3 09:42:53 PST 2016


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



More information about the Digitalmars-d mailing list