sorting - 如何在不将迭代器全部放入向量中的情况下对迭代器进行排序？

Question

我正在构建一个类似于生成器的通用接口(interface)，将数据从一个流传输到另一个流，最终执行如下操作:

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

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

stream.iter().collect_sorted()

我需要融合向量、树、文件、数据库等，所以有时我不知道传入的数据有多大而不用全部消耗掉。

我不反对存储结果。问题是排序与切片/向量相关联。我需要能够做到:

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

代替:

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

针对不同的用例存在不同的排序算法，所以最终我希望对手头的数据应用最好的算法:

datasource |> Algo.MergeSort |> next...
datasource |> Algo.BubbleSort |> next...

Answer 1

在没有所有数据的情况下要对一组值进行排序实际上是不可能的。例如，如果迭代器有 10 亿个 1 实例，后面跟着一个 0，那么在到达那里之前，您根本不知道零需要先走。您可能希望重新认识 on- and offline algorithms 的概念.

without putting it all in a vector

这很简单:不要使用向量，使用任何实现了 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);
    }
}

This is a common problem with databases, where is not wise to load all the data then sort

数据库是非常复杂的软件，考虑到仔细权衡的权衡，我们付出了多年的努力。您不会在包管理器中找到那种级别的算法。即使可以，数据库也不总是正确的，需要熟练的程序员调整查询以更好地执行。 All you need to know about sorting in Postgres涵盖了 Postgres 的一系列功能。

理论上应该可以编写一个迭代器适配器，将所有数据写入磁盘，在那里执行排序，然后从磁盘重新读取数据。这叫做 external sorting .