gifts2017

Алгоритмы. Часть 1.1. Динамические соединения.

Опубликовал Алексей Бочков (Aleksey.Bochkov) в раздел Программирование - Работа с интерфейсом

Конспект первой лекции из свежего курса Принстонского университета США за 2014 год.
Вольный перевод с английского с реализацией примеров на 1С.
Курс в целом достаточно интересный и полезный для общего развития.
Перевел и адаптировал только первую лекцию (в 1 части 11 лекций, 2 часть - еще не завершена преподавателями).
Первоисточник на английском - https://www.coursera.org/course/algs4partI.
Если сообщество посчитает материал полезным - займусь переводом следующих лекций (но это довольно трудоемко).
Enjoy! :)

Алгоритмы – это методы решения проблем. Алгоритмы применяются практически в любой области человеческой деятельности. Умение составлять правильные и эффективные алгоритмы является важным качеством любого специалиста практически из любой области.

«Я считаю, что разница между плохим и хорошим программистом в том – считает ли он свой код или структуры данных более важными. Плохой программист заботится о коде. Хороший программист – о структуре данных и их взаимосвязях».
Линус Торвальдс

«Алгоритмы + структуры данных = программы».
Никлаус Вирт

 

Зачем изучать алгоритмы?

  1. Они имеют очень широкое распространение и влияние.
  2. Имеют глубокие корни и предоставляют широкие возможности.
  3. Помогают решить проблемы, которые не могут быть решены иным путем.
  4. Помогают стать хорошим программистом.
  5. Они могут раскрыть секреты жизни и вселенной.
  6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.

Лекция 1. Соединение-поиск.

Порядок преподнесения материала в лекциях:

  1. Сформулировать проблему/задачу.
  2. Найти алгоритм решения
  3. Достаточно ли он быстр? Достаточно ли памяти?
  4. Если нет – понять почему.
  5. Найти пути оптимизации.
  6. Повторить пока не будем удовлетворены результатом.

Так называемый Научный метод

Динамические соединения.

Допустим мы имеем массив из N объектов, а также 2 команды:
1. Процедура Объединить – создает соединение между двумя объектами.
2. Функция ОбъектыСоединены – проверяет наличие пути, который объединяет 2 объекта.

 

Пример задачи: существует ли путь, соединяющий точки p и q?
(поиск конкретного пути в данной лекции не рассматривается!)

Будем считать, что тезис «объект p соединен с объектом q» включает в себя следующие утверждения:

  • p соединен с p, т.е. объединен сам с собой;
  • если p соединен с q, то q соединен c p;
  • если p соединен с q и q соединен с r, то p соединен с r.

Коллекция соединенных объектов – перечень всех объектов, объединенных в единую сеть.

Таким образом, операция проверки наличия пути между объектами сводится к проверке принадлежности 2 объектов одной коллекции. А операция объединения объектов – к объединению двух коллекций.

 

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

1 методика. Быстрый поиск.

Алгоритм, который обеспечит максимально быструю проверку наличия связи между двумя объектам.

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

Например:

представлены 3 коллекции:

  • 0, 5 и 6 – коллекция с индексом 0
  • 1, 2 и 7 – коллекция с индексом 1
  • 3, 4, 8 и 9 – коллекция с индексом 8

Логика работы операций:

ОбъектыСоединены(p, q) – проверить равенство идентификаторов у элементов с индексами p и q. Если идентификаторы равны – объекты соединены, иначе – нет.

Объединить(p, q) – объединить 2 коллекции – заменить у всех элементов идентификаторы q на p.

Например, выполним объединение объектов 6 и 1 (помимо 6 необходимо переподчинить объекты 0 и 5, т.к. они были связаны с 6):

И сразу видим проблему – пришлось изменить идентификаторы у большого числа объектов.

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

 

При этом операция объединения слишком затратная. Она требует N^2 доступов к массиву для выполнения последовательности из N команд для N объектов.

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

