Правильный алгоритм захвата памяти под индексы


[ Пpишедшие ответы ] /www.hdru.com/wwwboard/faq.htm">Help ]

Posted by Рустем Мухаметшин on December 06, 1998 at 02:43:00:

In Reply to: Re: О ТОМ, KAK НА САМОМ ДЕЛЕ ИНДЕКСИРУЮТСЯ ДАННЫЕ В ФБП posted by Рустем Мухаметшин on December 04, 1998 at 12:00:07:

        Поразмыслив еще некоторое время я вывел правильный алгоритм захвата памяти под граф "цепи букв индексов".
1)    Базовым элементом является ячейка объемом 26 байт
2)    Под каждую букву в графе (не в индексах!!!) расходуется одна ячейка
3)    Плюс 2 ячейки расходуются под цепи (и подцепи) - проще говоря на само наличие уникального индекса
4)    Хотя сама топология стрелок в графе зависит от порядка регистрации индексов его общий объем от нее не зависит - поэтому сами стрелки в этом смысле не имееют значения

Поясню на примере Аркадия (см. первый рисунок)
Имеется 5 индексов - ALFA, ALPHA, ALL, ALLOW, BYE . Судя по стрелкам их ввод был в этом же порядке (хотя регистрацию некоторых можно и переставить). Нарисуем топологию графа согласно 4)
A  L  F  A
         P  H  A
         L  O  W
B  Y  E
Имеем 13 ячеек, добавляем 2 на 5 индексов (цепей) = 10 получаем 23-и ячейки. Итого 23*26=598 байт.

Все вышескзанное относится к случаю одного объекта (счета)
По всей видимости граф индексов общий для всех счетов. Если на уже имеющийся индекс в графе регистрируется еще один счет, то происходит захват еще одной ячейки, т.е если бы в вешеупомянутом примере все индексы были прикреплены к 2-м счетам Z,Y то расход памяти составил бы 13+2*5+5=28 ячеек.

        Из вышесказанного видно, Аркадий, что первоначальная формула
Индексы_ЭП  = 26*(L+3*N-1+[N/10]+[N/100]+[N/1000]+...), где L - длина идекса, N - количество индексов, [...] - целая часть
        Была недалека от истины - просто последняя группа слагаемых имела частный вид характерный проводившемуся эсперименту


        Быстродействие. Я промоделировал на С++ алгоритмы данной цепи и плоского массива. Действительно, быстродействие поиска по цепи во много раз больше того же по плоскому массиву. Поэтому применение подобного алгоритма мне кажеться целесообразным. Только хотелось бы что бы на ячейку уходило столько сколько ей положено - 13 байт и не было дополнительных расходов: 2 ячейки на индекс.

Скачайте тестовую настройку (9K)



Пpишедшие ответы: