Динамическая структура прямой адресации.
Автор Семенов М.Б. Кострома, Россия 2007г.
В данной статье пойдет речь об оптимизации структур данных.
В связи все большими гигагерцами и растущими объемами памяти оптимизация структур данных... зачем?
В области больших объемов хранимых данных, обсчета глобальных процессов (природных?) со многими
неизвестными, перебора игровых комбинаций используется скорее всего не "1С-ка". Попробовать свои силы?
Читая статью svsrus //infostart.ru/articles/230/ решился исследовать эту тему.
В частности, в рассмотренной статье используется таблица значений (кол-во строк : кол-во столбцов)
для хранения значений, раскиданных по "площади". И чем больше эта площадь, тем больше надо будет
памяти. (для ТЗ 1000 х 1000 это 80мб). И скорее всего, из задействованного адресного пространства
для хранения будет использовано не более одного процента. Что же можно предпринять?
Первый вариант: можно добавлять в ТЗ строки и столбцы по мере увеличения адреса значений.
Это можно использовать, если известно, что поступающие в структуру значения первоначально будут
с "маленькими" адресами. В противном случае при первом же поступлении значения с адресом 1000:1000
ТЗ достигнет максимального размера.
Второй вариант: использовать структуры без адресации, например, список значений. Значения из СЗ будем
получать по "представлению" адреса в виде "<НомерСтроки>:<НомерСтолбца>". Подойдет для небольших объемов
СЗ, все-таки поиск значения методом перебора "Получить()" работает медленно. Можно воспользоваться
объектом XBase и на его основе построить структуру аналогичную СЗ, но с индексированным адресом.
Считаю, что это "быстрое" и экономное решение, к тому же достаточно легкое в реализации.
Третий вариант, собственно, сама тема. Идея почти такая же как и в первом варианте - увеличивать
нашу ТЗ по мере поступления значений, только их адреса предварительно пропускать через
"функцию переадресации", уменьшающую количество разрядов реального адреса в ТЗ. Предположу, что такая
"переадресация" очень широко используется в ВТ на аппаратном и на низком уровне программирования.
На примере "площади" это выглядело бы примерно так:
1. Квадрат 25 х 25 разбиваем на подквадраты 5 х 5.
2. Функция переадресации преобразует прямые координаты в <НомерПодквадрата> и <НомерЯчейкиВподквадрате>, причем
нумерация подквадратов и ячеек в них выполняется последовательно по мере поступления новых адресов.
3. Используем полученные координаты как прямые. И будем расширять нашу структуру по мере увеличения адресов.
Во внешней обработке показана упрощенная "одномерная" реализация, используется только "НомерПодквадрата",
основная таблица для хранения данных увеличивается "порциями", - "подквадратами", которые добавляются
вниз таблицы.
Основные функции "переадресации" взамен встроенных методов "ПолучитьЗначение()" и "УстановитьЗначение()":
"ПолучитьЗначТЗ()" и "УстановитьЗначТЗ()" с теми же параметрами.
Для особо больших объемов можно использовать аналогичную перадресацию и для структуры данных в самой
функции переадресации. На любителя рекурсий. :)
Успехов!
29.10.2007
Добавлена внешняя обработка DinTVMultiLevel.ert - развитие идеи, предложенной Fixin,
ее суть: функцию переадресации сделать "жесткой", без использования в ней же дополнительных
структур данных, - "правила" адресации будут "зашиты там же, в основной структуре данных.
В обработке используется объект "ТаблицаЗначений", работа с ним производится след. образом:
НомерСтроки два младших разряда текущего адреса
Колонка 1 (без имени) - значение по указанному конечному адресу (или самым старшим разрядам от него)
Колонка 2 "Ссылка" - ссылка на объект "ТаблицаЗначений" для доступа к значениям с дополнительными
старшими разрядами адреса (новый уровень ТЗ)
На примере это будет выглядеть так:
получить значение по адресу 15: ТЗ.ПолучитьЗначение(15,1);
получить значение по адресу 115: ТЗ.ПолучитьЗначение(15,"Ссылка").ПолучитьЗначение(01,1);
получить значение по адресу 340115:
ТЗ.получитьЗначение(15,"Ссылка").ПолучитьЗначение(1,"Ссылка").ПолучитьЗначение(34,1);
Адресация сделана одномерной, как в массиве, однако, ничто не мешает ее использовать для
структур с несколькими измерениями с предварительным приведением всех адресов измерений к одному.
Параметры функций и процедур изменены, см. в коде обработки.
