search

jackfirth / rebellion

A collection of core libraries for Racket
https://pkgs.racket-lang.org/package/rebellion
Apache License 2.0
80 stars 15 forks source link

Max N values transducer #213

Open jackfirth opened 4 years ago

jackfirth commented 4 years ago

There should be a transducer that combines sorting (#212) with taking a finite number of elements. This would allow users to express "limit the stream to the top 10 biggest values" as a transducer. A dual version for taking the smallest N values should also exist. These transducers can be far more efficient than naively doing (transduce ... (sorting <) (taking 10)), since they only need to sort the N biggest elements and can leave the rest unsorted. Possible names: taking-largest and taking-smallest. Blocked on #193.

jackfirth commented 4 years ago

Implementation considerations: this problem is known as partial sorting, and there is a lot of research on how to do it efficiently. See the Partial Sorting wikipedia article for more information.