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

Разработчики, перешедшие с 7-ки на 8-ку по привычке продолжают использовать универсальные коллекции "список значений", "таблица значений" в задачах, которые в 8-ке существенно быстрее решаются с использованием новой коллекции "соответствие". Эта статья для тех, кто еще не оценил всех преимуществ новой структуры данных. Статья позволит создавать Вам максимально быстрые программы. Приведено несколько примеров, в том числе, решение для задач на графах.

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 приведен фрагмент кода программы, который производит чтение из базы данных в оперативную память связей номенклатуры, задаваемых в конфигурации "Бухгалтерия предприятия" в справочнике "СпецификацииНоменклатуры".



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

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

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

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



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