В статье «Алгоритмы. Часть 1.1. Динамические соединения» рассмотрена интересная задача уточнения сильно связных компонент графа в процессе добавления новых ребер. Приведено и подробно проанализировано целых четыре разных метода. И может сложиться впечатление, что лучший метод решения этой задачи на 1С определен и дальнейшее ускорение решения уже невозможно. Однако оказывается, что это не так. И если использовать подходящие для данной задачи структуры данных языка 1С, то можно получить еще более быстрое решение, которое, возможно, и нужно использовать на практике.
Структура данных, которую предлагается использовать, это коллекция «соответствие». В статье «Эффективная обработка данных в оперативной памяти за счет использования коллекции "соответствие"» было показано, как можно использовать эту коллекцию для эффективного представления графов. В данной задаче применен тот же принцип с той небольшой особенностью, что вместо «соответствия соответствий» для простоты использован «массив соответствий».
Впрочем, предисловие затянулось. Лучше сразу привести код. Вот он
Процедура Инициализация(ЧислоВершин) Экспорт
Связи = Новый Массив(ЧислоВершин);
Для Этого = 0 По ЧислоВершин - 1 Цикл
Связи[Этого] = Новый Соответствие;
Связи[Этого].Вставить(Этого)
КонецЦикла
КонецПроцедуры
Процедура Объединить(Ежа, Ужа) Экспорт
Если Связи[Ежа] <> Связи[Ужа] Тогда
Если Связи[Ежа].Количество() < Связи[Ужа].Количество() Тогда
Для Каждого Этого Из Связи[Ежа] Цикл
Связи[Ужа].Вставить(Этого.Ключ);
Связи[Этого.Ключ] = Связи[Ужа]
КонецЦикла
Иначе
Для Каждого Этого Из Связи[Ужа] Цикл
Связи[Ежа].Вставить(Этого.Ключ);
Связи[Этого.Ключ] = Связи[Ежа]
КонецЦикла
КонецЕсли
КонецЕсли
КонецПроцедуры
Функция ОбъектыСоединены(Ёж, Уж) Экспорт
Возврат Связи[Ёж] = Связи[Уж]
КонецФункции
Как и в исходном решении, объекты идентифицируются числами. Для их обработки используется массив Связи, в котором каждому объекту сопоставлен элемент с соответствующим номером. Каждый элемент массива хранит ССЫЛКУ на соответствие, которое содержит номера объектов, связанных с этим элементом.
Чтобы проверить, что объекты А и Б входят в одну компоненту связности, достаточно убедиться, что Связи[А] = Связи[Б]. – Наглядно, не правда ли?
При добавлении очередного ребра сначала проверяется, принадлежат ли его концы Ёж и Уж одной компоненте сильной связанности. Если да, то ничего делать не нужно.
Если нет, то все номера, связанные с "ежом" из левого соответствия Связи[Ежа], добавляются к правому соответствию Связи[Ужа], а перечисленные элементы массива заменяются на элемент Связи[Ужа].
Поскольку выгоднее присоединять меньшее соответствие к большему, то производится «балансировка» присваивания. Для этого мощности коллекций сравниваются и в качестве левой (добавляемой) коллекции берется коллекция с меньшим количеством элементов.
Обратите внимание на присваивание соответствий, которое производится не путем создания копии соответствия, а копированием ССЫЛКИ. Для понимания этого процесса попробуйте предположить, что будет выведено в окно сообщений при выполнении вот такого фрагмента кода:
Трус = Новый Соответствие;
Трус["Крик"] = "Ой, мама!";
Балбес = Трус;
Балбес["Крик"] = "Ура!";
Сообщить(Трус["Крик"])
Если вашим предположением было «Ура!», то можете читать дальше, поверив, что «this is not a bug, this is a feature», как сказал бы американский преподаватель. Еще один тонкий момент - это подмена коллекции внутри цикла по элементам этой коллекции. В том, что это работает, убедимся, проверив работу следующего фрагмента кода:
ВотЭтоДа = Новый Соответствие;
ВотЭтоДа.Вставить("Вот");
ВотЭтоДа.Вставить("это");
ВотЭтоДа.Вставить("да!");
Для Каждого Этого Из ВотЭтоДа Цикл
ВотЭтоДа.Очистить();
Сообщить(Этого.Ключ)
КонецЦикла
На Фиг.1 изображена схема метода. Показано, что происходит, если при существующих двух компонентах связности {a, b, c} и {d, e} добавляется связь (a, d). Очевидно, компоненты объединяются, а ссылки в ячейках d и e переопределяются общей ссылкой.
Проверка быстродействия предлагаемого подхода показывает более чем двукратное ускорение решения задачи. Посмотрите график на Фиг.2.
Предлагаемый вариант обозначен цифрой 1 и показан на графике красным. Выше него идет самый быстрый метод из исходной статьи.
К статье приложена обработка, которая позволяет проверить удтверждения данной статьи относительно сравнительного быстродействия методов, правильности работы предлагаемого алгоритма и результатов выполнения приведенных "сомнительных" фрагментов кода.
Выводы заключаются в том, что
- Если требуется работать с графами, очень удобным и эффективным является использование коллекции "соответствие";
- При максимизации быстродействия не стоит забывать о втором слагаемом формулы "программы = алгоритмы + структуры данных".