Как бы вы отсортировали 1 миллион 32-битных целых чисел в 2 МБ оперативной памяти?

StackOverflow https://stackoverflow.com/questions/134158

Вопрос

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

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

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

Другие советы

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

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.

Примера нет, но Сортировка по Ведру обладает относительно низкой сложностью и достаточно прост в реализации

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top