сортировать 1 млрд целых чисел с небольшой физической памятью

Question

Хотите отсортировать 1 млрд целых чисел, и моя система имеет всего 1 ГБ ОЗУ. Какой самый быстрый и эффективный способ сортировки?

1. Скажем, у нас есть вход втекстовый файл целое число в строке.

2. Мы используем программу сортировки Java.

3. Я указал ОЗУ, поскольку мы не можем хранить всевведите целые числа в ОЗУ.

Обновление: Целые числа состоят из 7 цифр.

Answer 1

Целые числа состоят из 7 цифр.

Таким образом, существует только 10 миллионов возможных значений.

У вас 1 ГБ ОЗУ.Создайте массив счетчиков, по одному для каждого возможного значения.

Прочитайте файл один раз, сосчитайте счетчики.

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

Каждое число может встречаться не более 1 миллиарда раз.Так что 32-битного счетчика будет достаточно.Это означает, что массив размером 10M x 4 байта = 40M.

Answer 2

Вы указали, что сортируете миллиардные 7 (десятичные) цифры.

Если бы не было дубликатов, вы могли бы отсортировать в памяти 10 ⁷ БИТОВ, используя радикальную сортировку. Поскольку у вас должны быть дубликаты (10 ⁷ меньше 10 ⁹ ), вы можете реализовать радикальную сортировку, используя, скажем, массив из 10 ⁷ 8-битных счетчиков. с HashMap<Integer, Integer> для решения относительно небольшого числа случаев переполнения счетчиков. Или просто массив из 10 ⁷ 32-битных счетчиков.

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

Answer 3

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

Гвидо ван Россум (Guido van Rossum) хорошо описывает это на python , хотя, очевидно, это не тот же язык, принцип тот же.

Answer 4

Предполагая, что каждое целое число встречается ровно один раз, когда вы можете прочитать файл, и для каждого найденного вами числа вы устанавливаете бит - массив битов должен содержать 10000000 битов - при этом используется только 1,28 МБ ОЗУ, которое должно быть доступно ...после того, как вы прочитали все целые числа, вы просто просматриваете массив и выводите числа, для которых установлен бит ...

Answer 5

Использование BitSet с 4 миллиардами возможных значений занимает 512 МБ. Просто установите все значения int, которые вы видите, и запишите их по порядку (они естественно отсортированы)

Это работает, только если вас не интересуют дубликаты.

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

Недавно я купил компьютер на 24 ГБ менее чем за 1 000 фунтов стерлингов, так что несколько ГБ не так много, если вы не ограничены размещенным решением. (Или с помощью мобильного устройства)