Binary Tree
Текущий рейтинг темы: Нет
wsx
Участник Проекта
Юниксойд, сетевик
 Откуда: Казань Всего сообщений: 1074 Рейтинг пользователя: 28 Репутация пользователя: 1Дата регистрации на форуме: 14 янв. 2005 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 4 июля 2006 14:14
Как построить бинарное дерево на основе 4 октетных данных вида "127.0.0.1"(например, но их множество) и обойти его при помощи логики двоичного логарифма?
ессно дело юзается Перл.
точнее сказать есть строка вида 10.0.0.52 надо найти аналогичное значение в этом дереве, тоесть например если в нём есть 10.0.0.0/24, то срабатывает процедура, если же ни чего не найдено то срабатывает другая процедура.
Массивы не предлагать, т.к. они будут отрабатываться дольше, а время - критично; | | | |
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
 Откуда: Москва Всего сообщений: 2994 Рейтинг пользователя: 79 Дата регистрации на форуме: 29 сен. 2001 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 4 июля 2006 16:47
Оффтопик: Тут я тебе вряд ли чем смогу помочь: с бинарными деревьями сам не очень хорошо знаком...
---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
| | | |
wsx
Участник Проекта
Юниксойд, сетевик
Откуда: Казань Всего сообщений: 1074 Рейтинг пользователя: 28 Репутация пользователя: 1Дата регистрации на форуме: 14 янв. 2005 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 5 июля 2006 10:24
Вот, кое что нашёл. Но пока разобраться не могу, как это можно использовать...
use Tree::Binary;
# a tree representaion of the expression:
# ((2 + 2) * (4 + 5))
my $btree = Tree::Binary->new("*")
->setLeft(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("2"))
->setRight(Tree::Binary->new("2"))
)
->setRight(
Tree::Binary->new("+")
->setLeft(Tree::Binary->new("4"))
->setRight(Tree::Binary->new("5"))
);
# Or shown visually:
# +---(*)---+
# | |
# +-(+)-+ +-(+)-+
# | | | |
# (2) (2) (4) (5)
# get a InOrder visitor
my $visitor = Tree::Binary::Visitor::InOrderTraversal->new();
$btree->accept($visitor);
# print the expression in infix order
print $visitor->getAccumulation(); # prints "2 + 2 * 4 + 5"
# get a PreOrder visitor
my $visitor = Tree::Binary::Visitor::PreOrderTraversal->new();
$btree->accept($visitor);
# print the expression in prefix order
print $visitor->getAccumulation(); # prints "* + 2 2 + 4 5"
# get a PostOrder visitor
my $visitor = Tree::Binary::Visitor::PostOrderTraversal->new();
$btree->accept($visitor);
# print the expression in postfix order
print $visitor->getAccumulation(); # prints "2 2 + 4 5 + *"
# get a Breadth First visitor
my $visitor = Tree::Binary::Visitor::BreadthFirstTraversal->new();
$btree->accept($visitor);
# print the expression in breadth first order
print $visitor->getAccumulation(); # prints "* + + 2 2 4 5"
# be sure to clean up all circular references
$btree->DESTROY();
http://search.cpan.org/~stevan/Tree-Binary-0.07/lib/Tree/Binary.pm
Пожалуй пока на массивах сделаю, тачка выдержит, а затем уже потихоньку на бинарное дерево буду переделывать. | | | |
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
Откуда: Москва Всего сообщений: 2994 Рейтинг пользователя: 79 Дата регистрации на форуме: 29 сен. 2001 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 5 июля 2006 12:38
Тебе для твоей задачи, видимо, больше подойдет не Tree::Binary, а Tree::Binary::Search.
А процедуру, которая будет преобразоывать конкретный IP-адрес в адрес подсети, скорее всего, придется писать самому, или искать отдельный модуль, напрямую с Tree не связаный....
Оффтопик: А я-то думал, ты сам собираешься дерево реализовывать...
---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
| | | |
wsx
Участник Проекта
Юниксойд, сетевик
Откуда: Казань Всего сообщений: 1074 Рейтинг пользователя: 28 Репутация пользователя: 1Дата регистрации на форуме: 14 янв. 2005 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 5 июля 2006 13:36
Я похож на извращенца ? Процедуру я уже пишу, точнее пишу функции нахождения минимлаьного и максимального ИП адреса в заданной сети(заданная сеть пример: 10.1.1.1/29)
Ок, сейчас гляну что к чему.Я вот ещё думаю, а может быть ХЕШ по генереить? не будет лиэто проще для дерева или всё таки затраты на вычисления хеша(аля сдвигов) будут слишком велики? | | | |
4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
Откуда: Москва Всего сообщений: 2994 Рейтинг пользователя: 79 Дата регистрации на форуме: 29 сен. 2001 |
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 5 июля 2006 14:11
На извращенца как раз иногда бываю похож я, т.к. терпеть не могу использовать чужой код (за исключением функций, изначально встроенных в язык).
Оффтопик: Вот поэтому я и люблю PHP — там их много...
Зачем тебе хеш? Я тут посмотрел документацию на Tree::Binary::Search и пришел к выводу, что тебе нужно сделать вот что: написать процедуру, которая берет конкретный IP-адрес и адрес сети и сравнивает их (причем не только на равенство, но и на больше/меньше) и "подвесить" ее к дереву с помощью setComparisionFunction (или что-то в этом роде). И тогда все будет работать как надо...
---
Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
| | | |
Время выполнения скрипта: 0.0670. Количество выполненных запросов: 18, время выполнения запросов 0.0264
|
