Бинарное дерево поиска

[nuclearcat]

Есть ли смысл заменять в приложении на 700-800 элементов (tcp коннектов) (планируется в два раза больше в будущем) бинарное дерево поиска вместо линейного?

Конечно впихнуть код можно, но есть ли смысл?

[user_anonymous]

Есть ли смысл заменять в приложении на 700-800 элементов (tcp коннектов) (планируется в два раза больше в будущем) бинарное дерево поиска вместо линейного?

Конечно впихнуть код можно, но есть ли смысл?

Во время линейного поиска у вас в среднем будет пройдена половина элементов, тоесть будет примерно 400 обращений. Для поиска в сбалансированном дереве из такого же количества элементов потребуется порядка 10 обращений. Деревья рулят :) А если у вас элементы живут довольно долго - можно подумать об организации коннектов в виде постоянно отсортированного массива из указателей на структуры. Это будет еще круче, чем дерево. Дерево, кстати, лучше делать не простое, а красно-черное или, на худой конец, рандомизированное.

[jab]

не прошло и пятнадцати лет, как пингвинщики начали залезать на деревья...

в то время как bsd'шники с них и не слезали...

[ram_scan]

jab: среди bsd-шников тоже дохрена народа которые Кнута ниасилили.

nuclearcat: дерево можно юзать любое, хоть trie деревья, главное чтобы с автобалансировкой. Либо использовать хэширование, это тоже к Кнуту, только оверхед может по памяти свирепый получиться. Для бинарных деревьев уже упоминался достаточно несложный алгоритм балансировки red-black. Либо avl дерево.

 

Ну и в зависимости "от" можно еще поднять крепко производительность используя шитые деревья (например дополнительный указатель для ассоциации двух соединений)

[jab]

jab: среди bsd-шников тоже дохрена народа которые Кнута ниасилили.

Какой из томов и в каком году ? Я например совковый трехтомник после 92го и не читал ни разу.

Мне как-то Ершова всегда хватало. :-)

[PommeFritz]

Есть ли смысл заменять в приложении на 700-800 элементов (tcp коннектов) (планируется в два раза больше в будущем) бинарное дерево поиска вместо линейного?

Конечно впихнуть код можно, но есть ли смысл?

Используйте хэш-таблицу, немного накладно по расходу памяти (смотря с какой стороны посмотреть, впрочем), зато поиск почти всегда (зависит от количества коллизий, которое в свою очередь определяется выбранной хэш-функцей) O(1), тоесть в 99.999% за одно обращение.

 

ЗЫ

Странный вопрос для автора такого замечательного продукта как globax ;)

[nuclearcat]

Просто ищу оптимальный алгоритм.

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

Насчет красно-черного еще не дочитал, т.к. понял, что без автобалансировки не обойтись, элементы достаточно часто удаляются-добавляются.

Насчет хешей посмотрю.

А вообще... интерес больше теоретический, чем практический. Это далеко не самая ресурсоемкая операция в программе.

[jab]

По-моему, чем читать всю эту ерунду, проще взять библиотечные

функции и прогнать тесты в граничных условиях задачи.

[PommeFritz]

По-моему, чем читать всю эту ерунду, проще взять библиотечные

функции и прогнать тесты в граничных условиях задачи.

судя по количеству и качеству ваших сообщений, вы не только любите читать всю эту ерунду.

[jab]

судя по количеству и качеству ваших сообщений, вы не только любите читать всю эту ерунду.

Именно, прежде чем советовать применять хэши даже не потрудившись узнать условия задачи,

я предпочитаю сравнительное тестирование того, что уже есть. :-) А то под описание "приложение

на 800 tcp-коннектов" попадает половина современного софта.

[user_anonymous]

...

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

Я для себя проводил ну не то, чтобы серьезные исследования, но оценки. Так вот, оказалось, что все очень не плохо, если мы используем подобную технологию.

Для того, чтобы сортировать массив с рандомным распределением лучше всего быстрая сортировка. Но в нашем случае - это плохой выбор, так как у нас массив будет отсортированным с самого начала. Идеальна тут сортировка вставками.

Если вы используете большие структуры в качестве элемента массива - лучше сделать второй массив из указателей на них и сортировать его.

 

Вот результаты моих "исследований" (Athlon 2600/2x256 PC400 одноканальный режим)

 

Сортировка вставками массива из 1000000 чисел типа long int.

90% отсортировано

10% случайно

start: 1166554525 end: 1166555108 diff = 583

 

Сортировка вставками массива из 1000000 чисел типа long int.

99% отсортировано

1% случайные

start: 1166554027 end: 1166554088 diff = 61

Итого: 61 секунда

 

Сортировка вставками массива из 1000000 чисел типа long int.

99,9% отсортировано

0.1% случайные

start: 1166554345 end: 1166554351 diff = 6

 

На закуску:

Добавление 100000 случайных элементов к отсортированному массиву из 900000

чисел.

start: 1166555783 end: 1166555815 diff = 32

 

Добавление 10000 случайных элементов к отсортированному массиву из 990000

чисел.

start: 1166556010 end: 1166556011 diff = 1

1 секунда

 

Добавление 100 случайных элементов к отсортированному массиву из 999900 эл-тов

start: 1166555351 end: 1166555351 diff = 0

 

 

видно, что добавление к отсортированному массиву - это нечто гораздо более быстрое, чем сортировка.

 

PS Хэши штука очень хорошая, когда элементов мало и правильно подобрана хэширующая функция. Может в вашем случае это и впрямь будет оптимальным вариантом.

[PommeFritz]

судя по количеству и качеству ваших сообщений, вы не только любите читать всю эту ерунду.

Именно, прежде чем советовать применять хэши даже не потрудившись узнать условия задачи,

я предпочитаю сравнительное тестирование того, что уже есть. :-) А то под описание "приложение

на 800 tcp-коннектов" попадает половина современного софта.

Именно! Применять сбалансированные деревья на таком числе элементов - стрельба из пушки по воробьям. Сортированные массивы - принципиально метод поиска аналогичен сбалансированным деревьям, а вот вставка новых элементов - гимор. Не зря же деревья придуманы. Хотя каждый сам себе буратина. Хеши, кстати, интенсивно используются в коде ядра что линукса что других "не юниксов". Подумайте на досуге почему.

Для примера реализации аналогичных поставленной задач на хэшах можно почитать сорцы /usr/src/sys/netgraph/netflow во фре или /usr/src/linux/net/core/flow.c в линуксе.

[user_anonymous]

Именно! Применять сбалансированные деревья на таком числе элементов - стрельба из пушки по воробьям. Сортированные массивы - принципиально метод поиска аналогичен сбалансированным деревьям, а вот вставка новых элементов - гимор. Не зря же деревья придуманы. Хотя каждый сам себе буратина. Хеши, кстати, интенсивно используются в коде ядра что линукса что других "не юниксов". Подумайте на досуге почему.

Для примера реализации аналогичных поставленной задач на хэшах можно почитать сорцы /usr/src/sys/netgraph/netflow во фре или /usr/src/linux/net/core/flow.c в линуксе.

А еще полезно посмотреть, что происходит с хэшем при сильной нагрузке. Где-то в инете есть сравнение iptables, pf и ipfw (которая как раз хэш и использует, по крайней мере так там написано. Я сам исходники не смотрел) Очень интересное сравнение, надо заметить.