Log files
- From
- Boris Rudakov (2:5054/9.4)
- To
- Roman Vasin
- Date
- 2000-03-03T00:57:44Z
- Area
- RU.ALGORITHMS
Hello Roman!
02 Mar 00 18:08, Roman Vasin wrote to All:
RV> From: "Roman Vasin" <vasin@kaluga.ru>
RV> Кстати, решение с помощью деревьев решает проблему скорости, но, как я
RV> понял не решает проблему с памятью, т.е. если лог на ~10Гб, то и
RV> деревьев, создастся на тот же порядок,
Это смотря каково количество уникальных данных. В дерево ведь дубликаты не помещаются: если запись там уже есть, у нее просто счетчик использований увеличивается.
RV> это неподходит.
В таком случае твоя задача вообще не имеет решения: данные либо есть, либо их нет. Непосредственно сам файл ты модифицировать не можешь (в принципе можно было бы отсортировать сами актуальные данные): файл текстовый, и все записи произвольной длинны - обмены внутри файла отпадают. Значит - только внешняя сортировка, значит на временные данные нужна память. Природу не обманешь...
RV> Можно ли построить алгоритм, который бы решал эту задачу не абсолютно
RV> точно, а как бы "статистически" точно?
Нет.
RV> т.е. результат являлся бы некоторым ПРИБЛИЖЕННЫМ значением ТОЧНОГО
RV> результата?
Поразмысли логически сам: на основании чего можно вычислить интересующие тебя сведения ? Ну кроме, конечно, гадания на кофейной гуще и расположения звезд на небе ? :) Только на ОСНОВАНИИ АНАЛИЗА ДАННЫХ. Либо ты их анализируешь, либо нет.
Решение я тебе уже предложил:
* B-Tree, страницы кила по четыре.
* Каждая запись - 4 бата на IP (DWORD) и 4 байта на счетчик использований (еще DWORD), итого - 8. примерно 3 DWORD-а на служебную информацию страницы, итого - 508 записей на страницу. Миллион записей - жалкие 8 мег при условии что все они уникальны. Реализаций Б-Деревьев в ИНете - как собак.
Проблемы ? :)
RV> Роман Васин
Борис Рудаков, Я вчера думал, и мне понравилось -
BBR сегодня я хочу попробовать еще раз !
--- Be happy: BBR is looking at you !
* Origin: АлкАголь малыми дозами безвреден в любых количествах (2:5054/9.4)