Грубый пример: процессор выполняет 10^9 операций в секунду, для доступа к 10^9 объектам в памяти требуется 1 секунда. Но для выполнения 10^9 команд объединения по алгоритму быстрого поиска потребуется более 10^18 операций. Более 30 лет компьютерного времени.
Можно взять компьютер в 10 раз более производительный, но в 10 раз большая задача будет решаться в 10 раз медленнее!

Реализация в 1С:

См. обработку «БыстрыйПоиск»

2 методика. Быстрое объединение.

Алгоритм, который обеспечит максимально быстрое объединение двух объектов.

В этом случае изменим схему хранения связей - в значениях массива будут храниться индексы ближайших связанных объектов: id[i] это родитель для i.
А для вычисления корня потребуется рекурсия id[id[id[...id[i]...]]]

Логика работы операций:

ОбъектыСоединены(p, q) – проверить что элементы с индексами p и q имеют один и тот же корень.

Объединить(p, q) – добавить корневой элемент первой коллекции к корневому элементу второй коллекции.

Например, выполним объединение объектов 3 и 5:

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

Быстрое объединение (худший вариант)

N

N

N

 

Дефекты быстрого поиска:

  • Объединение слишком затратно
  • Деревья плоские, но слишком затратно поддерживать их таковыми

Дефекты быстрого объединения:

  • Деревья бывают очень высокими
  • Поиск слишком затратен.

Реализация в 1С:

См. обработку «БыстроеОбъединение»

 

Первое улучшение. Оценка веса.

Быстрое объединение с оценкой веса деревьев:

  1. Изменить предыдущий алгоритм там, чтобы избегать высоких деревьев.
  2. В отдельной структуре хранить размеры каждого дерева
  3. При объединении деревьев всегда присоединять малое дерево к корню большого (метрика рассчитывается исходя из числа узлов в дереве).

Пример результатов работы обоих методов:

Скорость выполнения операций объединения и проверки соединения в данном случае пропорциональна длине веток. Длина веток при этом не превосходит lg N.

Затраты. Число операций чтения и записи для массива размером N:

Алгоритм

Инициализация

Объединение

Проверка соединения объектов

Быстрый поиск

N

N

1

Быстрое объединение

N

N

N

Быстрое объединение с оценкой веса

N

lg N

lg N

 

Реализация в 1С:

См. обработку «БыстроеОбъединениеСОценкойВеса»

Второе улучшение. Сжатие пути.

Быстрое объединение со сжатием пути:

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

Например, для данного дерева при вычислении корня для объекта номер 9 будет выполнен перенос объектов 9, 6 и 3 к верхнему уровню.

Исходное дерево:

Результат:

На практике – нет причин не использовать этот метод. Он позволяет поддерживать дерево плоским.

Реализация в 1С:

См. обработку «БыстроеОбъединениеСоСжатиемПути»

Финальный вариант. Быстрое объединение с оценкой веса и сжатием пути.

Утверждение (Hopcroft-Ulman, Tarjan): начиная с пустой структуры данных любая последовательность операций объединения-поиска M для N объектов потребует =< c ( N + M lg* N ) числа доступов к массиву.

Где ln*N:

Итог.

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

Алгоритм

Максимальное время выполнения (максимальное число доступов к массиву)

Быстрый поиск

M N

Быстрое объединение

M N

Быстрое объединение с оценкой веса

N + M log N

Быстрое объединение со сжатием пути

N + M log N

Быстрое объединение с оценкой веса и сжатием пути

N + M lg* N

Где M – число операций объединения и проверки соединения для массива из N-объектов.

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

Графики времени выполнения алгоритмов в 1С.
Все 5 вариантов:

Без 1 и 2 варианта:

Пример применения алгоритма – вычисление проницаемости структуры.

Модель для множества физических систем:

  1. Фигура размером N*N из объектов
  2. Каждый объект является либо открытым (проницаемым) с вероятностью p, либо закрытым (непроницаемым) с вероятностью 1-p.
  3. Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда