Доброго дня,
Давиче столкнулся с задачей которую якобы предлагали на собеседовании Perl программиста в Yandex.
Суть : Есть файл со строками. В каждой строке число, характеризующее время, за которое отработан некоторый поисковый запрос. Числа в файле принадлежат типу double и имеют как минимум 10 значимых цифр после запятой. Задача - посчитать в какое время не уложилось 10% самых медленных запросов.

Все бы ничего если бы не следующий комментарий - файл состоит из минимум 10млрд строк !!! И естественно файл не отсортирован и возможны дырки между числами.

Посидел, подумал. Интересно однако стало  
Вспомнил пару алгоритмов и максимум что у меня получилось это 46 секунд на 1млн (на 10млн получил 413 сек, дальше не пробовал ) что при даже самых скромных вычислениях даст ~ 127 часов на 10млдр  

Собственно вопрос - как решить задачу в приемлемые сроки. Какой алгоритм использовать ? Свои результаты получал на половинчатом делении. Ниже реализация.
Будет интересно послушать ваше мнение относительно данной задачи.


 

какой размер файла не написан... 

Это сообщение отредактировал(а) gcc - 4.9.2010, 15:09

этого в условии нет.
дано лишь то что тип doulbe. и мин 10млрд 
но вариации на тему кол-во элементов = size of file / size of double не прокатать потому как мин 10 значащих знаков... погрешность на лицо

Размер там написан - минимум 112гб на диске. 

Т.е. прочитать всё в память - не вариант. У вас выбран вариант "читаем всё очень много раз" - пока данных мало (даже 10м - мало), вы читаете всё из дискового кэша, скорее всего, поэтому не сильно чувствуете ограничения на скорость дискового чтения. Если бы было надо найти 1% самых медленных (т.е. столько, сколько в принципе может влезть в память) - было бы проще (бонусный вопрос - почему?). А так - читаем какими-то разумными блоками (10м?), сортируем их в памяти, пишем на диск. Занимаем этим занятием все процессоры попутно. Потом, т.к. сами данные нам не нужны, а нужна только граница, то вместо полноценного merge'a результатов, просто пропускаем первые 10% значений (общее количество мы уже знаем - т.к. прочитали на предварительной сортировке все)  - и получаем границу. 

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

На счет задачи ты уж как нибудь сам)

PS: а сколько они обущали/обещают платить, если не секрет?)

так не корысти ради же  я уже старый так всякого рода конкуренции 
просто интересно.

вариации на тему если ... ну если бы файл был отсортирован то я бы тут не спрашивал 

Добавлено через 1 минуту и 6 секунд


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

>а сколько платить - устраивайтесь и узнаете  
Мне _очень_ лениво ездить в Мск ради непонятного результата и без точных цифр (а сейчас все скрывают. Конечно, это спорная позиция, но что поделать.

ну так если даже Lоgo послали то напишите им решение и узнаете цену   

А они принимают случайно присланные решения?)))

я так понимаю и искренне надеюсь что они принимают правильные решения   
тем более если как говорит Logo задача жива еще с весны  

Это сообщение отредактировал(а) dva300 - 4.9.2010, 16:36

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

Я тему зп  не затрагивал, ждал их предложения. Свои тесты они предложили пройти в ответ на размещенное резюме, в котором была указана зп 60 или 50 т. р. 
Условия у них хорошие, свободный график.

ЭЭЭ.. а никому не пришло в голову что не нужно весь файл перелопачивать ?
По моему выборки в 1 000 000 запросов вполне достаточно будет что бы посчитать время 10 % самых медленных.
Тем более что они говорят, что файл не отсортирован. 
ИМХО нужно уточнить откуда они этот файл взяли. И если это не выдуманная ситуация - то сократить себе работу

как ? файл то не отсортирован.


ну так в том то и дело не что отсортирован  так бы действительно было бы все просто.
хм... или я смотрю в книгу и вижу фигу....



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

>sir_nuf_nuf
Это вероятностный подход. Предположим, вы выбрали 1кк самых быстрых или самых медленных запросов, и нашли среди них нижние 10% - это будет не точный результат. Если говорить о равномерном распределении запросов по файлу - это одно, но, если это реальный лог, то такого не будет, существуют пики нагрузки.