Вольный перевод с английского с реализацией примеров на 1С.
Курс в целом достаточно интересный и полезный для общего развития.
Перевел и адаптировал только первую лекцию (в 1 части 11 лекций, 2 часть — еще не завершена преподавателями).
Первоисточник на английском — https://www.coursera.org/course/algs4partI.
Если сообщество посчитает материал полезным — займусь переводом следующих лекций (но это довольно трудоемко).
Enjoy! 🙂
Алгоритмы – это методы решения проблем. Алгоритмы применяются практически в любой области человеческой деятельности. Умение составлять правильные и эффективные алгоритмы является важным качеством любого специалиста практически из любой области.
«Я считаю, что разница между плохим и хорошим программистом в том – считает ли он свой код или структуры данных более важными. Плохой программист заботится о коде. Хороший программист – о структуре данных и их взаимосвязях».
Линус Торвальдс«Алгоритмы + структуры данных = программы».
Никлаус Вирт
Зачем изучать алгоритмы?
- Они имеют очень широкое распространение и влияние.
- Имеют глубокие корни и предоставляют широкие возможности.
- Помогают решить проблемы, которые не могут быть решены иным путем.
- Помогают стать хорошим программистом.
- Они могут раскрыть секреты жизни и вселенной.
- Для саморазвития, интеллектуальной стимуляции и хорошего заработка.
Лекция 1. Соединение-поиск.
Порядок преподнесения материала в лекциях:
- Сформулировать проблему/задачу.
- Найти алгоритм решения
- Достаточно ли он быстр? Достаточно ли памяти?
- Если нет – понять почему.
- Найти пути оптимизации.
- Повторить пока не будем удовлетворены результатом.
Так называемый Научный метод
Динамические соединения.
Допустим мы имеем массив из 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#k8SjZc9Dxk2 доступов к массиву для выполнения последовательности из N команд для N объектов.
Алгоритм получился квадратичным. А квадратичные алгоритмы не масштабируются, даже с учетом развития технологий.
Грубый пример: процессор выполняет 10#k8SjZc9Dxk9 операций в секунду, для доступа к 10#k8SjZc9Dxk9 объектам в памяти требуется 1 секунда. Но для выполнения 10#k8SjZc9Dxk9 команд объединения по алгоритму быстрого поиска потребуется более 10#k8SjZc9Dxk18 операций. Более 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С:
См. обработку «БыстроеОбъединение»
Первое улучшение. Оценка веса.
Быстрое объединение с оценкой веса деревьев:
- Изменить предыдущий алгоритм там, чтобы избегать высоких деревьев.
- В отдельной структуре хранить размеры каждого дерева
- При объединении деревьев всегда присоединять малое дерево к корню большого (метрика рассчитывается исходя из числа узлов в дереве).
Пример результатов работы обоих методов:
Скорость выполнения операций объединения и проверки соединения в данном случае пропорциональна длине веток. Длина веток при этом не превосходит lg N.
Затраты. Число операций чтения и записи для массива размером N:
|
Алгоритм |
Инициализация |
Объединение |
Проверка соединения объектов |
|
Быстрый поиск |
N |
N |
1 |
|
Быстрое объединение |
N |
N |
N |
|
Быстрое объединение с оценкой веса |
N |
lg N |
lg N |
Реализация в 1С:
См. обработку «БыстроеОбъединениеСОценкойВеса»
Второе улучшение. Сжатие пути.
Быстрое объединение со сжатием пути:
- При каждом вычислении корня выполним привязку всех глубоко вложенных объектов к корню.
- Это потребует только 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 варианта:
Пример применения алгоритма – вычисление проницаемости структуры.
Модель для множества физических систем:
- Фигура размером N*N из объектов
- Каждый объект является либо открытым (проницаемым) с вероятностью p, либо закрытым (непроницаемым) с вероятностью 1-p.
- Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда
Зависимость проницаемости структуры от вероятности проницаемости каждого объекта (p).
При большом числе N теория гарантирует наличие четкого порога p*, при котором:
- если p > p* — структура почти наверняка проницаема
- если p < p* — структура почти наверняка непроницаема.
p* получено путем симуляции на больших массивах данных и не доказано математически:
Симуляция по методу Монте-Карло для вычисления p*.
http://ru.wikipedia.org/wiki/%CC%E5%F2%EE%E4_%CC%EE%ED%F2%E5-%CA%E0%F0%EB%EE
- Создать структуру N*N из закрытых клеток.
- Последовательно и случайно открывать закрытые клетки до тех пор, пока верхний ряд не будет соединен с нижним рядом.
- Процент открытых клеток даст значение p*
Применение алгоритма динамических соединений для определения проницаемости структуры.
1) Создать структуру N*N и последовательно определить для каждой клетки элемент в массиве:
2) Выполнить объединение соседних открытых клеток:
3) Структура будет проницаемой, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда. Для упрощения проверки добавим виртуальные вершины для верхнего и нижнего ряда. Проверка будет сведена к единственной операции проверки связи между двумя вершинами:
Симулируем открытие случайной клетки. Необходимо проверить всех «соседей» и выполнить соединение с теми из них, которые уже открыты.
Во вложенной конфигурации 1С приведена реализация данного подхода.
P.S. — если обнаружите нестыковки, ошибки — пишите в комментариях, я поправлю.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Очень полезно! Спасибо автору за перевод, надеюсь на продолжение.
Это не просто полезно, это просто архиполезно. С огромным удовольствием прочитаю продолжение. Давно хочу заняться изучением алгоритмов, тк это логичное развитие программиста…но что-то погряз в изучении типовых. А тут такая возможность.
Спасибо 🙂
Спасибо автору!
Ну очень интересно!
Будем ждать продолжений!
Спасибо, статья очень полезная!
Конечно материал очень полезный. Спасибо
Большое спасибо! Надеюсь на продолжение, хотя понимаю, что труд огромный.
(0), спасибо! Небольшая поправка — «Система проницаема только в том случае, если любой объект из верхнего ряда соединен с любым объектом из нижнего ряда» заменить на «Система проницаема только в том случае, если существует такой объект из верхнего ряда, который соединен с одним из объектов из нижнего ряда».
Т.е. надо поменять квантор всеобщности, на квантор существования (если вы понимаете о чём я =)). Либо пример «проницаемой системы» неверен, потому как есть объекты нижнего ряда, которые не соединены с объектами верхнего ряда (что противоречит данному определению «проницаемости»).
Готовящимся в аттестации по платформе на заметку.
Вероятно, можно попробовать использовать алгоритм при решении задач из «1С: Специалист» с формулировками типа:
«У некоторых товаров могут быть аналоги – другие позиции номенклатуры с теми же потребительскими свойствами и ценой, причем таких аналогов у товара может быть несколько. Считается, что если «Товар1» имеет аналог «Товар2», а «Товар2» имеет аналог «Товар3», то «Товар3» также является аналогом «Товар1»»
Выглядит несложно.
Я думал решить через матрицу связности, но перспектива каждый раз при вычислении связности несколько раз перемножать матрицы, взамен
меня теперь не прельщает.
(8) ошибся в предыдущем своем псто. Такой подход предполагает что «если p связан с q, то q связан с p», — это в общем случае не является истиной
Если можно расскажите, вкратце как проходит обучение в коурсера, и если можно «исходники» статьи, чтобы понять насколько сложна для понимания версия без перевода. Просто давно интересуюсь подобным образованием, но слабое знание английского останавливает :).
(10) davdykin,
там просто всё. Курс не рассчитан на «шибко англоязычных», сложные слова можно подсмотреть, но в основном всё понятно по контексту. Я спокойно переводил со словарем, прошел, учась в универе, два года назад, Machine Learning и Model Thinking с большим удовольствием.
Мне лично формат не всегда удобен, я могу пропустить экзамен, замаявшись с делами. Тут, не смотря на дистанционный формат всё равно нужна хорошая дисциплина.
Хороший материал, как раз для недопрограммистов 1С-ников! 🙂
(11) утюгчеловек, Спасибо большое, возможно ваша информация поможет решиться послушать курс.
Честно говоря после прочтения статьи осталось несколько вопросов, если не сложно, кто все понял до конца поясните:
1. Сжатие пути. Насколько я понял из кода, через некоторое количество итераций мы получим не деревья а обычный массив, т.е. картинку которую мы видели в 1, т.к. в процедуре поиска корня не анализируется насколько глубокое дерево и стоит ли его перекидывать к корню?
2.
— в курсе рассказывается как получили данное уравнение, или, как любил говорить мой учитель по вышке «Нетрудно видеть», когда писал ответ следом за условием задачи?
3. Из
как-то совсем не видно сильного преимущества 5 алгоритма над 1-ым, не говоря уже о разнице в 30 лет и 6 секунд
. В 1С даже хорошие алгоритмы работают плохо? 🙂
Очень жалею что так наглядно, просто и интересно в нашем институте не рассказывали лекций. Спасибо! Статья просто супер!
Большое Вам спасибо! Объём проделанной работы впечатляет.
Спасибо за лекцию.
Все очень подробно рассказано.
Есть повод подучить алгоритмы.
здорово, всё очень наглядно и хорошо описано, в детали не вникал. Но по первому впечатлению всё очень доходчиво.
именно так и должны делаться все учебные материалы
терпения автору — учить программированию бывает сложнее самого программирования
В статье приведено гораздо более быстрое решение той же задачи на 1С
(19) ildarovich,
в качестве оправдания 🙂 — я пытался максимально сохранить соответствие примеров кода на java и 1С.
Если примеры будут использовать какие-либо специфичные объекты от 1С, то это получится слегка однобоко и неприменимо к другим языкам программирования.
В последующих лекциях будет аналогичная ситуация.
(20) и сама лекция и Ваша интерпретация выше всяких похвал. И я бы очень хотел, чтобы мое решение выглядело не как критика или замечание, а как дополнение к лекции, сделанное мелким шрифтом и нужное тем, кто решит применить результаты сразу на практике. А способ подачи своего решения и задиристое название статьи-спойлера — это просто юмор и способ привлечь к решению внимание.
С другой стороны, я сам долгое время думал, что все алгоритмы давно открыты. Пока не узнал, что алгоритм Боурера-Мура (быстрого поиска подстроки в строке) был открыт аж в 1984 году, когда люди уже лет 30 решали такие задачи. Из этого я сделал вывод, что алгоритмика не закостенела, что можно ждать новых открытий и искать новые решения.
«Быстрое объединение с оценкой веса» в английской литературе звучит как weighted quick-union, что в нашей литературе переводят как «Взвешенное быстрое объединение». А где взвешенное быстрое объединение с делением пополам (weighted quick-union with path compression by halving)? 🙂 Непроходят чтоль такое в принстоне? 🙂 Ладно я шучу, как сжать путь любой программист придумает кучу методов, если он не очередной «гугл копипаст говнокодер».
(21) ildarovich,
Да не то слово! Я, к примеру сам был в шоке когда узнал, что алгоритм Патерсона был придуман только в 1981 году! А это ведь азы computer science!
Колосальная работа. Только не понятно, зачем?
(24) chmv, если после прочтения всей статьи остался вопрос — «зачем она написана», то это печально. Вам, я думаю, эта статья незачем. С таким же успехом можно зайти на любую страницу, с темой не представляющей конкретно для вас интереса (например самолётостроения, или вышивки бисером, или бокса, да чего угодно! Если сказать языком теории множеств, то — универсальное множество минус узкий круг ваших интересов) и спрашивать, зачем она была написана. Но я всё же постараюсь кратенько обрисовать, зачем. Для саморазвития как программист, для развлечения и отвлечения от монотонной работы, может быть и куча других причин. Судя по популярности этой статьи, каждый, кто поставил под ней плюс, извлёк некую ценность из статьи для себя. Если же вы имели ввиду конкретную прикладную ценность для решения задач программистом, который забрёл на этот форум, то таковая имеется. Во-первых, эти алгоритмы могут пригодиться если специалист хочет расширить круг используемых языков, выйдя за рамки 1С, во-вторых статья демонстрирует возможность реализации на 1С стандартных алгоритмов. Наконец, и конкретно в автоматизации бизнеса на 1С встречаются задачи, где необходим поиск оптимального пути (например у моего коллеги была задача, где необходимо было найти наиболее удачный путь денежной транзакции через несколько подразделений одного предприятия в зависимости от набора ограничений — пришлось учить старые добрые алгоритмы).
Позабавило:
5. Они могут раскрыть секреты жизни и вселенной.
6. Для саморазвития, интеллектуальной стимуляции и хорошего заработка.
Не переводили бы Вы такую дурь 😉 — взяли бы лучше хорошую книжку какую-нибудь из прошлого века 19xx
Java — это немножко для другого…
(упрек по поводу выбору гнилого источника, к реализации на 1С — вопросов нет, т.к. это уже для забавы)
(24) chmv,
думаю, статья — наглядный и поучительный пример, что иногда надо думать )
т.е. смена алгоритма получения результата часто дает на порядок большее ускорение, чем другие методы
в применении к 1с — если что-то тормозит, не обязательно апгрейдить сервера, можно и запросы переписать, или над регистрами поработать
неоднократно изменение 1 запроса в типовых конфигурациях ускоряло проведение документа с 15-40 минут до 0.1-0.3с
Статья отличная.
Прошу простить мое буквоедство и откорректировать:
«…потребует =< c ( N + M lg* N ) числа доступов к массиву.
Где l
n*N:..»на
«…потребует =< c ( N + M lg N * N ) числа доступов к массиву.
Где lg*N:..
«
(28) Насколько я понимаю текущий вариант является правильным.
(29)
Ого, прошу прощения. Спасибо за просвещение.
Взял вашу конфигурацию, на ее основе сделал алгоритм построения дерева путей при тыке мышью на ячейке.
Дерево путей сделал визуальное отображение в виде красных ячеек на месте белых ячеек (свободные).
Коричневые ячейки — препятствие.
Должен заметить что мой алгоритм очень ущербен и на данный момент при размере веток дерева >5 1с уходит в долгий расчет более чем на час.
При размере веток дерева Путей <=5 считается в пределах нормы.
Как я понимаю, после каждого шага расчета (у меня 1 шаг расчета = увеличение всех веток дерева на 1) необходимо уплощать дерево (уменьшать количество листьев, увеличивать количество веток).
Алгоритм уплощения надо додумать.
Думаю, при верном построении алгоритма удастся создать полное дерево связности.
Но пока что нет на это время.
Зато получилось сделать визуальное отображение поиска на малых деревьях в небольшом диапазоне расстояний от точки старта.
См. рисунок
Как вариант упрощения алгоритма можно взять предложенный в игровой индустрии так называемый «Муравьиный поиск».
Попробую реализовать его для уменьшения количества вычислений.
В данном алгоритме необходимо реализовать распараллерирование вычислений. Каждый «Муравей» есть отдельный процесс производящий вычисление пути и помечающий его в дерево.
Соседние муравьи «Видят» проложенный собратом путь и не идут по нему.
Таким образом можно запустить несколько параллельных процессов обсчета дерева пути.
Кроме того, в прикладном значении алгоритм важен прежде всего для вычисления кратчайшего пути между 2 точками.
Это можно использовать в муравьином алгоритме.
Например, вычислять «РАсстояние» до целевой точки в каждой точке пути и таким образом вычислять «Рейтинг» каждой точки.
Муравей, при выборе следующей точки для обсчета из соседних, выбирает точку с наибольшим рейтингом.
Таким образом, сокращается радиус поиска и количество вычислений.
Еще одно упрощение задачи — муравей, первый нашедший путь будет считаться выигравшим гонку.
Все поиски завершаются и выбирается данный путь (Может и не самый лучший) — таким образом будет реализация алгоритма поиска первого попавшегося пути (возможно не самого кратчайшего), зато с минимальными затратами времени.
(32) Должен заметить особые случаи муравьиного алгоритма.
Если муравей прошел какой то тропой, не самой оптимальной. Его собрат «наткнулся» на след муравья.
Должен ли он пересекать его путь?
Варианты:
1. Муравьи не пересекают свои пути поиска
— В этом случае необходимо реализовывать «жадный» вариант поиска — искать все возможные соседние пути без пропусков
— Только после исчерпания всех соседних клеток искать другие
— Минусы — медленная прогрессия поиска, топтание на месте, тупики обхода, возвращение в исходные точки.
— Реализовать поиск быстрый поиск по рейтингу пути тяжело
2. Муравьи пересекают пути собратьев. Но делать это нежелательно.
Чтобы уменьшить это явление, уменьшать рейтинг тех клеток, которые прошел собрат.
Муравей пересечет путь собрата при острой необходимости (когда другие варианты менее желательны)
— Действует алгоритм поиска пути по рейтингу
— Более быстрый поиск, обход тупиков и слепых пятен.
Эти алгоритмы желательно реализовать в режиме реального времени с выводом в табличный документ и визуализацией «Муравьев», «рейтинга» и т.п.
Займусь данным вопросом, о результатах отпишусь.
Всем спасибо за внимание.