Проблемка опять у меня. Есть почти дописанная прога. До финала остался один рывок
но.. Смысл программы такой. работает в режиме демона и выполняет функции NAT’a
Но в отличии от natd она считает траффик и кладет его в mysq базу. Потом из этой базы
все красиво достается и показывается пользователям.
Когда пакет проходит через мой софт то он перехватывает его смотрит от кого, кому , считает
размер и переправляет дальше. Проблема состоит в том что бы где нибуть хранить промежуточный траффик то того момента когда придет время сбрасывать его в БД.
Нужно в памяти что то вроде хеша, параметр в котором будет являтся ip а значением кол-во байтов. Что делать подскажите? Может кто сталкивался или у кого есть другие идеи по этому поводу?
Последние комментарии
-
OlegL, 17 декабря в 15:00 →
Перекличка
21
-
REDkiy, 8 июня в 9:09 →
Как «замокать» файл для юниттеста в Python?
2
-
fhunter, 29 ноября 2022 года в 2:09 →
Проблема с NO_PUBKEY: как получить GPG-ключ и добавить его в базу apt?
6
-
Иванн, 9 апреля 2022 года в 8:31 →
Ассоциация РАСПО провела первое учредительное собрание
1
-
Kiri11.ADV1, 7 марта 2021 года в 12:01 →
Логи catalina.out в TomCat 9 в формате JSON
1
ecobeing.ru
Экология и вегетарианство на благо всем живым существам Планеты.
Ничего лучше чем хэш функция с массивом и списком в голову не приходит.
Хэш фунция по IP определяет номер в массиве, который ссылается на список
ip — трафик.
А подробнее…?
Д. Кнута в руки и втыкать глазами внимательно. Или, можно просто посмотреть libstdc++ (std::map), или даже glibc (hsearch и hsearch_r). Хотя нет, glibc только строки в качестве ключа приемлет :(.
Ну если сильно извратится можно и ип адреса и траффик конвертить в строки..
Но это изврат( Блин не ужеле нет нечего что бы решить эту проблему??
Прога почти дописана(
если надо, чтобы работало быстро, то — 2/3 дерево — самое оно.
даже если будешь просто сравнивать сами строки как есть.
даже без применения хешей.
Спросил я у гугля:
http://algolist.manual.ru/ds/index.php
http://www.citforum.netis.ru/programming/theory/sorting/sorting2.shtml#4
а 2/3 дерево наверное не лучший выход: 2/3 это для БД может быть хорошо, чтоб на диске искать, а в оперативке лучше b-tree — проще, и не дольше.
Но хеш будет быстрее (тем более что для ipv4 хэш функция не нужна — sizeof (ip адрес) == 4), правда, из хеша удалять неудобно.
2/3-дерево более сбалансированное, при вставке элемента балансировка достигается несколько меньшими затратами.
поиск, как и в обычном бинарном дереве — O(log2 n).
но, в отличие от бинарного дерева, вырождения в список не происходит.
всего делов.
можно комбинировать — хеш (простой xor байтов ip-адреса) + список/2-дерево узлов.
в общем, тут как удобнее будет.
Надо поробовать оба варианта.. Хорошо что в сроках я пока не ограничен.
Чёт я не понял… Кнут вроде писал, что не вырождается.
И точно:
А ip-адреса, думается мне, будут достаточно «случайными».
PS А в ядре linux’а для ip-адресов хэш пользуется :P
Народ а дайте мне что нибуть почитать по этому вопросу?
А то из обрывков фраз много не понял)
Кури TAOCP или TPOP.
ну, если не балансировать постоянно — то вырождаться может..
хотя. как верно подмечено:
балансировать постоянно необходимости нет.
как-то об этом даже не задумывался. ;)
впрочем, на деле-то задумываться о скоростях обработки необходимо, когда просчитывать надо порядка миллиона записей. пара десятков тысяч такой потребности не имеет. (а, скажем, средняя конторка из 20 человек за месяц не всегда наберёт столько адресов, куда ходит, и, соответственно, в статистике много записей и не будет…)
любая толковая книжка по программированию. продаются ли такие счас — я не знаю, но лет эдак несколько (8-10-12) назад найти такие было можно (я по книжным магазинам с тех пор и не хожу…).
лично я со всякими такими методами знакомился на примере написания этих алгоритмов в Прологе.. логично, что логические механизмы учить лучше всего на нём. ;)
У тебя есть в эл виде хотя бы?
вся документация у меня погибла вместе с винтом в 2000ом году (или чуть раньше, не помню уже)
тогда было много чего полезного
впрочем, померла тогда не только документация, но и много программулинок (в то время у меня программерский зуд ещё не окончился, а только-только начинался в серъёзной стадии).
с тех пор почти ничего не восстанавливал — из документации особенно. зачем? если есть гугль, у которого спросить и получить ответ много быстрее, чем копаться на собственном винте в поисках чего-то полезного.. ;)
Так лазил..мне хотя бы пример небольшой а дальше все пойдет как надо.
жаль в универе дальше hello world преподы сами не ушли. А на мое творение смотрят так как будто бы они не преподы по программированию а по истории например ;o)
гугль форева. посмотри algolist.manual.ru. там много чего есть.
Вот еще мысля
Сделать стуктуру в которой будет src_addr входящий и исходящий траффик храниться а потом завести массив указателей на эсу структуру. Программеры как думаете это выход?
Выделять потом динамически память для каждого а после записи в БД free для всех и все по новой. Или есть идея лучше?