twitter/algebird — pull request #122 by johnynek (2013-02-15 02:43:03+00:00)
Title: PriorityQueue monoid

Benchmarks: about 500ms to take top 100 from a list 100k long with SortedTakeList, about 30ms for PriorityQueue (on my crappy laptop).

This could be a very big win in scalding jobs that are using SortedTakeList. SortedTakeList is fine for VERY small lists (like top 10 or something). After that, it is a killer. TODO: see if we can make sortedTakeList faster by making a data-structure:

case class TopK[T](items: List[T], max: T)

And then we can quickly skip cases where the left.max < right.items.min (and regain the immutability and safety therein).