LINUX.ORG.RU

стр-ра данных


0

0

Есть программа, которая принимает пакеты из сети. В каждом пакете есть id отправленного в этом пакете сообщении. Эти id в большинстве своем(но не всегда) монотонно возрастают. Иногда могут происходить перепосылки сообщений, тогда приходит новый пакет с тем же id сообщения. Для того, чтобы отсеивать такие перепосылки планирую хранить id-шки сообщений принятых за последние N минут(часов, дней, не имеет значения) и при приходе каждого нового пакета проверять нет ли в этом пуле уже такого id. Тут встает вопрос как реализовать хренения этих id-шек. С точки зрения поиска удобно использовать дерево, но в связи с тем, что ключи в большинстве своем монотонно возрастают просто бинарное дерево невыгодно использовать, т.к. оно будет практически вырожденным. Какие варианты дерева(?) посоветуете для данного случая?

з.ы. пока писал подумалось, что похожую задачу решает tcp/ip стек. кто-нибудь знает что там используют?

з.ы.ы язык, если это важно, c++

anonymous
Ответ на: комментарий от anonymous

> чем не устраивает tcp?

тем что работа приложения ведется поверх tcp. протокол взаимодействия изменить нельзя.

anonymous
()

А зачем дерево? Дак пиши прямо в массив подряд: добавление у тебя будет как очередь, а поиск обычный бинарный. По мере роста массив можно реаллочить, а можно сразу подобрать размер.

swizard
()
Ответ на: комментарий от swizard

да, массив бы многое упростил, но бинарный поиск тут не прокатит потому, что последовательность не строго монотонная. а вставка в серединку массива, не очень эффективное дело =/

anonymous
()

По-быстрому хеш-таблица будет оптимальна.

По-хорошему она имхо тоже оптимальна, только надо хеш-функцию затюнить с учётом знания примерной структуры приходящих данных.

Legioner ★★★★★
()
Ответ на: комментарий от anonymous

> бинарный поиск тут не прокатит потому, что последовательность не строго монотонная. а вставка в серединку массива

Тогда да, тебе там правильно подсказывают выше хеш таблицу. Раз у тебя последовательность, в основном, возрастает, можно сделать так: выделяешь массив списков идентификаторов в N элементов, а в качестве хеш функции берешь f(seq) = seq % N.

Соответственно, чем больше ты возьмешь N, тем ближе время доступа будет к константе, а то, что у тебя возрастающая последовательность выльется в эффективное использование памяти :)

swizard
()
Ответ на: комментарий от swizard

Предлагаю задуматься о том, стоит ли хранить каждый ид... может лучше хранить интервалы пришедших (ну это если пропуски бывают редко и последовательность монотонно возрастает)... или вообще только пропуски хранить. А использовать как структуру лучше всего любой дерево с балансировкой - АВЛ или Красно-чёрное... или чего там ещё есть. В хэш-таблице смысла не вижу - если будет много коллизий - выродится в тот же массив, если мало - тоже не так много радости, как от двоичного поиска :)... хотя многое зависит от того, каков характер твоих данных. С другой стороны, хэш проще...

anonymous
()

> з.ы. пока писал подумалось, что похожую задачу решает tcp/ip стек. кто-нибудь знает что там используют?

кажется, ты изобретаешь велосипед. Tcp поверх Tcp, есть же туннели..

http://en.wikipedia.org/wiki/Transmission_Control_Protocol#Ordered_data_trans...

"Двухстороннее рукопожатие" там используют.

TCP, имеет в пакете "номер последовательности", "номер подтверждения". При установлении соединения отсылается пакет с установленным SYN; на него приходит ответ с установленным ACK, с "номером подтверждения" = " номеру последовательности" ; потом пакеты приходят с соотв. синхронизированными номерами последовательности, подтверждения, которые увеличиваются

В деталях + недостатки этой схемы http://bugtraq.ru/library/books/attack/chapter04/05.html

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.