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

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

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

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

Ответы на вопрос(10)

Ковш сортировать имеет относительно низкую сложность и достаточно прост в реализации

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

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

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

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

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

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

 Omar Kooheji25 сент. 2008 г., 18:04
Вероятно, лучшее решение, за исключением того, что вы также хотите иметь достаточно рабочего пространства в памяти для их сортировки ...
 jfs25 сент. 2008 г., 20:52
меня интересуют примеры кода (яЯ уже читал теоретические аспекты в Кнуте)

анилище доступно? Где вы должны хранить результат?

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

 jfs25 сент. 2008 г., 21:06
Мы обновили вопрос.
Хм, храните их все в файле.Карта памяти файла (вы сказали, что было только 2M RAM;Предполагается, что адресное пространство достаточно велико для отображения файла в памяти).Сортируйте их, используя хранилище файлов, как будто это настоящая память!

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

#!/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..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

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

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

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

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

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

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

 Adam Hawes12 февр. 2009 г., 09:08
Вы'тратить больше места на отслеживание типов, чем выбуду экономить!
 gabr25 сент. 2008 г., 18:35
Wouldn»не очень помогает. Или нене поможет, если все числа больше 65535.
Решение Вопроса
 skaffman02 июл. 2009 г., 11:34
Тот'с подозрительной спецификой :)
 Noah Tony05 сент. 2018 г., 02:38
Гвидо должен сначала оптимизировать свой сайт. Почему он не сделалт белый фон и белый цвет шрифта ;-) выглядит лучше

Ваш ответ на вопрос