Каталог решений - Эффективная обработка данных в оперативной памяти за счет использования коллекции соответствие

1. Место коллекции «соответствие» среди других универсальных коллекций значений.

Мы знаем, что: 

массив предназначен для доступа к элементам массива; 

структура используется для хранения небольшого количества значений, каждое из которых имеет некоторое имя;

список значений — это не сохраняемый в базе данных объект, который позволяет строить динамические наборы значений и манипулировать ими;

таблица значений — почти тоже, что список, только еще с колонками. 

А вот про соответствие в хелпе написано только что данный объект «Представляет доступ к соответствию».

Не собираюсь поправлять техписателей 1С — другого определения давать не буду.

С моей точки зрения, соответствие занимает промежуточное положение между структурой и массивом, с одной стороны, и списком и таблицей значений, с другой, объединяя хорошие черты этих коллекций.

Все коллекции хранят множества элементов. Структура позволяет получить нужный элемент по имени, массив — по номеру, список и таблица значений — поиском (отбором) среди других элементов. А соответствие позволяет выбрать или изменить нужный элемент по «ключу» этого элемента. При этом в качестве ключа может использоваться значение почти любого типа (например, ссылка). Возможность выбора и изменения по ключу дает возможность обрабатывать заранее неизвестное количество элементов, при этом никак их не нумеруя. Получаем практически таблицу значений, проиндексированную по колонке «ключ».

И вот тут, думаю, для многих будет сюрпризом, что доступ к элементу соответствия по ключу происходит почти со скоростью доступа к массиву или элементу структуры! — Как будто по номеру!

Приведем пример:

Будем подавать на вход обработки случайные числа в диапазоне от 1 до КоличествоРазличныхЭлементов.  Обработка должна будет проверять каждое число, чтобы определить: не встречалось ли очередное число в текущей последовательности раньше. Если такого числа не было — оно добавляется в коллекцию, иначе — увеличивается число его повторений.

То есть оценивается время выполнения конструкции «…» в цикле (фиг1)

В качестве конструкции «…» используется:

Вариант 1. Массив (фиг2)

Вариант 2. Соответствие (фиг3)

Вариант 3. Индексированная ТаблицаЗначений (фиг4)

Результаты сравнения показали, что отметка в массиве занимает на тестовом компьютере 2,45 мкс, в соответствии — 7,06 мкс, в индексированной таблице значений — 15,06 мкс, причем это время не зависит от числа элементов в коллекции! Прилагаемый к статье отчет «БыстродействиеКоллекций» позволит Вам перепроверить эти результаты. 

Скорость доступа к элементам соответствия и независимость скорости доступа от размера коллекции «соответствие» может удивлять, если не догадываться о ее устройстве. Можно предположить, что используется хеш-функция и хеш-таблица. Хеш-функция вычисляет номер строки хеш-таблицы, где лежит ссылка на элемент. Простая косвенная адресация! Одно лишнее (по сравнению с массивом) обращение к памяти! 

При использовании для решения этой задачи списка значений, неиндексированной таблицы значений или добавления чисел в таблицу значений без контроля повторений с последующей сверткой, получаются существенно более плохие результаты. Которые, к тому же, зависят от размеров коллекций . При этом самые лучшие результаты среди аутсайдеров дает свертка.

В комментариях к статье также уже посоветовали отметить, что еще одна прелесть соответствия в том, что перед присваиванием Соответствие[Ключ] = Значение не нужна проверка на существование элемента с этим ключом, так как отсутствующий элемент в этом случае вставляется в соответствие. В приведенных примерах этому красивому приему, к сожалению, места не нашлось.

2. Пример использования соответствия в задаче подсчета повторений слов.

Приведем пример программы, подсчитывающей число повторений каждого слова в заданном тексте. Обычное решение — запоминание отдельных слов в строках таблицы значений и последующая свертка по полю «Слово». Соответствие ускоряет основную операцию в этом алгоритме минимум в два раза! При этом получается не только самый быстрый, но и выразительный код. Чтобы учесть, что слово, прочитанное в переменную «Слово» строкового типа,  встретилось еще раз, используется наглядная запись: Частота[Слово] = Частота[Слово] + 1. Правда, чтобы определить, что символ является буквой, использовать соответствие будет уже неправильно: встроенная функция поиска подстроки работает быстрее!

Текст программы приведен на фиг5 и в приложенном к статье отчете «ЧастотаСлов», позволяющем проанализировать любой текстовый файл.

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

3. Пример использования соответствия в задаче представления ориентированного графа.

Если стоит задача сохранить в оперативной памяти и проанализировать связи объектов информационной базы, то эффективной оказывается использование следующей структуры: Соответствие «Граф» хранит связи объекта, ссылка на который определяется ключом. Значением соответствия «Граф» является вложенное соответствие «Связи», которое для каждого связанного элемента хранит вес связи.  

Например, если переменные «Элемент1» и «Элемент2» хранят ссылки на два элемента справочника «Номенклатура», причем второй входит в спецификацию первого с весом 2, то выражение

Граф[Элемент1][Элемент2] будет равно 2. 

Если связи нет, то выражение Граф[Элемент1][Элемент2] будет равно «Неопределено«.

Если нужно сделать вес связи равным 1, это сделает следующий код: Граф[Элемент1][Элемент2] = 1.

При этом Элемент1 и Элемент2 могут быть как ссылкой на справочник, так и ссылкой на документ и другие объекты. То есть так можно обрабатывать любые связи!

Стоит предупредить, что обращаться к элементам вложенного соответствия можно только, если во внешнем соответствии существует ключ первого элемента. Поэтому перед обращением к связям требуется проверка Граф[Элемент1] <> Неопределено.

На фиг6 приведен фрагмент кода программы, который производит чтение из базы данных в оперативную память связей номенклатуры, задаваемых в конфигурации «Бухгалтерия предприятия» в справочнике «СпецификацииНоменклатуры».

Текст самой обработки (разузлования) графа спецификаций БП, построенной целиком на соответствиях, Вы можете загрузить по ссылке к статье [//sale.itcity.ru/public/78371/]. Там всего десяток строк!

Заключительные замечания.

1. Ничего нового здесь не изобретено, просто делюсь опытом. Сам узнал о сравнительной эффективности коллекций из статьи Сергея Осипова. Спасибо ему!

2. Использование соответствия в решении задач позволяет исключить поиск при обработке заранее непронумерованных данных. Таким образом существенно ускоряется реализация многих базовых алгоритмов. Пользуйтесь соответствием в случаях, когда не нужен весь функционал таблиц значений!

3. Несмотря на ориентированность языка 1С на решение бизнес-задач, в нем есть место настоящему программированию — кодингу, в том числе и самому хитроумному. Поэтому изучайте теорию алгоритмов и программ, не мусорьте в коде и сможете сберечь нервы и время пользователей, строки кода, место на дисках, циклы процессора, электроэнергию. Делайте мир лучше!