Построение байтового дерева для сверхбыстрого поиска.

Задача формулировалась так: Имеется список звонков или один звонок.
Звонок содержит в себе тариф и номер, но заранее не известна длина тарифа. Например 845678606708 : 8-это международный код 45678 - тариф 606708-телефон. В базе тарифов могут присутствовать тарифы 45, 456, 45678 и нужно выбрать самый длинный (максимальный тариф). Соответственно поиск по индексу не подходит, необходим перебор вариантов, то есть для каждого звонка необходимо перебрать все тарифы. У меня было 500 тарифов и 100000 звонков. В результате получается 500*100,000=50,000,000 операций. Можно это сделать с оптимизацией, но все равно необходим перебор вариантов. У меня операция пересчета занимала 1 час. Поэтому я решил прикинуть тарифы в память, а поиск выполнять во время считывания звонка и записывать ID тарифа. Этим я убивал сразу 2 зайцев. Скорость поиска тарифа сокращалась почти до нуля, и упрощался алгоритм пересчета. Весь пересчет сводился к заурядному SQL-запросу плюс функция расчета цены. Но поскольку к скорости сохранения данных предъявляются весьма жесткие требования, алгоритм должен быть весьма быстрым! Я посмотрел различные источники, подумал о бинарных деревьях и решил, что мне это не подходит. Немного подумав, создал свое дерево, в нем каждый элемент дерева представлен одним байтом 0 до 9; разумеется, мне нужно всего 4 бита, но для операций сравнения удобней использовать весь байт. Вот пример узла дерева
sNode = packed record Item: Byte; ID: Word; Point: Array of Word; end;

Item - это элемент дерева от 0 до 9

• ID - Идентификатор тарифа
• Point - динамический массив состоящий из указателей на дочерние узлы

Я выбрал динамический массив для хранения дерева как наиболее удобный и экономичный способ хранения. При использовани масива мы икономим 2 байта на указателе, это накладывает ограничение на количество элементов масива 65535. Если необходимо больше, то можно заменить индекс адресом. Но при этом обций размер масива увеличится в 3-4 раза.

При таком посторении дерева экономится память. То есть, для нахождения тарифа 82345 надо сделать 4 шага от корня и при каждом шаге проверять содержание дочерних элементов для нахождения нужной ветки. Если при построении дерева встречаются два похожих тарифа типа 82346, то добавляется только узел 6. Этим экономится много памяти. Все остальное вместе с примерами можно найти в архиве. Там релизован класс TsmallTree который имеет необходимые методы

procedure AddArray(Var Tarif: Array of ShortString); строит дерево из массива procedure AddElement(Key: ShortString; ID: Cardinal); function Find(Key: ShortString): Word; procedure RecursiveBeat(AProc: TBuildNode); создает указатель на процедуру. procedure ShowTree; - вызывает эту процедуру для каждого узла(я использовал при отладке) В секцию public вынесены две переменные Step: Word; - а это как следует из названия шаг увеличения памяти. List: Array of sNode; - это само дерево

Поскольку при построении дерева количество элементов обычно больше 100, то невыгодно прибавлять по 1 элементу (очень медленно). Поэтому я сделал, как обычно в этих случаях, свой менеджер, который при превышении границы массива прибавляет N элементов. Я советую величину шага ставить на порядок меньше элементов масива. То есть Array:1000 Step:100, Array:10000 Step:1000 , тогда нет торможения программы.

У меня при 10000 элементах все работало нормально, но при 12000 начинались какие-то проблемы, возможно, это связано с теоретическим пределом в 65535 узлов дерева.

В описании упоминаются два массива - один массив строк (исходный материал для построения), другой масив - это само дерево, не перепутайте!

сентябрь 2001г.
Специально для

Скачать файлы проекта :

• Исходные коды (6K)
• Исполняемый файл (190K)