Как бы вы отсортировали 1 миллион 32-разрядных целых чисел в 2 МБ ОЗУ?

Question

Пожалуйста, предоставьте примеры кода на выбранном вами языке.

Обновление : Нет ограничений на внешнее хранилище.

Пример: целые числа принимаются / отправляются через сеть. На локальном диске достаточно места для промежуточных результатов.

Answer 1

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

Answer 2

Сортировка миллиона 32-разрядных целых чисел в 2 МБ ОЗУ с использованием Python от Guido van Rossum

Answer 3

Вам необходимо предоставить больше информации. Какое дополнительное хранилище доступно? Где вы должны хранить результат?

В противном случае самый общий ответ: 1. загрузить первую половину данных в память (2 МБ), отсортировать их любым способом, вывести в файл. 2. загрузить вторую половину данных в память (2 МБ), отсортировать ее любым способом, сохранить в памяти. 3. используйте алгоритм объединения, чтобы объединить две отсортированные половины и вывести полный отсортированный набор данных в файл.

Answer 4

1 миллион 32-разрядных целых = 4 МБ памяти.

Вы должны отсортировать их, используя некоторый алгоритм, который использует внешнее хранилище. Mergesort, например.

Answer 5

Эта статья в Википедии о внешней сортировке содержит некоторую полезную информацию.

Answer 6

Двойная сортировка турнира с многофазным слиянием

#!/usr/bin/env python
import random
from sort import Pickle, Polyphase


nrecords = 1000000
available_memory = 2000000 # number of bytes
    #NOTE: it doesn't count memory required by Python interpreter 

record_size = 24 # (20 + 4) number of bytes per element in a Python list
heap_size = available_memory / record_size 
p = Polyphase(compare=lambda x,y: cmp(y, x), # descending order
              file_maker=Pickle, 
              verbose=True,
              heap_size=heap_size,
              max_files=4 * (nrecords / heap_size + 1))

# put records
maxel = 1000000000
for _ in xrange(nrecords):
    p.put(random.randrange(maxel))

# get sorted records
last = maxel
for n, el in enumerate(p.get_all()):
    if el > last: # elements must be in descending order
        print "not sorted %d: %d %d" % (n, el ,last)
        break
    last = el

assert nrecords == (n + 1) # check all records read

Answer 7

Вот правильное и забавное решение.

Загрузка половины чисел в память. Куча сортирует их по месту и записывает вывод в файл. Повторите для другой половины. Используйте внешнюю сортировку (в основном сортировку слиянием, которая учитывает файловый ввод / вывод) для объединения двух файлов.

Кроме: Ускорьте сортировку кучи перед лицом медленного внешнего хранилища:

• Начните строить кучу до того, как все целые числа будут в памяти.

• Начните помещать целые числа обратно в выходной файл, пока сортировка кучи все еще извлекает элементы

Answer 8

• Хм, сохраните их все в файле.
• Карта памяти файла (вы сказали, что было только 2M ОЗУ; давайте предположим, что адресное пространство достаточно велико для карты памяти файла).
• Сортируйте их, используя хранилище файлов, как если бы это была настоящая память!

Answer 9

Нет примера, но Bucket Sort имеет относительно низкую сложность и достаточно прост для реализации

Answer 10

Как уже упоминалось выше, тип int 32-битный 4 МБ.

Чтобы разместить как можно больше "Number" на как можно меньшем пространстве, используя типы int, short и char в C ++. Вы можете быть ловким (но иметь странный грязный код), выполнив несколько типов приведения, чтобы наполнить вещи повсюду.

Вот оно с края моего места.

все, что меньше 2 ^ 8 (0 - 255), сохраняется как символ (тип данных 1 байт)

все, что меньше 2 ^ 16 (256 - 65535) и> 2 ^ 8, сохраняется как короткий (тип данных 2 байта)

Остальные значения будут помещены в int. (Тип данных 4 байта)

Вы хотите указать, где начинается и заканчивается раздел char, где начинается и заканчивается короткий раздел, а также где начинается и заканчивается раздел int.