Как отсортировать итератор, не помещая все это в вектор?

Question

Я создаю общий интерфейс, похожий на генераторы, которые передают данные из потока в другой, чтобы в конечном итоге сделать что-то вроде:

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

Буквально невозможно отсортировать набор значений без , имеющего все данные.Например, если у итератора 1 миллиард экземпляров 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.

Теоретически возможно написать адаптер итератора, который записывает все данные на диск,выполняет там сортировку, затем перечитывает данные с диска.Это называется внешняя сортировка .