Top-k
Ve většině programovacích jazyků mi chybí top-k operace přímo ve standardní knihovně. Představte si situaci, kdy máte určitou kolekci a chcete z ní dostat 10 elementů s největší váhou dle určité funkce. Dosáhnout se toho dá celkem pohodlně řazením, ale to má jeden zásadní nedostatek: Je neefektivní a pomalé.
case class Item(id: Int, weight: Double) val items: Seq[Item] = ??? xs.sortBy(-_.weight).take(k)
Mnohokrát se mi stalo, že jsem si říkal, seřadím to, přece to nemůže být tak pomalé, jen aby se později ukázalo, že v řazení program tráví většinu času. Řazení běží v čase O(n log(n)), ale už skoro šedesát let známe quickselect nebo heap, které to samé zvládnou v čase O(n) respektive O(n log(k)).
Ideálně by mělo jít být oneliner, který by byl nejen stručný, ale i efektivní.
xs.topk(10)(_.weight)
V Javě, Scale a dalších jazycích odkojených JVM se dá použít
java.util.SortedSet
nebo scala.collection.mutable.SortedSet
.
val topk = scala.collection.mutable.TreeSet[Item]()(Ordering.by(_.weight)) val k = 10 for (item <- items) { topk += item if (topk.size > k) topk.remove(topk.head) } println(topk)
To je jednak nepříjemně ukecané, ale hlavě má jeden zásadní problém:
TreeSet
nemůže obsahovat duplicity. Ne duplicity podle equals
,
které dávají smysl, ale duplicity podle řazení. V dokumentaci se to označuje
jako konzistentní s equals
.
The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.
Item(id = 47, weight = 1.0)
je považován za stejný jako Item(id = 69696969,
weight = 1.0)
při řazení podle weight
a výsledná množina bude obsahovat jen
jeden z nich, což je přesně opak intuitivního chování. Člověk by je chtěl oba a
vyhazovat jen duplicity, které a.equals(b)
. TreeSet ale bere jako duplicity
všechno a.weight.equals(b.weight)
.
Správná třída je PriorityQueue
. Ta konečně dělá, co chci. Stále ne moc
elegantně, ale aspoň správně.
val k = 10 val heap = new java.util.PriorityQueue[Item](1, Ordering.by(_.weight)) for (item <- items) { heap.add(item) if (heap.size > k) heap.poll() } val topk = Seq.fill(heap.size) { heap.poll() }.reverse
Navíc tady je ta komplikace, že API nemá metodu, jak en-masse vytahat
elementy seřazené a musím to udělat ručně, což to má stále daleko od pohodlného
one-lineru. Javadoc radí Arrays.sort(heap.toArray())
, ale řazení je přesně
to, čemu se chci vyhnout.
Naproti tomu jazyk D, se kterým se v posledních dnech intimně seznamuji,
má ve standardní knihovně funkci topN
pro materializované kolekce,
topNCopy
pro iterátory a BinaryHeap s příjemným rozhraním pro všechny
ostatní případy.
struct Sim { uint id; float weight; } auto heap = BinaryHeap!(Sim[], "a.weight > b.weight")(new Sim[30], 0); foreach (item; items) { heap.conditionalInsert(Sim(item.id, computeWeight(item)); }
Metoda conditionalInsert
dělá přesně co, potřebuji: Pokud je v haldě místo,
element vloží, pokud ne, vloží ho tam jen, když je větší než současné minimum.
auto result = new Sim[30]; items.map!((item) => Sim(item.id, computeWeight(item))) .topNCopy!"a.weight > b.weight"(result);
Takhle bych si to představoval.
D je super v mnoha dalších ohledech. Autoři si dávají velice záležet na efektivitě2 výsledného kódu i efektivitě použité implementace. Jako jeden z mála jazyků přímo ve standardní knihovna nabízí schwartzSort, což je řazení za pomoci Schwartzian transform pro případy, kdy je porovnávací funkce příliš drahá. Schwartz sort člověk nepoužije příliš často, ale když ho potřebuje, potřebuje ho jako sůl.