Repository: rust-itertools/itertools
Pull request #925 (2024-04-27 11:26:58)

Add k_smallest_relaxed and variants
This implements the algorithm described [in](https://quickwit.io/blog/top-k-complexity) which consumes twice the amount of memory as the existing `k_smallest` algorithm but achieves linear time in the number of elements in the input.

I expect this to fail the MSRV job as `select_nth_unstable` was stabilized in 1.49 and is therefore not available in 1.43.1. I decided to propose it anyway for the time when an MSRV increase is planned or if deemed sufficiently useful as reason for one.

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/rust-itertools/itertools/pull/925?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 94.66%. Comparing base [(`6814180`)](https://app.codecov.io/gh/rust-itertools/itertools/commit/68141809aabec2816d3250820c8d6608f3b2293f?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) to head [(`19747d1`)](https://app.codecov.io/gh/rust-itertools/itertools/pull/925?dropdown=coverage&src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).
> Report is 63 commits behind head on master.


<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##           master     #925      +/-   ##
==========================================
+ Coverage   94.38%   94.66%   +0.27%     
==========================================
  Files          48       48              
  Lines        6665     7048     +383     
==========================================
+ Hits         6291     6672     +381     
- Misses        374      376       +2     
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/rust-itertools/itertools/pull/925?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).

adamreichold: > I note that we would have 12 methods... k_(smallest|largest)[_relaxed][_by[_key]] which is a lot!

I agree and if pressed to make a choice, I would argue that the relaxed would be a reasonable general choice, i.e. could completely replace the heap-based versions.

For one, `k` usually is bounded by small fixed numbers and I do not really see a lot of situations where I have the memory to compute the top 100 but not the enough to invest into the top 200. And since the implementation can directly work with `select_nth_unstable_by`, the complications of having a custom heap implementation could be avoided.

However, making this choice does not appear obviously better than having twelve methods though.

Alternatively, the combinatorics could be reigned in by adding a "strategy-like" type parameter, e.g. `Strict` and `Relaxed` to indicate the desired memory bound.

Finally, I am not sure the `k_largest*` methods really carry their weight now that the `k_smallest_by` and `k_smallest_by_key` methods exist as in applications of these methods that I am aware of, adapting the way items are sorted in required in any case and hence choosing ascending or descending order does not really increase call site complexity.
Philippe-Cholet: @phimuemue @jswrenn I don't know if you would agree on the current PR but have 12 similar methods seems a bit much to me. `k_smallest` variants are in itertools 0.13.0 which is _not released yet_, so we could still change some things without breaking and avoid the 12 methods. We could have

    iter.top_k(k).smallest() // redirected from the current k_smallest (that we could deprecate)
    iter.top_k(k).smallest_by(f)
    iter.top_k(k).smallest_by_key(key)
    iter.top_k(k).largest()
    iter.top_k(k).largest_by(f)
    iter.top_k(k).largest_by_key(key)
    And once MSRV >= 1.49, this PR would introduce:
    iter.top_k(k).relaxed().smallest()
    iter.top_k(k).relaxed().smallest_by(f)
    iter.top_k(k).relaxed().smallest_by_key(key)
    iter.top_k(k).relaxed().largest()
    iter.top_k(k).relaxed().largest_by(f)
    iter.top_k(k).relaxed().largest_by_key(key)

<details><summary>Implementation draft (click to see)</summary>

```rust
trait Itertools: Iterator {
    fn top_k(self, k: usize) -> Top<Self> { ... }
    #[deprecate...]
    fn k_smallest(self, k: usize) -> ... { self.top_k().smallest() }
}

pub struct GeneralTop<I, A> {
    iter: I,
    k: usize,
    marker: PhantomData<A>,
}
pub type Top<I> = GeneralTop<I, Unrelaxed>;
pub type TopRelaxed<I> = GeneralTop<I, Relaxed>;

impl<I: Iterator> Top<I> {
    pub fn relaxed(self) -> TopRelaxed<I> { ... }
}
impl<I: Iterator, A> GeneralTop<I, A> {
    pub fn smallest(self) -> ...
    pub fn smallest_by<F: FnMut...>(self, f: F) -> ...
    pub fn smallest_by_key<F: FnMut...>(self, key: F) -> ...
    pub fn largest(self) -> ...
    pub fn largest_by<F: FnMut...>(self, f: F) -> ...
    pub fn largest_by_key<F: FnMut...>(self, key: F) -> ...
}
```
The relaxed version would be added once the MSRV is big enough.
</details>

"Minimal allocation" vs "linear complexity" are both valuable tradeoffs here, but maybe it would be nice to not multiply methods.
adamreichold: Looking at the results of the benchmark pushed as part of the second commit, I would summarize them as no difference for the ascending/best case

![grafik](https://github.com/rust-itertools/itertools/assets/12997846/feaafb52-5e97-4170-bd5b-7c5d690b0ecf)

a small but consistent lead in the random/average case

![grafik](https://github.com/rust-itertools/itertools/assets/12997846/409a82eb-0390-4802-bfa8-737c7a7de324)

and a large improvement for the descending/worst case

![grafik](https://github.com/rust-itertools/itertools/assets/12997846/1a9a8483-0b38-4fa5-ac45-0091885a2eb2)

phimuemue: Hi there, nice algorithm. Unsure about what to do best. And the algorithm begs the question of the scaling factor: Could a capacity of 3*k or 4*k even be more performant?

As for the 12 methods. I think that - if we decide to keep all of them - we should just offer 12 methods right on `Itertools`. I still feel the same for our grouping_map thing: It adds an indirection, and - from what I've seen so far - does not help in composability or reusability (see our trials to extend it to custom hashers). Sure, it occupies lots of space in docs.rs, but I do not see a real problem with that.
adamreichold: > Sidenote: What's the unstable/stable behavior of the current implementation?

It is unstable, at least because it calls into the unstable selection/sorting routines from `std`.
adamreichold: > And the algorithm begs the question of the scaling factor: Could a capacity of 3k or 4k even be more performant?

The [original issue](https://github.com/quickwit-oss/tantivy/issues/298#issue-322365190) and I think I agree with the assessment there: Further increasing the capacity is not too interesting as it will only change the constant factor attached to the `O(n)` part of the runtime, i.e. I don't think it is worth it complicating the API by giving this choice to the calling code.
Philippe-Cholet: Ok about having 12 methods. The scaling factor 2 is fine.

TODO:
- Close this OR add this as an alternative OR replace our heap-based versions with it.
  Personally I would choose to keep this as an alternative as both tradeoffs are valuable enough?
- A bit unsure about the name: change "relaxed"?
  OR should we make the relaxed versions the default and the heap-based ones the ones with a longer name instead? It might be a better choice perf-wise but do so would be a breaking change IMHO.
- Review docs.
- Wait a bit for MSRV>=1.49 to merge this.

adamreichold: > A bit unsure about the name: change "relaxed"?

Note that I am very much _not_ invested in that name and made it up on the spot when I had to name the methods somehow to avoid conflicting with the existing ones. I think the only requirement for the name is that they should reflect the space-time trade-off somehow.
Philippe-Cholet: @adamreichold The long wait has ended, thanks again for this!

Patch:
diff --git a/Cargo.toml b/Cargo.toml
index 8006146..6ec88a9 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -27,7 +27,7 @@ either = { version = "1.0", default-features = false }
 
 [dev-dependencies]
 rand = "0.7"
-criterion = "0.4.0"
+criterion = { version = "0.4.0", features = ["html_reports"] }
 paste = "1.0.0"  # Used in test_std to instantiate generic tests
 permutohedron = "0.2"
 quickcheck = { version = "0.9", default_features = false }
@@ -75,3 +75,7 @@ harness = false
 [[bench]]
 name = "specializations"
 harness = false
+
+[[bench]]
+name = "k_smallest"
+harness = false
diff --git a/benches/k_smallest.rs b/benches/k_smallest.rs
new file mode 100644
index 0000000..509ed7f
--- /dev/null
+++ b/benches/k_smallest.rs
@@ -0,0 +1,61 @@
+use criterion::{black_box, criterion_group, criterion_main, Bencher, BenchmarkId, Criterion};
+use itertools::Itertools;
+use rand::{rngs::StdRng, seq::SliceRandom, SeedableRng};
+
+fn strict(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) {
+    b.iter(|| black_box(vals.iter()).k_smallest(*k))
+}
+
+fn relaxed(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) {
+    b.iter(|| black_box(vals.iter()).k_smallest_relaxed(*k))
+}
+
+fn ascending(n: usize) -> Vec<usize> {
+    (0..n).collect()
+}
+
+fn random(n: usize) -> Vec<usize> {
+    let mut vals = (0..n).collect_vec();
+    vals.shuffle(&mut StdRng::seed_from_u64(42));
+    vals
+}
+
+fn descending(n: usize) -> Vec<usize> {
+    (0..n).rev().collect()
+}
+
+fn k_smallest(c: &mut Criterion, order: &str, vals: fn(usize) -> Vec<usize>) {
+    let mut g = c.benchmark_group(format!("k-smallest/{order}"));
+
+    for log_n in 20..23 {
+        let n = 1 << log_n;
+
+        let vals = vals(n);
+
+        for log_k in 7..10 {
+            let k = 1 << log_k;
+
+            let params = format!("{log_n}/{log_k}");
+            let input = (k, &vals);
+            g.bench_with_input(BenchmarkId::new("strict", &params), &input, strict);
+            g.bench_with_input(BenchmarkId::new("relaxed", &params), &input, relaxed);
+        }
+    }
+
+    g.finish()
+}
+
+fn k_smallest_asc(c: &mut Criterion) {
+    k_smallest(c, "asc", ascending);
+}
+
+fn k_smallest_rand(c: &mut Criterion) {
+    k_smallest(c, "rand", random);
+}
+
+fn k_smallest_desc(c: &mut Criterion) {
+    k_smallest(c, "desc", descending);
+}
+
+criterion_group!(benches, k_smallest_asc, k_smallest_rand, k_smallest_desc);
+criterion_main!(benches);
diff --git a/src/k_smallest.rs b/src/k_smallest.rs
index 7b2f62e..7e4ace2 100644
--- a/src/k_smallest.rs
+++ b/src/k_smallest.rs
@@ -88,6 +88,46 @@ where
     storage
 }
 
+pub(crate) fn k_smallest_relaxed_general<I, F>(iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
+where
+    I: Iterator,
+    F: FnMut(&I::Item, &I::Item) -> Ordering,
+{
+    if k == 0 {
+        iter.last();
+        return Vec::new();
+    }
+
+    let mut iter = iter.fuse();
+    let mut buf = iter.by_ref().take(2 * k).collect::<Vec<_>>();
+
+    if buf.len() < k {
+        buf.sort_unstable_by(&mut comparator);
+        return buf;
+    }
+
+    buf.select_nth_unstable_by(k - 1, &mut comparator);
+    buf.truncate(k);
+
+    iter.for_each(|val| {
+        if comparator(&val, &buf[k - 1]) != Ordering::Less {
+            return;
+        }
+
+        assert_ne!(buf.len(), buf.capacity());
+        buf.push(val);
+
+        if buf.len() == 2 * k {
+            buf.select_nth_unstable_by(k - 1, &mut comparator);
+            buf.truncate(k);
+        }
+    });
+
+    buf.sort_unstable_by(&mut comparator);
+    buf.truncate(k);
+    buf
+}
+
 #[inline]
 pub(crate) fn key_to_cmp<T, K, F>(mut key: F) -> impl FnMut(&T, &T) -> Ordering
 where
diff --git a/src/lib.rs b/src/lib.rs
index b98e03f..10abe96 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -3153,6 +3153,105 @@ pub trait Itertools: Iterator {
         self.k_smallest_by(k, k_smallest::key_to_cmp(key))
     }
 
+    /// Sort the k smallest elements into a new iterator, in ascending order, relaxing the amount of memory required.
+    ///
+    /// **Note:** This consumes the entire iterator, and returns the result
+    /// as a new iterator that owns its elements.  If the input contains
+    /// less than k elements, the result is equivalent to `self.sorted()`.
+    ///
+    /// This is guaranteed to use `2 * k * sizeof(Self::Item) + O(1)` memory
+    /// and `O(n + k log k)` time, with `n` the number of elements in the input,
+    /// meaning it uses more memory than the minimum obtained by [`k_smallest`](Itertools::k_smallest)
+    /// but achieves linear time in the number of elements.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// **Note:** This is functionally-equivalent to `self.sorted().take(k)`
+    /// but much more efficient.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_smallest = numbers
+    ///     .into_iter()
+    ///     .k_smallest_relaxed(5);
+    ///
+    /// itertools::assert_equal(five_smallest, 0..5);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_smallest_relaxed(self, k: usize) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        Self::Item: Ord,
+    {
+        self.k_smallest_relaxed_by(k, Ord::cmp)
+    }
+
+    /// Sort the k smallest elements into a new iterator using the provided comparison, relaxing the amount of memory required.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// This corresponds to `self.sorted_by(cmp).take(k)` in the same way that
+    /// [`k_smallest_relaxed`](Itertools::k_smallest_relaxed) corresponds to `self.sorted().take(k)`,
+    /// in both semantics and complexity.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_smallest = numbers
+    ///     .into_iter()
+    ///     .k_smallest_relaxed_by(5, |a, b| (a % 7).cmp(&(b % 7)).then(a.cmp(b)));
+    ///
+    /// itertools::assert_equal(five_smallest, vec![0, 7, 14, 1, 8]);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_smallest_relaxed_by<F>(self, k: usize, cmp: F) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        k_smallest::k_smallest_relaxed_general(self, k, cmp).into_iter()
+    }
+
+    /// Return the elements producing the k smallest outputs of the provided function, relaxing the amount of memory required.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// This corresponds to `self.sorted_by_key(key).take(k)` in the same way that
+    /// [`k_smallest_relaxed`](Itertools::k_smallest_relaxed) corresponds to `self.sorted().take(k)`,
+    /// in both semantics and complexity.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_smallest = numbers
+    ///     .into_iter()
+    ///     .k_smallest_relaxed_by_key(5, |n| (n % 7, *n));
+    ///
+    /// itertools::assert_equal(five_smallest, vec![0, 7, 14, 1, 8]);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_smallest_relaxed_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        F: FnMut(&Self::Item) -> K,
+        K: Ord,
+    {
+        self.k_smallest_relaxed_by(k, k_smallest::key_to_cmp(key))
+    }
+
     /// Sort the k largest elements into a new iterator, in descending order.
     ///
     /// The sorted iterator, if directly collected to a `Vec`, is converted
@@ -3243,6 +3342,94 @@ pub trait Itertools: Iterator {
         self.k_largest_by(k, k_smallest::key_to_cmp(key))
     }
 
+    /// Sort the k largest elements into a new iterator, in descending order, relaxing the amount of memory required.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// It is semantically equivalent to [`k_smallest_relaxed`](Itertools::k_smallest_relaxed)
+    /// with a reversed `Ord`.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_largest = numbers
+    ///     .into_iter()
+    ///     .k_largest_relaxed(5);
+    ///
+    /// itertools::assert_equal(five_largest, vec![14, 13, 12, 11, 10]);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_largest_relaxed(self, k: usize) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        Self::Item: Ord,
+    {
+        self.k_largest_relaxed_by(k, Self::Item::cmp)
+    }
+
+    /// Sort the k largest elements into a new iterator using the provided comparison, relaxing the amount of memory required.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// Functionally equivalent to [`k_smallest_relaxed_by`](Itertools::k_smallest_relaxed_by)
+    /// with a reversed `Ord`.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_largest = numbers
+    ///     .into_iter()
+    ///     .k_largest_relaxed_by(5, |a, b| (a % 7).cmp(&(b % 7)).then(a.cmp(b)));
+    ///
+    /// itertools::assert_equal(five_largest, vec![13, 6, 12, 5, 11]);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_largest_relaxed_by<F>(self, k: usize, mut cmp: F) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+    {
+        self.k_smallest_relaxed_by(k, move |a, b| cmp(b, a))
+    }
+
+    /// Return the elements producing the k largest outputs of the provided function, relaxing the amount of memory required.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// Functionally equivalent to [`k_smallest_relaxed_by_key`](Itertools::k_smallest_relaxed_by_key)
+    /// with a reversed `Ord`.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // A random permutation of 0..15
+    /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+    ///
+    /// let five_largest = numbers
+    ///     .into_iter()
+    ///     .k_largest_relaxed_by_key(5, |n| (n % 7, *n));
+    ///
+    /// itertools::assert_equal(five_largest, vec![13, 6, 12, 5, 11]);
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn k_largest_relaxed_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        F: FnMut(&Self::Item) -> K,
+        K: Ord,
+    {
+        self.k_largest_relaxed_by(k, k_smallest::key_to_cmp(key))
+    }
+
     /// Consumes the iterator and return an iterator of the last `n` elements.
     ///
     /// The iterator, if directly collected to a `VecDeque`, is converted


Test patch:
diff --git a/tests/test_std.rs b/tests/test_std.rs
index f626a17..ad391fa 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -528,6 +528,42 @@ qc::quickcheck! {
         it::assert_equal(largest_by, sorted_largest.clone());
         it::assert_equal(largest_by_key, sorted_largest);
     }
+
+    fn k_smallest_relaxed_range(n: i64, m: u16, k: u16) -> () {
+        // u16 is used to constrain k and m to 0..2¹⁶,
+        //  otherwise the test could use too much memory.
+        let (k, m) = (k as usize, m as u64);
+
+        let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
+        // Generate a random permutation of n..n+m
+        v.shuffle(&mut thread_rng());
+
+        // Construct the right answers for the top and bottom elements
+        let mut sorted = v.clone();
+        sorted.sort();
+        // how many elements are we checking
+        let num_elements = min(k, m as _);
+
+        // Compute the top and bottom k in various combinations
+        let sorted_smallest = sorted[..num_elements].iter().cloned();
+        let smallest = v.iter().cloned().k_smallest_relaxed(k);
+        let smallest_by = v.iter().cloned().k_smallest_relaxed_by(k, Ord::cmp);
+        let smallest_by_key = v.iter().cloned().k_smallest_relaxed_by_key(k, |&x| x);
+
+        let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
+        let largest = v.iter().cloned().k_largest_relaxed(k);
+        let largest_by = v.iter().cloned().k_largest_relaxed_by(k, Ord::cmp);
+        let largest_by_key = v.iter().cloned().k_largest_relaxed_by_key(k, |&x| x);
+
+        // Check the variations produce the same answers and that they're right
+        it::assert_equal(smallest, sorted_smallest.clone());
+        it::assert_equal(smallest_by, sorted_smallest.clone());
+        it::assert_equal(smallest_by_key, sorted_smallest);
+
+        it::assert_equal(largest, sorted_largest.clone());
+        it::assert_equal(largest_by, sorted_largest.clone());
+        it::assert_equal(largest_by_key, sorted_largest);
+    }
 }
 
 #[derive(Clone, Debug)]
@@ -572,8 +608,11 @@ where
     I::Item: Ord + Debug,
 {
     let j = i.clone();
+    let i1 = i.clone();
+    let j1 = i.clone();
     let k = k as usize;
-    it::assert_equal(i.k_smallest(k), j.sorted().take(k))
+    it::assert_equal(i.k_smallest(k), j.sorted().take(k));
+    it::assert_equal(i1.k_smallest_relaxed(k), j1.sorted().take(k));
 }
 
 // Similar to `k_smallest_sort` but for our custom heap implementation.
@@ -583,8 +622,11 @@ where
     I::Item: Ord + Debug,
 {
     let j = i.clone();
+    let i1 = i.clone();
+    let j1 = i.clone();
     let k = k as usize;
-    it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k))
+    it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k));
+    it::assert_equal(i1.k_smallest_relaxed_by(k, Ord::cmp), j1.sorted().take(k));
 }
 
 macro_rules! generic_test {