gifts2017

Как организовать хранение данных с большим адресным пространством, оставив "прямую" адресацию?

Опубликовал Михаил Семенов (Shaman100M) в раздел Программирование - Практика программирования

Это статья про то, как найти альтернативу Перем Массив[10 000 000], уменьшить выделение памяти для структур с многоразрядными адресами, оставив при этом "прямую" адресацию.
Две внешние обработки - примеры реализации двух подходов на объекте "ТаблицаЗначений".

Динамическая структура прямой адресации.
Автор Семенов М.Б. Кострома, Россия 2007г.

В данной статье пойдет речь об оптимизации структур данных.
В связи все большими гигагерцами и растущими объемами памяти оптимизация структур данных... зачем?
В области больших объемов хранимых данных, обсчета глобальных процессов (природных?) со многими
неизвестными, перебора игровых комбинаций используется скорее всего не "1С-ка". Попробовать свои силы?
Читая статью svsrus http://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);



Адресация сделана одномерной, как в массиве, однако, ничто не мешает ее использовать для
структур с несколькими измерениями с предварительным приведением всех адресов измерений к одному.

Параметры функций и процедур изменены, см. в коде обработки.

Скачать файлы

Наименование Файл Версия Размер
Пример 52
.1193390055 5,32Kb
25.09.09
52
.1193390055 5,32Kb Бесплатно
Многоуровневая ТЗ 44
.1193652719 9,50Kb
25.09.09
44
.1193652719 9,50Kb Бесплатно

См. также

Подписаться Добавить вознаграждение
Комментарии
2. Михаил Семенов (Shaman100M) 26.10.07 16:14
(1) Да, наверно это почти также, но проще. Но организовать в 1с-ке массив массивов? Это как? Таблицу таблиц можно. И, в основании (1) это будет выглядеть так:

6-значный адрес ячейки: abcdef переводим в 100-ичную систему ab cd ef,
а дальше (при наличии всех созданных таблиц):
Код
ТЗ.ПолучитьЗначение(ab+1,1).ПолучитьЗначение(cd+1,1).ПолучитьЗначение(ef+1,1); 
Показать полностью

ну, добавить все проверки...
3. Аркадий Кучер (Abadonna) 27.10.07 05:47
На мой вкус такие разработки гораздо интереснее, чем "Отчет по сотрудникам, выпивающим более 2-х раз в неделю" ;) Плюс
vasilykushnir; das; +2 Ответить 2
4. Михаил Семенов (Shaman100M) 27.10.07 10:01
(3) :) Доброе утро.
Интересно, было бы посмотреть на ТЗ такого отчета: в рабочее/ не рабочее время, место, с кем, итого грамм, вес, количество "пронесло" и "попал"...
Ну лана, все равно это работа для другого программиста: "сб-сника". :)
5. Михаил Семенов (Shaman100M) 29.10.07 13:27
Добавил реализацию многоуровневой ТЗ, см. комментарии (1) и (2)
6. VasilyKushnir (vasilykushnir) 24.12.07 14:39
(3) Полностью согласен и даже плюсика не жалко.