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

Question

(С здесь )

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

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

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

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

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

Итак, как кто-то может подойти к этой проблеме?

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

Кнут имеет целый раздел внешняя сортировка ; Это было обычным делом, когда не было жестких дисков и не так много памяти, а стримеры были нормой. Посмотрите на страницу википедии, и / или том. 3 Кнута Искусство компьютерного программирования.

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

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

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

Answer 8

Обсуждение аналогичной проблемы можно найти в Jon Bentley Programming Pearls Столбец. 1. Здесь Bentley имеет дело с проблемой сортировки миллионов кодов городов, которые гарантированно будут уникальными при использовании структуры данных с битами.

Answer 9

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

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

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