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