Есть ли алгоритмы для сортировки данных с последовательного ввода с использованием буфера, который меньше длины данных?Сортировка последовательных данных с буфером
Например, у меня есть 100 байтов последовательных данных, которые могут быть прочитаны только один раз и 40-байтовый буфер. И мне нужно распечатать отсортированные байты.
Мне это нужно в Javascript, но любые общие идеи оцениваются.
Этот вид сортировки невозможен за один проход.
Использование вашего примера: предположим, что вы заполнили свой 40-байтовый буфер, поэтому вам нужно начать печатать байты, чтобы освободить место для следующего. Чтобы распечатать отсортированные данные, сначала нужно напечатать наименьший байт. Однако, если самый маленький байт не был прочитан, вы еще не можете его распечатать!
Ближайшие релевантные по вашему вопросу могут быть external sorting алгоритмами, которые принимают несколько проходов для сортировки данных, которые не могут вписаться в память. То есть, если у вас есть периферийные устройства, которые могут хранить вывод обработки, вы можете сортировать данные, большие, чем ваша память, в O (log (N/M)), где N - размер проблемы, а M - размер вашей памяти.
Классическое периферийное устройство хранения для внешней сортировки - это стример; однако одни и те же алгоритмы работают на дисках (любого типа). Кроме того, по мере углубления иерархии кеша принципы внешней сортировки становятся более актуальными даже для сортировки в памяти - попробуйте взглянуть на алгоритмы cache-oblivious.
Я вполне уверен, что это невозможно, если данные предварительно заказаны, по крайней мере, в некоторой степени. Если последний байт, который вы получаете, должен быть первым в выводе, вы * не можете * вывести все байты перед ним и все еще сначала выходить, но вы не можете сохранить все промежуточные данные в буфере, меньшем, чем это данные занимают. Вы можете попробовать что-то вроде сжатия данных, но это может иметь неприятные последствия и сделать его более крупным. –