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

Ответ 1

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

Ответ 2

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

Ответ 3

1 миллион 32-битных целых чисел = 4 МБ памяти.

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

Ответ 4

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

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

Ответ 5

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

Ответ 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

Ответ 7

• Um, сохраните их все в файле.
• Память сопоставляет файл (вы сказали, что всего 2 М ОЗУ, допустим, что адресное пространство достаточно велико, чтобы карта памяти отображала файл).
• Отсортируйте их с помощью хранилища файлов, как если бы это была настоящая память!

Ответ 8

Здесь действительное и веселое решение.

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

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

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

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

Ответ 9

Как упоминают выше люди типа int 32bit 4 MB.

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

Здесь он находится у края моего места.

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

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

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

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

Ответ 10

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