Доброго дня,
Давиче столкнулся с задачей которую якобы предлагали на собеседовании 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% - это будет не точный результат. Если говорить о равномерном распределении запросов по файлу - это одно, но, если это реальный лог, то такого не будет, существуют пики нагрузки.

ну.. перефразирую задачу.
Вам нужно определить процент рыжих в Москве.
Есть два - пути - пересчитать всех людей и пересчитать всех людей в каком-либо районе.
Второй способ менее точный, зато намного быстрее.

В том и фишка что файл не сортирован. Значит статистическое распределение его 10% почти совпадает с распределением всего файла.



Да.. это факт. У серверов бывают пики (как например квартал рыжих =)).
В таком случае нужно уточнить какой объем данных будет достаточно репрезентативен. Я думаю лог сервера за неделю - вполне.


P.S. я просто предложил обходной путь.
Если же вопрос ставят ребром - именнно посчитать честно, тогда это все не применимо. 
Но я сомневаюсь что такой объем данных можно обработать за приемлемое время.

погрешность вычислений в условии задана.


ну да, тут я согласен. только эта фишка изрядно усложняет поиски решения  


это уже интересней. неужели тут никого нет кто бы в реальной жизни сталкивался с таким обьемом ? 



Это сообщение отредактировал(а) dva300 - 6.9.2010, 12:28

>sir_nuf_nuf
Не сортирован по значению != не сортирован по времени. 

Хотя да, забавное решение - сначала сделать файл случайным (убив корреляцию, если она там была), а потом считать для небольшой выборки. Единственная проблема - генерация случайного файла - небыстрая операция, либо надо перепаковать исходный в формат с фиксированным размером блока, и мы сразу будем знать позицию байта, с которого начинается i-е число. Здесь затраты по I/O 100% read+100% write+x %random read, где x - число для обеспечения нужной точности. А в моём случае прочитать+записать так же придётся, но величина чтения Х - фиксирована ( 10% )и это более линейное чтение, и даёт точный ответ. Минус - тратится время cpu на сортировку. Т.е. получаем точность за счёт времени cpu. По i/o там будет выигрышь, только если достаточно прочитать <1% файла. Не уверен в этом, надо считать погрешность.

Это сообщение отредактировал(а) DurRandir - 6.9.2010, 15:11

DurRandir, необязательно сильно перемешивать файл.

Можно сделать из него последовательно 10000 выборок по 100 чисел каждая.
Перемещаться можно с помощью seek и потом немного дочитывать до границы числа.

 Если не сортировать файл по Нейману (тоже не быстро при таком размере) тогда можно получить распределение запросов по времени читая файл построчно. 10^10 - это около 20 г байт, если отвести short (будем считать что разброс по времени хороший и повторения маловероятны тогда можно и один байт отвести на счетчик) под каждый счетчик поэтому записывать надо в файл. Нормализуем полученную гистограмму  и интегрируем до 10% со стороны самого медленного запроса.

Sartorius, 
Вы предлагаете использовать файл на 20 Гб в качестве массива флагов/счетчиков или я вас не понял ?
Random-access к файлу на 20Гб - это полный провал. 

sir_nuf_nuf, да он сильно разряженный скорее всего будет. Потом можно несколько проходов сделать. Сначала с малой дискретизацией - пусть только 10000 точек в функции распределения будет. Получаем примерное ограничивающее время для 10% запросов, а на следующем проходе учитываем только запросы выполнявшиеся за время приблизительно равное этому ограничивающему времени (t0).  т.е. нас интересовать будет только интервал t0 - dt < t < t0 + dt, а доля всех запросов с t > t0 + dt- уже известна из первого прохода. Так за два прохода при удачно выбраном dt можно получить точную границу для 10 %
 Кстати в условии не сказано с какой точностью нужно получить границу времени .  

Это сообщение отредактировал(а) Sartorius - 6.9.2010, 17:15

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

>Sartorius
Не ниже точности входных данных - т.е. 10 знаков после запятой.
Несколько проходов = читать исходный файл Х>=2 раза = получаем меньшую точность за бОльшую цену.

Это сообщение отредактировал(а) DurRandir - 6.9.2010, 17:15

Задача искусственная. За одну микросекунду(10^-6) свет проходит 300 метров, а тут десять знаков после запятой.

Когда я решал задачу условие было несколько иным - "Есть файл 1.txt с примерно 10 млрд строками. В каждой строке число, характеризующее время, за которое отработан некоторый поисковый запрос. Задача посчитать в какое время не уложилось 10% самых медленных запросов." Код, который я им отослал:



Решение, которое они предлагают - использовать unix sort. Бонусный вопрос был, что если много разных значений, и в память не поместятся. Новое условие это оговаривает.

