Сортировка 1 ТБ файла на машине с 1 ГБ ОЗУ

Question

Этот вопрос кажется легким, но я не могу понять реальную работу за ним.Я знаю, что люди скажут, разбить на 512 Мегабайты и отсортировать их, как с помощью Merge Sort, используя Map Reduce.

Итак, вот актуальный вопрос, который у меня есть:

Предположим, я разбил файл на512 мегабайт чанка, а затем отправить на разные хост-машины для их сортировки.предположим, что эти машины использовали сортировку слиянием.Теперь скажите, у меня было 2000 машин, каждая сортировала 2000, 512 мегабайт.Теперь, когда я сливаю их обратно, как это работает?Не будет ли размер снова увеличиваться?Например, при объединении двух 512 мегабайт получится 1024 мегабайт, что соответствует размеру моей оперативной памяти, так как бы это работало?Ни одна машина не может объединить блок размером более 512 мегабайт с другим блоком, потому что тогда размер> 1 ГБ.

Как в конце объединения я смогу когда-либо объединить два блока по 0,5 ТБ с другим 0,5Кусочек туберкулеза. Приходит ли сюда понятие виртуальной памяти?

Я здесь, чтобы уточнить свои основы и надеюсь, что правильно задаю этот очень важный вопрос (правильно).Кроме того, кто должен сделать это слияние (после сортировки)?Моя машина или несколько из тех 2000 машин?

Answer 1

Краткая версия слияния выглядит следующим образом:

1) Вы создаете таблицу с одним слотом для каждой машины, с которой вы объединяетесь.

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

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

4) Повторите шаг 3, пока таблица не станет пустой.

Это позволяет объединять только N машин, хранящих толькоN записей одновременно.Конечно, вы можете тривиально оптимизировать его для хранения M записей с каждого компьютера.В этом случае вам необходимо сохранить N * M записей, а когда слот пуст, попросите на этом аппарате M записей, чтобы пополнить его.

Answer 2

Эта проблема может быть сведена к более простой задаче .Эта проблема была разработана, чтобы заставить вас подойти.Вот оно:

• Собрать куски = ~ 1 ГБ, отсортировать и сохранить их как отдельные отсортированные файлы.
• В результате у вас в файловой системе 1000 отсортированных файлов по 1 ГБ.

• Теперь, это просто проблема слияния массивов, отсортированных по k, в новый массив.

  Чтобы объединить массивы, отсортированные по k, необходимо поддерживать минимальную кучу (очередь приоритетов) с k элементамиза один раз.

, т.е. k = 1000 (файлы) в нашем случае.( 1 ГБ оперативной памяти может хранить 1000 номеров )

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

У вас будет новый файл,отсортировано по размеру 1 ТБ.

См .: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Обновление

PS: Может быть сделано наодин компьютер с 1 ГБ ОЗУ с улучшенной структурой данных

Объединение может быть выполнено менее чем O (N) пространства с Приоритетной очередью, т.е. O (K) пространства то есть суть проблемы.

Answer 3

Теперь, скажем, у меня было 2000 машин, каждая из которых отсортировала 2000, 512 мегабайт.Теперь, когда я сливаю их обратно, как это работает?Не будет ли размер снова увеличиваться?Например, при объединении двух 512 мегабайт получится 1024 мегабайт, что соответствует размеру моей оперативной памяти, так как бы это работало?Ни одна машина не может объединить блок размером более 512 мегабайт с другим блоком, потому что тогда размер> 1 ГБ.

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

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

Answer 4

Вот теоретический способ, который должен работать.Допустим, у вас есть файлы объемом 512 МБ 2000, которые готовы создать один файл размером 1 ТБ.

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

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

Answer 5

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

Один проход слияния требует 2 (или более) входов и производит один выход. Вы просто продолжаете объединять входные данные в выходные, пока не останется только один файл.