Как сортировать миллионы строк данных в файле с меньшей/меньшей памятью

Я присутствовал на интервью на прошлой неделе, и этот вопрос был задан:

Как вы сортируете миллиард строк данных в файле с 640 КБ памяти на компьютере с процессором 8080? Нет виртуальной памяти, нет внешнего диска.

Я прямо спросил интервьюера, могу ли я использовать жесткий диск, поэтому я могу сериализовать деревья по мере сортировки, а затем объединить в конце. Он сказал нет. Я пробовал много способов, разные алгоритмы. Ничего не согласилось.

Я сдался и вежливо спросил его: "Как бы вы это сделали?" Он прямо сказал: "Я бы не сказал тебе". (Интервью закончилось сразу после этого. Я не хотел обидеть его, как разработчика, мне было любопытно. Более того, это был инстинктивный вопрос, так же как я бы спросил кого-нибудь на моем рабочем месте.)

Это интервью было для действительно большого банка.

Итак, как бы кто-нибудь приблизился к этой проблеме?

Ответ 1

Хепсорт будет моей рекомендацией. Это относительно быстро, когда n велико, и вам нужно только взглянуть на три элемента с определенными indecies сразу.

Говоря, моя интуиция подсказывает мне, что сортировка миллиарда строк на 8080, даже в C, будет неоправданно медленной.

Ответ 2

Я бы не стал делать это на С#, для начала. Вы уверены, что это верно? Это проблема C, если она может быть решена.

640K дает вам только 640 * 1024 * 8 бит, поэтому нет возможности решить эту проблему в кадре. Возможно, тот ответ, который он искал. Эти интервью с инвестиционным банком иногда представляют собой мозговую игру.

Ответ 3

Если скорость не является требованием, вы можете "сортировать пузырь" в файле. Это требует только одновременного просмотра двух рядов данных без необходимости внешней информации или хранения.

Ответ 4

Другой вопрос, который нужно задать, - "Какова природа строк?" Если количество отдельных значений достаточно низкое, то ответ может быть сортировка отверстий голубя.

Например, скажем, что файл, подлежащий сортировке, содержит только строки, содержащие число от 0 до 100 включительно. Создайте массив из 101 неподписанных 32-битных или 64-битных целых чисел со значением 0. Когда вы читаете строку, используйте ее для индексации массива и увеличения количества этого элемента. Как только файл будет прочитан, начните с 0, прочитайте количество нулей, прочитанных и выплюнув, что многие, перейдите к 1, повторите. Разверните размер массива по мере необходимости, чтобы обработать набор чисел, проходящих через. Конечно, есть пределы, скажем, значения, которые можно увидеть, варьируются от -2e9 до +2e9. Это потребует 4х9 бункеров, которые не собираются вписываться в 640 тыс. ОЗУ.

Если вместо этого строки являются строками, но вы все еще смотрите на достаточно маленький набор различного значения, тогда используйте ассоциативный массив или хеш-таблицу для хранения счетчиков.

Ответ 5

Кнут имеет целый раздел внешняя сортировка; это было обычным делом, когда не было жестких дисков и не было большого количества памяти, а ленточные накопители были нормой. Посмотрите на страницу wikipedia и/или vol. 3 Knuth Art of Computer Programming.

Я согласен с комментарием Робусто:

Откуда вы получаете файл, если вы не можете использовать диск? Это, конечно, не будет сохранено в памяти.

Недостаточно определения проблемы.

Ответ 6

Чем больше я думаю об этом, тем больше я думаю, что сортировка слияния будет очень хорошо работать в окне памяти, которое мы даем.

Скажем, у вас есть память x. Разделите миллиардные записи на миллиард /x + 1 разделов и купите их (heapsort, потому что не требуется дополнительная память, и время O (2n (log n))). Когда все секции будут удалены, выполните сортировку слияния, начиная с первых элементов всех разделов. Это будет работать до тех пор, пока у вас больше памяти sqrt (миллиарда) для работы с данным базовым использованием памяти 8080 OS.

Выполняя математику, предполагается, что каждая строка данных меньше 165 бит.

Ответ 7

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

Если вы должны начать с несортированного файла и отсортировать его, вы можете использовать merge для создания слияния на месте, работающего на очень маленьких фрагментах файла. Так как ограничений времени доступа на носитель не существует, это может быть очень быстро.

Ответ 8

Я бы использовал GPU! Даже на быстром компьютере графический процессор часто быстрее сортирует. И я не знаю, насколько велики "ряды", но нетрудно найти 1 ГБ видеокарты, чтобы ответить на вопрос о хранении тоже.

Кроме того, если бы мне пришлось работать на 8080, я бы определенно захотел поставить самую сладкую графическую карту, которую я мог найти там.

Вам просто нужно быть готовым к следующему вопросу: "Как вы получите 8080, чтобы поговорить с современной картой PCI Express 2.0 x16?". Я обнаружил поистине чудесный метод, но это текстовое поле слишком узкое, чтобы его содержать.

Ответ 9

Вы можете найти обсуждение аналогичной проблемы в Jon Bentley Программирование Pearls Колонка. 1. Здесь Bentley занимается проблемой сортировки миллионов кодов областей, которые гарантированно уникальны с использованием битовой структуры данных.