Тем не менее, можно решить все тем же подсчетом, если сначала искать приближенные значения, а потом уточнять. 63 значащих бита double (знак отбрасываем) делим на 3 блока 21 бит, и используем их как integer идексы для массива. На втором проходе, если это даст прирост производительности, можно сохранить значения, лежащие в заданном промежутке, во временный файл. Достаточно 3-х проходов для полного диапазона возможных значений.
Сложность такого алгоритма будет линейная, в отличии от сортировки.

На perl'е правда будет реализовать сложнее, ввиду отсутствия работы с внутренним представлением числа.


Это сообщение отредактировал(а) Logo - 6.9.2010, 21:01

unix sort - первое, что мне сегодня подсказал опытный коллега) Там делается сортировка слиянием со сбросом временных буферов на диск. Я прогнал программу на файле из 1ккк чисел (~17Gb), заняло полтора часа. На 10ккк, соответственно, весь вечер+ночь работать будет. Сойдет, в прицнипе.

Это сообщение отредактировал(а) KSURi - 6.9.2010, 21:39

при unix sort придется несколько, много раз по файлу проходить...?

1) а если первый раз пройтись и вычилить среднее значение всех запросов, а из него определить "примерное" эксперементальное поле, за предел которого будет примерно ~7-14%  медленных запросов (из ходя от количества запросов и от минимума и от максимума времени школы и т.д.)...
например, это поле равно 10.40 сек. -- все что дольше 10сек. будет около ~7-17% (ну или ~9-12%)
2) второй раз пройтись и выбрать все что дольше 10 сек. и получить примерно ~10%


Это сообщение отредактировал(а) gcc - 8.9.2010, 10:30

Почти так. По основному файлу будет 1 проход, но по временным несколько. Для юзера это будет происходить прозрачно.
Сначала большой файл разобьется на много отсортированных файлов (в мое случае это было много файлов по ~11Mб), потом эти файлы будут слиты в файлы покрупнее. Эта итерация может повторяться несколько раз, в зависимости от размера исходного файла (в мое случае она повторялась до тех пор, пока не оказалось несколько отсортированных файлов по ~2.7Гб).
В конце все файлы сливаются, и у нас получается исходный отсортированный файл.

Это сообщение отредактировал(а) KSURi - 8.9.2010, 11:47

KSURi, объясните мне зачем нужна сортировка для вычисления распределения запросов ?

Вот упрощенный аналог. 

100 человек стоят в шеренгу. Часть из них лысые. Вам нужно посчитать сколько лысых.
Вам нужно сортировать их ?

gcc, подсчет среднего арифметического, максимального и минимального в общем случае ничего не даст, нам фактически нужно найти квантиль.

sir_nuf_nuf, в таком случае 10 самых высоких) Вернее найти самого низкого среди 10-и самых высоких.

Это сообщение отредактировал(а) Logo - 9.9.2010, 09:52

Это вариант, и он работает за относительно приемлемое время. Я вообще не предлагал это как решение, если что)

задачку порешать интересно. но есть одно но ), умный программист в яндекс и ему подобные конторы работать не пойдет. (кто не понял? для них это тоже своего рода задачка )

я не понял  три раза перечитал и все равно не понял 

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

Эт почему ?

нехотите мозгами пошевелить? или уже работаете в подобной конторе?
в такой конторе с десяток талантливых программистов и постоянно таких набирают, и среди них вы "один из многих", середнячок. над вами стоит начальник и равняет вас как хочет. по одиночке вы личность, а все вместе - строй. а раз строй то его можно пользовать как угодно. догадываюсь что среди интеллектуалов заводить профсоюзы не принято ). а значит при высокой конкуренции есть тенденция к понижению цены рабочей силы. там может и платят выше чем на каком нибудь заводике, или офисе, но высасывают по полной.
вообщем смысл простой, умный человек в строй добровольно не встанет, думающий не позволит использовать себя как пушечное мясо (пусть и в конкурентной борьбе).

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

