如果不将迭代器全部放入向量中，如何对其进行排序？ [英] How can I sort an iterator without putting it all in a vector?

问题描述

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

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...

推荐答案

在没有所有数据的情况下，几乎不可能对一组值进行排序。例如，如果迭代器有10亿个1实例，后跟一个0实例，那么在到达那里之前，您根本不会知道需要先执行0。您可能希望重新熟悉on- and offline algorithms的概念。

不将其全部放入向量

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

这是数据库的常见问题，加载所有数据然后排序是不明智的

数据库是令人惊讶的复杂软件，考虑到仔细权衡的权衡，他们投入了多年的努力。您不会在包管理器中找到那种级别的算法。即使可以，数据库也不总是正确的，需要熟练的程序员调整查询以提高性能。All you need to know about sorting in Postgres很好地介绍了Postgres的功能。

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

这篇关于如果不将迭代器全部放入向量中，如何对其进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！