Когда-то, давным-давно, в разгар активного поиска работы я написал в Яндекс. Не то что бы я думал туда пройти, все же алгоритмы не моя сильная сторона, но мне подумалось “а почему бы не попробовать, особенно с учетом того, что на РСДНе ходят легенды о полнейшей невменяемости собеседующих там товарищей”. Вобщем решил сходить и чисто позырить. Позырить мне так и не удалось, т.к. яндексовцы дали тестовое задание на дом, а на такое я принципиально не соглашаюсь. Но, надо признать, задание было интересное, и я его прикопал с целью когда-нибудь, когда будет соответствующее настроение, решить. Соответствующего настроения не было у меня два года, и вдруг оно появилось!
Само задание выглядит следующим образом:
Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске.
Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем),
в argv[2] – имя файла, в который нужно записать отсортированные данные.Ограничения:
1. Программа не может рассчитывать, что возможно выделить более 256Mb памяти.
2. Программа должна эффективно использовать несколько ядер.Кратко опишу, как будет оцениваться результат. Нам бы хотелось получить решение, по которому можно было бы оценить качество кода (простота чтения, скорость работы). Засчитывается решение, которое:
1. Компилируется
2. Правильно завершается, даже при неправильных данных, недостаточных ресурсах, а не просто падает в случайных местах.
3. Корректно сортирует произвольный файл.
4. Код можно прочитать и понять.
5. Работает эффективно. Эффективно значит
а) используя немного памяти, зато полностью загружая CPU.
б) нельзя придумать существенно более эффективное (на десятки процентов, или с принципиально лучшей временной сложностью) решение. Экономию в 2-3% путем микрооптимизаций не учитываем.Было бы идеально, если бы решение представляло собой один cpp файл, который компилировался бы gcc 4.x или ms visual studio c++ compiler’ом версии >= 7.1. Если не получится собрать, будем разбираться. Желательно бы в решении не использовать copy&paste из библиотек.
Кстати, на РСДНе чувак как-то постил пример своего решения данной задачи, которое обрабатывало данные 4 часа. Как у него вышло добиться такого эффекта я так и не понял, т.к. мой первый вариант, не полностью соответствующих требованиям т.к. работает в 1 поток и особо не обрабатывает ошибки, сортирует 1 гигабайт данных за 3.2-3.3 минуты, а на сортировку 4 Гб нужно 13-14 минут. Можно сделать скидку на разны объемы данных и на более мощное железо, которое появилось сейчас, но не на столько же…
Если говорить о возможных решениях, то мне в голову пришли 2 варианта. Первый вариант, скорей всего менее правильный но более интересный, так что я начал с него. Суть этого варианта в том, что при помощи быстрой сортировки можно отсортировать блоки данных по 256 (или меньше) Mb и сбросить их на диск в виде отдельных файлов. Потом, все маленькие файлы, содержащие отсортированные данные, можно склеить в один большой отсортированный файл. При этом, если говорить о параллельной сортировке, то как быстрая сортировка, так и сортировка слиянием довольно хорошо параллелятся.
Отдельно хотелось бы рассказать о времени затрачиваемом на чтение/запись. При работе с блоком памяти размером 128 мегабайт, на его чтение тратится около 26 миллисекунд, а на запись около 1750 миллисекунд. При этом, на саму сортировку (алгоритм quick sort) уходит примерно 12900 миллисекунд. Так что, суммарные потери на работу с винчестером, только в случае первичной сортировки, составляют порядка 10%, что довольно много. А уж в случае слияния отсортированных масивов, времени на работу с диском должно уходить еще больше, т.к. алгоритм слияния существенно проще алгоритма сортировки, а операций чтения/записи больше. Кроме того, учитывая то, что каких-то серьезных изменений в этом соотношении при изменении размеров буфферов в 2-4 раза не происходит, можно модифицировать алгоритмы, вынеся запись в отдельном потоке с переключением между буфферами.
Исходные коды однопоточного варианта и репозиторий на GitHub.
Да, если говорить о многопоточном варианте или о варианте №2, то они будут несколько позже
Почему кстати тестовые задания дома не решаешь? считаешь ниже своего достоинства?
Когда я в тот раз искал работу, у меня было по 1-2 собеседования в день, почти все закончились предложениями работы. Глупо тратить время на решение заданий при таком раскладе.
В текущей версии calcPivote возвращает int а не T. Это корректно?
Скажем так, это, почему-то, работает %)
Спасибо за замечание!
ну почему работает совершенно понятно.
раз уж все генерализуемо,
видимо если поменять целочисленное на строки, то перестанет.
а что, по тесту надо было самому quicksort делать? просто std::sort не подошел бы?
Ну как бы его надо еще распараллелить. До чего у меня пока что руки не дошли. Так что обычный qsort скорей всего не подойдет.
Первое впечатление, что здесь нужно было тупо реализовать какой-то из методов внешних сортировок. Например, в универе мне довелось докладывать принцип работы сбалансированного многоленточного слияния (тыц), поэтому сразу вспомнилось.
Ну а потом уже делать какое распараллеливание этого дела. Например, выделить одну нить для IO, остальные для проведения операций слияния нескольких блоков в ОП.
Да, я тоже так думаю. Почти вынес запись данных на диск в отдельный поток. Вроде и идея проста, но код разрастается как на дрожжах.
Но еще мне кажется что сортировка подсчетом вообще всех порвет
А “сортировка подсчетом” это что?
А берешь и считаешь сколько раз встречается каждое из влезающих в uint32 чисел.
для чисел – неплохой вариант
Если честно, не понял ваше решение.
Вы предлагаете сортировать блоки по 256 мб. На выхлопе вы и будете иметь набор отсортированных блоков по 256 мб, которые склеить напрямую невозможно.
Все отлично склеивается при помощи слияния, так как для операции слияния иметь все данные в памяти не обязательно. см. “сортировку слиянием”
Сейчас они дают похожее задание, только теперь это текстовый файл в 4 ГБ, в общем, нужно отсортировать строчки с имеющейся памятью, например, в 512 МБ.
Я там у них допёр до такого же решения, они не приняли, сказали, что можно быстрее. Ну и там подсчёт не поможет. Сейчас дописываю решение с буферами. Потом добавлю чуть параллельности. И попробую ещё раз отправить им
Про то что там собеседуют неадекваты – неподтвердившиеся слухи, очень даже прикольные люди. Правда меня до очного собеседования 8 раз собеседовали по скайпу
А Касперский, кстати, вообще не отвечает на отклики на hh.ru
Про неадекватов, обычно, рассказывают люди завалившие собеседование. По мне так сотрудники Яндекса, с которыми я общался, в общей массе адекватны, но работать с ними я бы не хотел.
Для ЛК довольно характерно не отвечать на сообщения. В общем случае это не значит вообще ничего, к сожалению. Если тебе хочется там работать, то есть только два варианта: пробивной внешний HR который организует тебе собеседование либо прямой выход на человека в компании, которому нужны люди.
А почему не хотел бы работать с ними? (Если не секрет.)
Основная причина – они слишком уж уверенны в своей офигенности и уникальности, что сказывается на процессе общения не в лучшую сторону. Один из тимлида в мне успел на хамить ещё до начала собеседования, потом его начальник, правда, извинился, но пусть и ложечки то нашлись, но осадок остался. Плюс подчеркиваемая молодежность и неформальность мне не нравится. Наверное, это звучит по старперски, но тем не менее
Я тут, кстати, порешал им эту задачку – https://github.com/vladon/test-yandex
Два способа: как у тебя здесь (ну тупо в лоб мёржим сразу читая и записывая) и второй – с помощью priority_queue и буферов.
С буферами медленнее чуток