Всем привет!
Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??:???:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Дональд Кнут, том 3. Внешняя сортировка.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, makdak, Вы писали:
M>Всем привет! M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
В Яндекс собеседование проходишь? Я, когда-то давным давно, так делал эту задачку решал. Сейчас, правда смотрю на это и понимаю что сделал бы иначе. Вообще интересно на свой старый код смотреть
Здравствуйте, makdak, Вы писали:
M>Всем привет! M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Даные в текстовом файле через перевод строки от 2 до 11 байт... Если есть еще 2Тб для результата или хотя бы 20Гб для промежуточных данных то
сортировка подсчетом (40бит счетчики) справится. Делишь 20Гб по 2Гб получаешь ~10 чтений по исходному файлу и одна запись результата.
Здравствуйте, kaa.python, Вы писали:
KP>В Яндекс собеседование проходишь?
почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать.
А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Здравствуйте, uzhas, Вы писали:
U>лучше гномиков посчитайте U>гораздо полезнее и писать код не надо
Здравствуйте, makdak, Вы писали:
M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Студентов, наверное, сперва через Академию Яндекса протаскивают.
Здравствуйте, makdak, Вы писали:
M>почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать. M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
В этой задачке ничего сверхчеловеческого нет, но она требует опыта в определенной сфере или как минимум практики пусть даже в на учебных задачах в чем-то похожем. Сходу, если учесть все их требования (их больше было чем ты привел) человек без нужного опыта врядли корректно решит. Насколько им действительно нужен такой опыт вопрос отдельный, но, видимо, важен. Либо просто очень большой поток желающих достаточно высокого качества и его нужно как-то фильтровать.
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, makdak, Вы писали:
M>>почти, угадал. Бывшие работники Яндекса, как-то прислали вопросы, еще до собеседования, там вот этот вопрос и был. Для себя хочу знать. M>>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
KP>(их больше было чем ты привел) человек без нужного опыта врядли корректно решит.
вот:
Имеется 1TB файл состящий из целых чисел (одно число на строку). Как отсортировать этот файл самым быстрым образом, если есть только 2GB памяти?
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??:???:
Здравствуйте, makdak, Вы писали:
M>Всем привет! M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
M>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки?? Q>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
Это — само собой, ибо числа целые.
Но сортировка подсчетом работает только над отдельной порцией данных.
А потом все равно все порции — сливать.
А это внешняя сортировка (слиянием), о коих в 3 томе Кнута написано чуть ли не полкнижки.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
M>>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки?? Q>>Может, предполагается, что надо использовать что-то типа сортировки подсчётом? LVV>Это — само собой, ибо числа целые.
больно разрядность большая. много Cache Miss будет.
Здравствуйте, kov_serg, Вы писали:
_>Даные в текстовом файле через перевод строки от 2 до 11 байт... Если есть еще 2Тб для результата или хотя бы 20Гб для промежуточных данных то _>сортировка подсчетом (40бит счетчики) справится. Делишь 20Гб по 2Гб получаешь ~10 чтений по исходному файлу и одна запись результата.
Счётчики можно сделать более хитрыми.
Например размером в байт.
Тогда если старший бит сброшен — счётчик находится прямо в этом байте. (0-127)
Если выставлен — младшие 7 бит означают номер корзины, в которой лежит внешний счётчик большого размера (хоть 64 бита). Большие счётчики создаются динамически, при переполнении встроенного. Проход по корзине произвольный, для начала можно даже линейный.
Скорее всего уложишься в один проход, с выделением памяти чуть больше 2гб.
Можно несколько алгоритмов придумать, для разного характера распределений чисел. И обрывать проход с перевыбором алгоритма, если статистика говорит что есть более оптимальный способ.
Здравствуйте, Qbit86, Вы писали:
Q>Может, предполагается, что надо использовать что-то типа сортировки подсчётом?
Не выйдет.
Для гистограммы над двордами нам потребуется 4 гига счётчиков, причём 40-битных (2 терабайта поделить на 2..16 байт в каждой строке). То есть, 20 гектар, если выжимать биты, и 32 гектара, если не выжимать.
А в нашем распоряжении только 2 гектара, то есть, по полбайта на счётчик.
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, LaptevVV, Вы писали:
M>>>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки?? Q>>>Может, предполагается, что надо использовать что-то типа сортировки подсчётом? LVV>>Это — само собой, ибо числа целые.
NB>больно разрядность большая. много Cache Miss будет.
2 гига — это как раз для 32-битных знаковых целых подойдет.
Но есть еще поразрядная сортировка — прекрасно подойдет в данном слуучае
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, makdak, Вы писали:
M>А что, в Яндекс только сверхчеловеков берут только? вроде и студентов набирают.
Студенты у них должны уметь просыпаться среди ночи, и быстро поисковые запросы отрабатывать. Ну или там, такси искать, в зависимости от проекта. Тоже в своем роде сверхчеловеки.
M>Имеется 1TB файл состящий из целых чисел (одно число на строку). Как отсортировать этот файл самым быстрым образом, если есть только 2GB памяти?
M>
что-то тут набросали ключевые слова и даже фамилии, а паззл лично у меня не сложился
давайте уточним задачу, а потом набросайте хоть примерную идею решения
1) есть текстовый файл размером 1TB (ну я бы сказал не более 1TB), в котором целые числа, умещающиеся в 32 бита перечислены в десятичном представлении. на каждой строке — одно число. между строками — newline (виндовый или линуксовый)
2) нужно в этом файле попереставлять строки так, чтобы числа были отсортированы (без ограничения общности, по возрастанию). то есть inplace
3) есть ограничение на рабочую память проги — 2GB. не забываем, что кроме огромного массива на 2GB могут быть еще рабочие переменные, так что огроменным массивом, который в точности занимает 2GB нам пользоваться нельзя. сколько там занимает рантайм нам побоку, считаем лишь рабочую память нашего алгоритма
не надо только отсылать к чтению томов Кнута, спасибо
Здравствуйте, uzhas, Вы писали:
U>2) нужно в этом файле попереставлять строки так, чтобы числа были отсортированы (без ограничения общности, по возрастанию). то есть inplace
Я, когда-то давным давно, так делал эту задачку решал. Сейчас, правда смотрю на это и понимаю что сделал бы иначе. Вообще интересно на свой старый код смотреть 
Перекуём баги на фичи!
