Как бы вы отсортировали 1 миллион 32-разрядных целых чисел в 2 МБ ОЗУ?
Пожалуйста, предоставьте примеры кода на выбранном вами языке.
Обновление: не установлены ограничения на внешнее хранилище.
Пример: целые числа принимаются / отправляются через сеть. На локальном диске достаточно места для промежуточных результатов.
10 ответов
Разделите задачу на части, достаточно маленькие, чтобы поместиться в доступную память, а затем используйте сортировку слиянием, чтобы объединить их.
Вам необходимо предоставить больше информации. Какое дополнительное хранилище доступно? Где вы должны хранить результат?
В противном случае самый общий ответ: 1. загрузить первую половину данных в память (2 МБ), отсортировать их любым способом, вывести в файл. 2. загрузить вторую половину данных в память (2 МБ), отсортировать ее любым способом, сохранить в памяти. 3. использовать алгоритм объединения, чтобы объединить две отсортированные половины и вывести весь отсортированный набор данных в файл.
1 миллион 32-разрядных целых = 4 МБ памяти.
Вы должны отсортировать их, используя некоторый алгоритм, который использует внешнее хранилище. Mergesort, например.
Эта статья в Википедии о внешней сортировке содержит полезную информацию.
Двойная турнирная сортировка с многофазным слиянием
#!/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
- Хм, храните их все в файле.
- Карта памяти файла (вы сказали, что было только 2M RAM; давайте предположим, что адресное пространство достаточно велико для карты памяти файла).
- Сортируйте их, используя хранилище файлов, как будто это настоящая память!
Вот правильное и забавное решение.
Загрузите половину чисел в память. Куча сортирует их по месту и записывает вывод в файл. Повторите для другой половины. Используйте внешнюю сортировку (в основном сортировку слиянием, которая учитывает файловый ввод / вывод) для объединения двух файлов.
В сторону: ускорение сортировки кучи в условиях медленного внешнего хранилища:
Начните строить кучу до того, как все целые будут в памяти.
Начните помещать целые числа обратно в выходной файл, пока сортировка кучи все еще извлекает элементы
В качестве людей выше упоминают тип int 32-битные 4 МБ.
Чтобы разместить как можно больше "Number" на как можно меньшем пространстве, используя типы int, short и char в C++. Вы можете быть ловким (но иметь странный грязный код), выполнив несколько типов приведения, чтобы наполнить вещи повсюду.
Вот оно с края моего места.
все, что меньше 2^8(0 - 255), сохраняется как символ (тип данных 1 байт)
все, что меньше 2^16(256 - 65535) и> 2^8, сохраняется как короткий (тип данных 2 байта)
Остальные значения будут помещены в int. (Тип данных 4 байта)
Вы хотите указать, где начинается и заканчивается раздел char, где начинается и заканчивается короткий раздел, а где начинается и заканчивается раздел int.
Нет примера, но Bucket Sort имеет относительно низкую сложность и достаточно прост в реализации.