Log files
- From
- Roman Vasin ()
- To
- All
- Date
- 2000-03-01T20:20:55Z
- Area
- RU.ALGORITHMS
From: "Roman Vasin" <vasin@kaluga.ru>
Возникла очень интересная алгоритмическая задача:
Есть лог файл, задача - найти самые встречающиеся ip адреса, т.е. получить
отчет типа:
ip count
-----------------------------
195.12.12.12 20
203.12.32.23. 15
195.64.23.105 8
В чем собственно проблема - формируешь обыкновенный список, а затем просто
сортируешь и выводишь результат.
Проблема в том, что этот список может быть очень большым - несколько
миллионов, это:
1. Занимает большое количество памяти.
2. Значительно замедляет анализ, т.к. при добавлении нового ip необходимо
полностью просмотреть список.
1-й алгоритм, который приходит в голову - это ограничение количества
"кандидатов на самые популярные адреса":
1. Обработка файла до тех пор, пока не кол-во элементов в списке не будет
равно 1000.
2. Сортировка списка.
3. Оставляем "верхние" 100 элементов, остальные 900 удаляем.
4. Если конец файла, то переход к п.5. иначе, переход к п.1
5. Оставляем верхние 10 элементов и выводим их в качестве результата.
Это простейший адгоритм, однако его использование не совсем корректно и есть
куча подводных камней, например такой случай: некоторый ip может стречаться
от цикла к циклу малое число раз, по постоянно на протяжении всех циклов, в
то время как другие ip, "могут захватить перенство", пример
195.10.10.10 303.10.10.10 400.01.01.111
------------------------------------------------
100 50 30
(столько раз ip встретился в 1-м цикле)
0 30 30
(столько раз ip встретился в 2-м цикле)
0 0 30
0 0 30
-------------------------------------------
100 80 120 (Итого
по всему лог файлу)
Здесь 195.10.10.10 с самого начала занимает 1-ю позицию в списке и не
пускает туда 400.01.01.111, хотя в конце концов оказывается, что именно
400.01.01.111 должен занимать 1-ю позицию.
Как быть? У кого какие идеи?
--
Роман Васин, Калуга, vasin@kaluga.ru
Home: http://www.geocities.com/CapeCanaveral/2971/
--- ifmail v.2.15dev4
* Origin: Demos online service (2:5020/400)