Летняя школа Яндекс задание 2 Стажировка вгруппе обработки мета-данных (Москва)

Здание № 2 из списка предложенных для отбора на летнюю школу от Яндекс. Общий список опубликован здесь. Для простоты обсуждения каждое задание публикуется отдельно.

Вакансия предполагает анализ почтовых логов, поиск закономерностей, отклонения от них, поиск возможных багов.

Задание. Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных без знаковых чисел. Нужно отсортировать этот файл. То есть программа  должна  сгенерировать ещё один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство  на жёстком диске.

Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно  отсортировать (размер файла до 16Gb, размер кратен четырём), в argv[2] — имя файла, в который нужно записать отсортированные данные. Предпочтительный язык программирования  — C++.  Решение присылайте в виде архива или ссылкой на репозиторий. Ограничения:

1. Программа  не может рассчитывать, что возможно выделить более 256Mb  памяти.

2. Программа должна эффективно использовать несколько ядер.

Нам бы хотелось получить  решение, по которому можно было бы оценить качество кода

(простота чтения, скорость работы). Засчитывается решение, которое:

1. Компилируется ;)

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

3. Корректно сортирует произвольный файл.

4. Код можно прочитать и понять.

5. Работает эффективно. «Эффективно» значит:

(a) используя немного памяти, зато полностью загружая CPU,

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

2-3% путём микрооптимизаций не учитываем.

Share

Tags: , ,

Leave a Reply