мозгляков набрать в такую контору прикольно для работодателя, можно даже заплатить за раб силу чуть выше рынка, и потом экспериментировать над этим яйцеголовым инкубатором идей, конкурсы проводить, тайм билдинг ), вводить форму, вообщем прикольно. студентов туда брать лучше всего, чтобы народ с измальства приучался к хозяской руке и не знал о каких либо других вариантах жизни.
и толку что ты талантливый программист? жизнь пуста и нелепа, состоит из, побольшей части никому не нужных, кусков кода. вначале вкалывать прикольно, занимательно, а после 30 уже начинают доставать ребята студенты, которые только вот вышли из универа, и хоть пока еще ничего из себя не представляют по сравнению с Вашим опытом и знаниями но уже наступают на пятки в работоспособности и плодовитости идей. А к сорока годам изношенный материал, с лысым черепом и подавленной самоценкой. Такие люди для начальника самые любимые.... мальчики для битья )
молодого особенно не попинаешь, еще есть в нем что то от вольной жизни, а этого старикана, который токлько и может что тянуть старые свои проекты, грех не попинать, не показать ему на дверь )
А у того жена, да дети, да кредит ))). А тут какждый день приходиться ходить стороем, и не дай бог опоздать на минуту, это молодому простительно, а Вам? А болеть? хотите поболеть? извольте передать свой проект молодому программисту, обьяснить что вы там для себя напридумывали, а там глядишь в ваших услугах и нуждаться уже не будут, извольте болеть сколько хотите.

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

сразу скажу, я не прошел тест ни в одну эту контору )
может я зол на них? я наверное не достаточно подготовлени и/или умен чтобы у них рабоать, эх как жаль. но видно не судьба )

Старо как мир. 
Людей с завышенной самооценкой всегда хватало. 

  
может вы хороший программист но вот бизнесмен вы хреновый. а метите именно туда.

NuINu, забавный рассказ.
А я всегда считал, что когда вокруг умные колеги - это полезно. Самомнение конечно страдает, зато уровень повышается.
А вообще описанная ситуация кажется больше похожа на банк с клерками чем на яндекс с кодерами.

при чем тут завышенная самооценка? я вам обьясняю почему не стоит идти в контору подобную яндексу. причина проста - высокий уровень эксплуатации вашего умственного труда. те соотношение эксплуатация/цена там гораздо выше чем если бы вы работали на каком нибудь заводе и занимались к примеру 1с, кстати именно туда можно пойти после 40 лет, поизносившись на такой вот работе.

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

так что даже решив бы эту задачу блестящее, я бы подумал прежде чем отправлять ее в яндекс ))), вдруг пригласят на собеседование. А там на собеседовании вы увидете такой шикарный офис, узнаете о дружной и сплоченной команде программистов, с нетерпением жаждущих принять в свои ряды такого гения как Вы, про высокую зарплату(страшно даже сказать с бонусами и настоящей медицинской страховкой), и вот тут то вы и почувствуете первые признаки будущего умственного расторойства, как бы его назвать, ах, да, легкое кружение головы сопровождающееся небольшой аритмией сердечных сокращений.
Большой БОСС жмет вам руку, провожает вас к вожделенному креслу, указывая рукой на комьютер ооооо с вожделенным числом гигагерцев и ядер ))). Все дружно отрывают голову от мониторов что бы посмотреть на очередного олуха, на которого торжественно одевают хомут(вириги? )) ), и вновь утыкаюстся в них и дружно топчут клавиатуру.
Ну чтож вот новый конь запряжен, хотя еще и не взнуздан ) но это дело техники, так что можно ехать.

Я прямо завидую вашему боссу, есть на ком покататься, а в случае плохого насторения и по кому прокатиться ).

Ну конечно такая престижная(или уже если говорить о конях пристяжная) работа может вызвать зависть у людей чей доход гораздо ниже, но лишь у тех кто не знает сути этой работы. Ведь как говориться: любишь кататься, люби и саночки возить ) ничто не дается даром(особенно от большого БОССА), повыше зарплата, пожестче требования.

Добавлено через 11 минут и 10 секунд
умные коллеги это здорово, особенно если они становяться друзьями ) (когда наоборот это скорее познавательно, чем полезно )))) умные гадости которые вы будете получать скрасят ваше унылое офисное существование ), умные коллеги это те друзья с которыми я постоянно общаюсь уже давно сменив место работы(феномен интеренета которого небыло буквально 15 лет назад).

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

недавно пересматривал фильм "Антитраст" - там кое что есть из корпоративной культуры офисных служащих, когда вы становитесь одним из многих, собственно уже не важно становиться, чем вы занимаетесь программируете, защищаете родину, клеите дружно марки на конверты или точите детали у станка.

Ерунда, по большей части. 

Умственные нагрузки полезны, так же, как и мышечные. Работая там, где много интересных задач, хорошо прокачиваешь свой уровень. Работая же одмином в какой-нибудь шаражке, деградидируешь. 
Разумеется, неоплачиваемые сверхурочные после работы - совсем другое дело. Известны случаи смерти от работы, это все понятно.
Только вот по моему опыту, как раз таки в мелкой конторе, где начальник, он же владелец, постоянно норовит эксплотировать фиксрованную плату. В более крупных конторах обычно относятся к рабочему времни более формально, со всеми вытекающими.
Оно и понятно, т.к. мелкий владелец получает непосредственную прибыль от твоей переработки.

