Můj problém je jednoduchý: mám pole doublů a potřebuji top-k hodnot a jejich indexů.
Top-k vrátí k největších elementů, které jsou větší než nějaké minimum. Funkce topKEstaimateMin velice rychle odhadne tohle minimum (jednou sekvenčně projde pole a ke cache se chová naprosto ideálně). Odhad nebude skutečné minimum, ale bude o něco menší, tedy vybere víc než k elementů. Ale zároveň garantuje, že nebude větší něž skutečné minimum. Je to tedy dolní mez pro minimum.
Pracuje tak, že rozhazuje elementy do k bucketů (prakticky je to nejbližší mocnina dvou větší než k, protože pak můžu použít maskování bitů, které je mnohem rychlejší než modulo) a počítá jejich maxima. Z těchto maxim pak vezmu minimum, u kterého je garantováno, že je menší nebo rovno než k (nebo více) čísel ze zdrojového pole a v ideálním je poměrně blízko skutečného minima (v mých testech se ukazuje, že pro n=340000 a k=1000, to vrátí minimum pro 6000 čísel, tedy odfiltruje 98% hodnot).
Dá se to dělat taky obráceně, jak maximum minim, ale to se mi zdá, že nebude tak účinné.
Když mám tohle odhadnuté minimum ještě jednou projdu zdrojovým polem a normálně počítám Top-K pomocí hald nebo binárních vyhledávacích stromů, ale věnuji se jenom elementům, které jsou větší než moje odhadnuté minimum + udržuji průběžné minimum.
Řešení s haldami nebo binárními stromy má dobrou asymptotickou složitost, ale jeho konstantní faktory jsou příliš veliké. Do značné míry jde o limitaci Javy a autoboxingu.
Obě řešení (odhadnout minimum + sort + top-k a haldy) jsou přibližně stejně rychlé, ale když se zkombinují dohromady, tak je jejich rychlost naprosto neuvěřitelná.
A potom, co jsem to naprogramoval, tak jsem si matně vzpomněl na jeden paper, který se mi kdysi dostal do ruky, kde se zmínili o podobné myšlence. Ale nepoužívali to pro konstrukci algoritmu pro odhad minima, ale pro důkaz ohledně časových složitostí. Kdybych si jenom vzpomněl, co to bylo za paper.
Aha jasne. Super finta. Jedine co ma trochu strasi je potreba 2x zbehnut cez cele pole "kandidatov".