Re: Log files

From

Roman Vasin ()

To

All

Date

2000-03-03T21:51:37Z

Area

RU.ALGORITHMS

From: "Roman Vasin" <vasin@kaluga.ru>

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

>  RV> Можно ли построить алгоритм, который бы решал эту задачу не абсолютно
>  RV> точно, а как бы "статистически" точно?
> Нет.
Почему же нет, можно. Я уже описывал (в 1-м сообщении сабжа) такой алгоритм.
Он откидывает (удаляет) элементы с наименьшим счетчиком, по истечении
определенного времени. В конечном счете получаются "приближенные"
результаты. Вопрос в том, как построить алгоритм, который бы давал наиболее
лучшие приближения.

>  RV> т.е. результат являлся бы некоторым ПРИБЛИЖЕННЫМ значением ТОЧНОГО
>  RV> результата?
> Поразмысли логически сам: на основании чего можно вычислить интересующие
тебя
> сведения ? Ну кроме, конечно, гадания на кофейной гуще и расположения
звезд на
> небе ? :) Только на ОСНОВАНИИ АНАЛИЗА ДАННЫХ. Либо ты их анализируешь,
либо
> нет.
Помнишь математику, численные методы? Как выполняется приближенное
вычисление интеграла? Конечно же, анализ данных всегда есть его не может не
быть :)

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

Идея, как мне кажется, в этой задаче может быть такая: при анализе данных
(ip) по истечении некоторого интервала времени необходимо будет принять
решение - оставить текущий ip в списке или нет.
например, в результате нескольких циклов для ip 195.30.30.30:
Цикл, 1,    2,    3,    4,    5,    6,.....
Count: 2,    3,    2 ,    2,    3,   3,

Если представить это графически, то получится почти горизонтальная прямая
(среднее значение счетчика= 2.5). А подсчет общего количества встречаемости
данного ip - это вычисление площади т.е. нахождение интеграла. Ну как такой
подход?

Затем можно сделать экстраполяцию
В данном случае, на протяжении 6 циклов, счетчик данного ip почти не
изменялся, тогда экстраполируюя кривую можно оценить потенциальную
"значимость" такого ip. можно предположить, что после n циклов суммарное
значение счетчика будет равно n*2.5. и если оно в этом случае значительно
меньше, чем текущее значение счетчиков ip из вершины списка, то можно с
уверенностью удалить этот ip из списка "кандидатов" т.е. он никогда не
попадет в 10 самых популярных ip.

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

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


> Решение я тебе уже предложил:
> * B-Tree, страницы кила по четыре.
> * Каждая запись - 4 бата на IP (DWORD) и 4 байта на счетчик использований
(еще
> DWORD), итого - 8. примерно 3 DWORD-а на служебную информацию страницы,
итого -
> 508 записей на страницу. Миллион записей - жалкие 8 мег при условии что
все они
> уникальны. Реализаций Б-Деревьев в ИНете - как собак.
Опиши, пожалуйста, алгоритм формирования B-Tree, хотябы на словестном
уровне, один абзац. или кинь хороший урл.


--
Роман Васин,                          Калуга,    vasin@kaluga.ru
Home:      http://www.geocities.com/CapeCanaveral/2971/




--- ifmail v.2.15dev4
 * Origin: Demos online service (2:5020/400)