А вообще, наверно, больше зависит от конкретного места.

Это сообщение отредактировал(а) Logo - 13.9.2010, 23:34

Мимо этого я просто не смог пройти  Интересно знать а как представляете вы ? И откуда знания и на чем основываетесь ?  
Как по мне - ересь чистой воды. В моей практике встречались люди подобного рода убеждений и взглядов. Плачевный опыт одного индивидуума не говорит что у других будет такая же страшная история. Если у вас был начальник дурак и структура на букву Г. то как говориться это сугубо ваша проблема. Станьте начальником сами (не можете ??!!) и тогда вам откроется страшная правда что вы ничем по сути от своего предшественника не отличаетесь. И вот тут начинается настоящее изнашивание мозга. 

И еще - что-то мне подсказывает что вы думаете что только что Америку открыли. Вы ошибаетесь.

P.S. Не смогли решить задачу - скажите что не знаю.    
 

Не кормите тролля)

да не, подожди.. это не троль. троли так много не пишут.


Интересно просто где-же NuiNu такой печальный опыт приобрел ?

Logo, нагрузки полезны, перегрузки вредны. не надо путать эти два момента. когда ты в "команде" перегрузки неизбежны. там конкуренция. там что бы остаться лучшим надо выкладываться пополной, а тут неизбежны перегрузки. 
Маленькая контора это другой конец шкалы эксплуатации. если принимать топ ИТ фирму за один конец и частного владельца на другом. получается парабола, если рисовать по У уровень эксплуатации.


к вопросу о том как изнашивается мозг. да очень просто, человек теряет способность что либо запоминать, на сколько я помню это были исследования японских ученых, они выявили этот факт и обнаружили что этим наиболее часто страдают программисты. к чему это ведет? к типичному случаю - вы не помните то что делали/гооврили 2 минуты назад.

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

последний абзац многое объясняет)

Я, вот, работаю в известной компании (не Яндекс), а ламер-ламером по сравнению с некоторыми присутствующими   
Нормально работается, никто соки не пьет и палкой не погоняет    Скорей - наоборот - хочется самому что-то новое выдумать   


Это сообщение отредактировал(а) Suppir - 14.9.2010, 15:05

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



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



мнительный вы какой-то...

причем тут метод и способ? я вам симптомы болезни описал. которая может возникнуть, как профессиональная болезнь у человека чья профессия связана с чтением большого обьема документации.
легкая форма этой болезни это склероз. тяжелую я описал.
вы наверное это не совсем правильно поняли, больной не разово забывает что то что было 2 минуты назад, а постоянно все забывает. при этом вы не можете ни начем сосредоточиться, просмотреть фильм, чтото почитать, чтото приготовить, вообщем ничего не можете сделать.
кстати вспомнил, в фильме сеть, мать сандры балок болела похожей болезнью, хотя там почемуто она не узнавала свою дочь. это наверняка еще более тяжкий случай, но поражения мозга могут быть разнообразны и их проявления тоже.

но я так понимаю вы не очень мнительны и готовы горы свернуть? те прочитать тонны документации и изучить гигабайты кода ). бог в помощь )
молодые никогда не верят что состаряться, здоровые в то что заболеют ).

я вообщем то и не хотел спорить и отговаривать вас от этой работы, просто предупредил, что конкуренция там будет высокая, и что бы стоять на месте (там), вам придеться очень быстро бежать.
и уж не буду говорить как надо бежать что бы куда то дойти ).

Так в итоге - как задачка то решается?)))

Написано же все.

Решение, которое они предлагают - использовать unix sort. - значит все таки это.Интересное тут выдалось обсуждение 

1. Решение, которое предлагают яндексы unix sort, оно же и наиболее простое, скрипт на пару-другую строк

2. Можно решить без сортировки, а подсчетом, как и то решение, что я привел. Только, т.к. из-за типа double подсчеты не поместятся в память, нужно сделать несколько проходов, сначала делая подсчет с округлением, а затем несколько раз уточнять, сохраняя промежуточные результаты в файл. Наиболее быстрый способ

3. Задача изначально искусственная. Тип double здесь ни к чему. Нельзя и не нужно замерить скорость запроса с точностью 10 знаков после запятой. Меньше наносекунды. За это время свет проходит 3 сантиметра. А максимальное число секунд, которое можно сохранить в double, во много порядков больше возраста вселенной.
Да там еще написано не меньше 10 знаков после запятой. Если больше так это вообще получается до 308 знаков.
Если имеем дело с реальными данными, памяти хватит. Нужно просто округлять значения до соответствующей точности, и опять же, как в том коде который я привел. Достаточно одного прохода файла. Только вместо хеша может потребоваться массив.