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

В том и фишка что файл не сортирован. Значит статистическое распределение его 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

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