Наш ответ американским лекторам

11.04.2014

Наш ответ американским лекторам

Это спойлер к замечательной публикации «Алгоритмы. Часть 1.1. Динамические соединения». Здесь описывается гораздо более быстрый способ решения задачи динамического связывания при отсутствии ограничений на используемые структуры данных

В статье «Алгоритмы. Часть 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 и показан на графике красным. Выше него идет самый быстрый метод из исходной статьи.

К статье приложена обработка, которая позволяет проверить удтверждения данной статьи относительно сравнительного быстродействия методов, правильности работы предлагаемого алгоритма и результатов выполнения приведенных "сомнительных" фрагментов кода. 

Выводы заключаются в том, что

1. Если требуется работать с графами, очень удобным и эффективным является использование коллекции "соответствие";
2. При максимизации быстродействия не стоит забывать о втором слагаемом формулы "программы = алгоритмы + структуры данных".

Текст публикации

Все новости