如何对迭代器排序而不将其全部放入向量中？

Question

我正在构建一个类似于生成器的通用接口，该生成器将数据从一个流传输到另一个流，以最终完成以下操作：

file |> toCsv |> filter |> sort |> filter...

我知道如何对向量/片段进行排序，但是如何将传入的流/迭代器排序而不将其全部放入向量中？

stream.iter().collect_sorted()

我需要融合向量，树，文件，数据库等，因此有时我不知道全部消耗不知道传入数据的大小。

我不反对存储结果。问题是排序与切片/向量有关。我需要能够：

stream.iter().collect_sorted()

代替：

datasource |> Algo.sort |> next...

针对不同的用例存在不同的排序算法，因此最终我希望对现有数据应用最好的排序方法：

let data = datasource |> into_vec
data.sort()
data |> next...

Answer 1

在没有所有数据的情况下，实际上不可能对一组值进行排序。例如，如果迭代器有10亿个实例，1后跟一个0，则您根本不知道要先到达零才需要。您可能希望重新熟悉在线和离线算法的概念。

而不是全部放在向量中

这很容易：不要使用向量，请使用任何实现的类型FromIterator。例如，您可以收集到BinaryHeap：

use std::{collections::BinaryHeap, iter};

fn main() {
    let a_lot_of_numbers = iter::repeat(1).take(100).chain(iter::once(0));
    let data: BinaryHeap<_> = a_lot_of_numbers.collect();
}

这是否一个好主意完全取决于您的情况。

如果您只是不想看到向量，或者只是想保留链接，则建议使用Itertools::sorted。这在Vec内部使用，这意味着在返回第一个值之前，所有数据都存储在内存中：

use itertools::Itertools; // 0.8.0
use std::iter;

fn main() {
    let a_lot_of_numbers = iter::repeat(1).take(100).chain(iter::once(0));

    for v in a_lot_of_numbers.sorted() {
        println!("{}", v);
    }
}

这是数据库的常见问题，在其中装载所有数据然后进行排序是不明智的

考虑到折衷的权衡，数据库是非常复杂的软件，需要花费多年的精力。您不会在包管理器中找到这种级别的算法。即使您可以，数据库也不一定总是正确无误，这要求熟练的程序员调整查询以使其性能更好。您需要在Postgres中进行排序的所有知识，涵盖了Postgres可以完成的一系列工作。

从理论上讲，应该有可能编写一个迭代器适配器，该适配器将所有数据写入磁盘，在磁盘上进行排序，然后从磁盘重新读取数据。这称为外部排序。