Max N values transducer

Open jackfirth opened this issue 6 years ago • 1 comments

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.

Sep 13 '19 04:09 jackfirth

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.

Sep 14 '19 22:09 jackfirth