Здравствуйте, uzhas, Вы писали:
U>Здравствуйте, makdak, Вы писали:
M>>вот:
M>>M>>Имеется 1TB файл состящий из целых чисел (одно число на строку). Как отсортировать этот файл самым быстрым образом, если есть только 2GB памяти?
M>>
U>что-то тут набросали ключевые слова и даже фамилии, а паззл лично у меня не сложился
U>давайте уточним задачу, а потом набросайте хоть примерную идею решения
U>1) есть текстовый файл размером 1TB (ну я бы сказал не более 1TB), в котором целые числа, умещающиеся в 32 бита перечислены в десятичном представлении. на каждой строке — одно число. между строками — newline (виндовый или линуксовый)
U>2) нужно в этом файле попереставлять строки так, чтобы числа были отсортированы (без ограничения общности, по возрастанию). то есть inplace
U>3) есть ограничение на рабочую память проги — 2GB. не забываем, что кроме огромного массива на 2GB могут быть еще рабочие переменные, так что огроменным массивом, который в точности занимает 2GB нам пользоваться нельзя. сколько там занимает рантайм нам побоку, считаем лишь рабочую память нашего алгоритма
U>не надо только отсылать к чтению томов Кнута, спасибо
А чем не устраивает Кнут? Можно придумать и другие алгоритмы с использованием временных файлов для хранения промежуточных результатов. Потом — перезаписать файл.
Здравствуйте, makdak, Вы писали:
M>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
Меня одного покоробило?
Если числа "размером в 32 бита", зачем нужны новые строки???
Здравствуйте, kaa.python, Вы писали:
KP>Здравствуйте, makdak, Вы писали:
M>>Всем привет!
M>>Как отсортировать файл 2TB с числами, размером в 32 бита, которые записаны в нём так, что каждое с новой строки, имея всего 2 ГБ оперативки??
KP>В Яндекс собеседование проходишь?
Мне такую задачку на скрининге по скайпу с MS дали под завершение разговора, когда оставалось минут 10-15. Только у меня были float-ы. Судя по другим рассказам о скринах MS, я везунчик