nixp.ru v3.0

27 мая 2017,
суббота,
22:36:04 MSK

DevOps с компанией «Флант»
Аватар пользователя Steck
Steck написал 27 июня 2005 года в 14:00 (181 просмотр) Ведет себя как мужчина; открыл 124 темы в форуме, оставил 549 комментариев на сайте.

Проблемка опять у меня. Есть почти дописанная прога. До финала остался один рывок

но.. Смысл программы такой. работает в режиме демона и выполняет функции NAT’a

Но в отличии от natd она считает траффик и кладет его в mysq базу. Потом из этой базы

все красиво достается и показывается пользователям.

Когда пакет проходит через мой софт то он перехватывает его смотрит от кого, кому , считает

размер и переправляет дальше. Проблема состоит в том что бы где нибуть хранить промежуточный траффик то того момента когда придет время сбрасывать его в БД.

Нужно в памяти что то вроде хеша, параметр в котором будет являтся ip а значением кол-во байтов. Что делать подскажите? Может кто сталкивался или у кого есть другие идеи по этому поводу?

iliya

Ничего лучше чем хэш функция с массивом и списком в голову не приходит.

Хэш фунция по IP определяет номер в массиве, который ссылается на список

ip — трафик.

Steck

А подробнее…?

rgo
Steck
А подробнее…?

Д. Кнута в руки и втыкать глазами внимательно. Или, можно просто посмотреть libstdc++ (std::map), или даже glibc (hsearch и hsearch_r). Хотя нет, glibc только строки в качестве ключа приемлет :(.

Steck

Ну если сильно извратится можно и ип адреса и траффик конвертить в строки..

Но это изврат( Блин не ужеле нет нечего что бы решить эту проблему??

Прога почти дописана(

Genie

если надо, чтобы работало быстро, то — 2/3 дерево — самое оно.

даже если будешь просто сравнивать сами строки как есть.

даже без применения хешей.

rgo

Спросил я у гугля:

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), правда, из хеша удалять неудобно.

Genie

2/3-дерево более сбалансированное, при вставке элемента балансировка достигается несколько меньшими затратами.

поиск, как и в обычном бинарном дереве — O(log2 n).

но, в отличие от бинарного дерева, вырождения в список не происходит.

всего делов.

можно комбинировать — хеш (простой xor байтов ip-адреса) + список/2-дерево узлов.

в общем, тут как удобнее будет.

Steck

Надо поробовать оба варианта.. Хорошо что в сроках я пока не ограничен.

rgo
Genie
но, в отличие от бинарного дерева, вырождения в список не происходит.

Чёт я не понял… Кнут вроде писал, что не вырождается.

И точно:

К счастью можно доказать что поиск по дереву требует лишь около $2 ln N \approx 1.386 lg N$ сравнений, если ключи вставляются в дерево в случайном порядке.

А ip-адреса, думается мне, будут достаточно «случайными».

PS А в ядре linux’а для ip-адресов хэш пользуется :P

Steck

Народ а дайте мне что нибуть почитать по этому вопросу?

А то из обрывков фраз много не понял)

myst

Кури TAOCP или TPOP.

Genie
Чёт я не понял… Кнут вроде писал, что не вырождается.

ну, если не балансировать постоянно — то вырождаться может..

хотя. как верно подмечено:

А ip-адреса, думается мне, будут достаточно «случайными».


балансировать постоянно необходимости нет.

как-то об этом даже не задумывался. ;)

впрочем, на деле-то задумываться о скоростях обработки необходимо, когда просчитывать надо порядка миллиона записей. пара десятков тысяч такой потребности не имеет. (а, скажем, средняя конторка из 20 человек за месяц не всегда наберёт столько адресов, куда ходит, и, соответственно, в статистике много записей и не будет…)

Народ а дайте мне что нибуть почитать по этому вопросу?

любая толковая книжка по программированию. продаются ли такие счас — я не знаю, но лет эдак несколько (8-10-12) назад найти такие было можно (я по книжным магазинам с тех пор и не хожу…).

лично я со всякими такими методами знакомился на примере написания этих алгоритмов в Прологе.. логично, что логические механизмы учить лучше всего на нём. ;)

Steck

У тебя есть в эл виде хотя бы?

Genie
У тебя есть в эл виде хотя бы?

вся документация у меня погибла вместе с винтом в 2000ом году (или чуть раньше, не помню уже)

тогда было много чего полезного

впрочем, померла тогда не только документация, но и много программулинок (в то время у меня программерский зуд ещё не окончился, а только-только начинался в серъёзной стадии).

с тех пор почти ничего не восстанавливал — из документации особенно. зачем? если есть гугль, у которого спросить и получить ответ много быстрее, чем копаться на собственном винте в поисках чего-то полезного.. ;)

Steck

Так лазил..мне хотя бы пример небольшой а дальше все пойдет как надо.

жаль в универе дальше hello world преподы сами не ушли. А на мое творение смотрят так как будто бы они не преподы по программированию а по истории например ;o)

rgo

гугль форева. посмотри algolist.manual.ru. там много чего есть.

Steck

Вот еще мысля

Сделать стуктуру в которой будет src_addr входящий и исходящий траффик храниться а потом завести массив указателей на эсу структуру. Программеры как думаете это выход?

Выделять потом динамически память для каждого а после записи в БД free для всех и все по новой. Или есть идея лучше?