问题

假设你正在对一个非常大的搜索空间进行暴力搜索，但想保留不仅仅是单个最佳项目 - 例如，你希望从十亿个选项中找到最佳的前 100 个项目。

即你想实现以下函数

fn get_best<T: Ord>(
    big_computation: impl Iterator<Item = T>,
    n: usize
) -> Vec<T> {
    // Somehow get the `n` largest items produced by `big_computation` ...
}

一个糟糕的解决方案

对此的直观方法是存储我们搜索的每个项目。然后一旦搜索完成，对这个列表进行排序，然后从列表的末尾取我们需要的任何数量的项目。这大致对应以下代码

fn get_best<T: Ord>(
    big_computation: impl Iterator<Item = T>,
    n: usize
) -> Vec<T> {
    // Collect all the results into a big sorted vec
    let mut giant_vec: Vec<T> = big_computation.collect();
    giant_vec.sort();
    // Return the last and therefore biggest n items with some iterator magic
    giant_vec.drain(..).rev().take(n).rev().collect()
}

但这在两个方面都非常低效

• 对非常大的列表进行排序非常慢，而且我们正在对可能永远不会需要的数十亿个项目进行排序。
• 对于任何相当大的搜索空间，存储这些项目可能会使计算机崩溃，因为它会耗尽内存。

此 crate 使用的解决方案

这就是使用 Shortlist 有用的地方。

Shortlist 是一种数据结构，它将动态保持迄今为止给定的最佳项目的“短名单”，每次推送新项目的时间平均为 O(1)。它也只会在创建 Shortlist 时执行一次堆分配，并且后续的所有操作都不会进行分配。因此，对于此库的用户，代码变为

use shortlist::Shortlist;

fn get_best<T: Ord>(
    big_computation: impl Iterator<Item = T>,
    n: usize
) -> Vec<T> {
    // Create a new Shortlist that will take at most `n` items
    let mut shortlist = Shortlist::new(n);
    // Feed it all the results from `big_computation`
    for v in big_computation {
        shortlist.push(v);
    }
    // Return the shortlisted values as a sorted vec
    shortlist.into_sorted_vec()
}

use shortlist::Shortlist;

fn get_best<T: Ord>(big_computation: impl Iterator<Item = T>, n: usize) -> Vec<T> {
    Shortlist::from_iter(n, big_computation).into_sorted_vec()
}