Repository navigation
Extend k_smallest with largest and key options #586
Description
Currently this crate only has k_smallest. Compare this to the offering for min/max (which are the same function, just limited to k = 1):
position_max
position_max_by
position_max_by_key
position_min
position_min_by
position_min_by_key
I think it would be nice if we extended k_smallest to:
k_smallest
k_smallest_by
k_smallest_by_key
k_largest
k_largest_by
k_largest_by_key
Reacted by C William Hakes
Reacted by Ltrlg, Alisander Qoshqosh, Kier Ada Davis, Martin Pool, Tim Leslie, Douwe Schulte and Philippe Cholet
Activity
orlp commentedon Dec 9, 2021
If this has a good chance of being accepted I'm willing to make a pull request for this feature.
phimuemue commentedon Dec 10, 2021
Sounds great to me!
If you decide to do a PR, could you try to implement
k_smallestandk_smallest_by_keyin terms ofk_smallest_by? (So that the implementations are tied together and do not diverge.)jswrenn commentedon Dec 10, 2021
This has a great chance of getting merged! 🙂
orlp commentedon Dec 14, 2021
Am I understanding it correctly that there's a bug in the current implementation?
https://github.com/rust-itertools/itertools/blob/master/src/k_smallest.rs#L10
This assumes the iterator is a
FusedIterator, does it not? I think we need to call.fuse()first?EDIT: yes, this is wrong: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=cc076206949046426a9d76dc005368b1
orlp commentedon Dec 14, 2021
Looking at it, I don't see a way we could implement this using
std::collections::BinaryHeap, if we don't wish to duplicate the comparison functionktimes (and probably destroy inlining). I'm thinking of manually implementing the sifting logic - mostly copying from the stdlib, any thoughts on this?scottmcm commentedon Dec 14, 2021
Or skip the
for_eachifheap.len() < k.phimuemue commentedon Dec 17, 2021
I guess your problem is that
BinaryHeapdoes not support custom comparison functions by itself (please correct me if I'm wrong) - and I've come to the same conclusion when I once ran into this problem.Copying the sifting logic might be a viable solution (unless it's a huge amount of code). I think we already did something similar (see https://github.com/rust-itertools/itertools/blob/master/src/unziptuple.rs#L42-L46). If you decide to go that route, please add documentation in a similar fashion.
Alextopher commentedon Dec 6, 2022
An alternative solution to #654 would be to use the binary_heap_plus crate which supports custom comparison functions.
One problem is their MSRV is 1.56 compared to Itertool's 1.32. I haven't looked into it but it might be possible to make their crate more backwards compatible.
It would keep the implementations within this crate much smaller. For example (not exactly the same API): https://github.com/Alextopher/advent-of-code-2022/blob/main/aoc/src/iterstuff.rs#L29