Алгоритм поиска / сортировки диска

Question

Учитывая диапазон чисел, скажем, от 1 до 10000, ввод в случайном порядке. Ограничение: В любой момент в память можно загрузить только 1000 номеров.

Предположение: Предполагая уникальные числа.

Я предлагаю следующий эффективный «алгоритм сортировки по требованию».

Мы записываем числа в файлы, предназначенные для хранения определенного диапазона чисел. Например, File1 будет иметь 0 - 999, File2 будет иметь 1000 - 1999 и т. Д. В случайном порядке.

Если ищется конкретное число, например «2535», то мы знаем, что это число в файле3 (бинарный поиск по диапазону, чтобы найти файл). Затем файл 3 загружается в память и сортируется с помощью, скажем, быстрой сортировки (которая оптимизирована для добавления сортировки вставкой, когда размер массива небольшой), а затем мы ищем число в этом отсортированном массиве с помощью бинарного поиска. И когда поиск будет завершен, мы запишем отсортированный файл.

Таким образом, в конечном итоге все числа будут отсортированы.

Пожалуйста, прокомментируйте это предложение.

Answer 1

Это называется Сортировка ведра .

Другим подходом, когда основная память ограничена, является использование Сортировка слиянием .

Часть вашего проекта, в которой вы сортируете каждое ведро по требованию, может быть лучше описана как «по требованию», «точно в срок» или «ленивый». Также можно повторно использовать номенклатуру, с которой люди уже знакомы, вместо того, чтобы придумывать термин «когда требуется - сортировка».

Рассматривали ли вы, как обрабатывать дополнительный ввод? Что произойдет, если некоторые сегменты уже отсортированы, а затем добавлено больше чисел?

Я предполагаю, что конечная цель - определить, включено ли число в набор, а не создать отсортированный список. Если вы будете делать это часто, начальные затраты на сортировку сегмента будут полезны. В редких случаях может быть достаточно линейного сканирования соответствующего сегмента.

Еще одна альтернатива. Bucket sort можно рассматривать как упрощенную хэш-таблицу. Хеш-функция n/1000. Ожидаются коллизии, поскольку в каждом сегменте может быть хэшировано большое количество значений (до 1000). Вместо того, чтобы использовать сортировку по требованию (а затем двоичный поиск) для разрешения коллизий, вы можете использовать более сложный хеш и получить O (1) производительность поиска.

Answer 2

Каждое число может быть от 1 до 10000. Это означает, что каждое число занимает не менее 14 бит (2 ¹³ = 8192, 2 ¹⁴ = 16384).

У вас есть возможность загрузить 1000 номеров в память. Это означает, что вы можете использовать битовую маску, поскольку вы заявили, что числа уникальны. Установите битовую маску из 10000 бит, которая при 14 битах на число составляет всего 715 цифр (самое большее, меньше, если у вас больше 14 бит на число).

Сначала очистите биты, чтобы указать, что числа не существуют, затем прочитайте числа по одному, установив соответствующий бит, чтобы указать, что он существует. Это операция O (n).

Затем, когда вы настроили этот битовый массив, это операция O (1), чтобы посмотреть, установлен ли конкретный бит.

Даже самый лучший алгоритм сортировки не даст вам лучше, чем O (n) для случайных данных.

Answer 3

Правильное описание предыдущего постера - это сортировка ведра.

Некоторые близкородственные сорта - сорта Radix. Это O (1), но зависит от довольно равномерного распределения значений в пределах диапазона.

Answer 4

Я прочитал вам вопрос, как это «Учитывая ввод n чисел из домена D, какой самый быстрый способ записать отсортированный ввод этих n чисел, при условии, что вы можете хранить только k чисел (k

Обратите внимание, в своем вопросе вы говорите, что домен D находится в диапазоне от 1 до 10000. Я считаю, что это упрощение. При n = 10000 и вводе в качестве диапазона (без повторений) это становится тривиальным , поскольку вы будете точно знать, где каждое число должно быть записано в отсортированном файле. Кроме того, вы точно знаете, что содержится в этом файле, и вам совсем не нужно его писать, и вам не нужно читать вводные данные. : D

Теперь, если N (D) не равно n или если вы разрешаете повторение, тогда проблема становится немного более интересной.

Если память ограничена, я думаю, что интуитивный подход заключается в следующем:

1-й подход

Считывая ввод, вы сможете отсортировать не более k1 элементов перед тем, как записать их, где k1 - это число элементов, для которого потребуется сортировка k элементов в памяти.

В результате вы получите f = (n div k1) + 1 файлов, которые отсортированы внутри.

Затем вам нужно будет прочитать из f файлов и объединить частично отсортированные данные, записав их в окончательный файл.

Разные сортировки имеют разные требования к памяти и будут производить разное количество частично отсортированных файлов, которые необходимо объединить.

Объединение большего количества файлов потребует больше памяти, потому что вы не будете знать, в каком файле вы можете найти следующий номер.

2-й подход

Другой подход, как вы предлагаете, - узнать, в каком файле вы можете найти следующий номер. Это все равно что складывать их в группы по размеру (распределять сортировку по классификации), но проблема в том, что, если вы не знаете, как распределяются ваши данные, определить диапазон каждого сегмента будет нелегко.

Размер каждого сегмента должен быть снова k1 для наименьшего количества файлов.

Предполагая, что вы знаете что-то о распределении ваших данных, это можно сделать, в противном случае вам потребуется еще один проход по вашим данным, чтобы установить точки отсечения.

Для общих данных, где размер сегмента неизвестен, и вы не можете сначала передать все данные, которые вы (например, если вам нужно сохранить какую-то сортированную структуру для ваших данных, когда ввод поступает, и вы не знаете, что будет дальше) вам, в основном, придется хранить индекс, такой как дерево B +, но это не оптимально. Индексы оптимизированы для быстрого поиска и (некоторые из них) для вставки небольшого количества новых элементов.

3-й подход
Наличие такого небольшого домена позволяет просто считать числа и записывать их частоту. Если вы можете иметь произвольный доступ к выходным файлам, буферизация файловой системы может позаботиться об эффективности (буферизация - это алгоритм, который выполняет эффективную запись на диск, ограниченную использованием памяти, единственная проблема заключается в том, что размер буфера меньше k чисел и если выбранная структура, подобная растровому изображению, является наиболее эффективной).

Интуитивно я бы сказал, что лучше всего было бы сначала рассчитать распределение и рассчитать размер и пределы для каждого сегмента. Затем разделите файл на ведра. Затем сортируйте каждое ведро. Я предполагаю, что некоторую производительность можно снизить, хотя бы частично отсортировав данные при записи их в сегменты.

Answer 5

Использовать сортировку:
http://en.wikipedia.org/wiki/Sorting_algorithm

Потребление памяти для сортировки слиянием равно n, а для сортировки ведра - n * k.
И наихудший случай для сортировки по группам - это n ^ 2 * k, а для сортировки по группам - n * ln (n)

И обратите внимание: почти в любом случае, когда вам нужно отсортировать большое количество чисел, сортировка слиянием является наиболее эффективным алгоритмом сортировки для задачи.