Я недавно нашел структуру под названием Ecto .
В этом контексте базовый компонент, называемый «плазмой» , является экто направленным ациклическим графом. В эктоплазме может работать планировщик экто.
Мне интересно, в чем преимущество этого механизма, и в каких других ситуациях мы можем использовать концепцию DAG?
algorithms
data-structures
frameworks
graph
По-Джен Лай
источник
источник
Ответы:
Хороший вопрос
РЕДАКТИРОВАТЬ :
Хорошие ресурсы:
источник
Ответ в том, что это не имеет ничего общего с программированием. Это связано с решением проблем.
Так же, как связанные списки являются структурами данных, используемыми для определенных классов задач, графики полезны для представления определенных отношений. Связанные списки, деревья, графики и другие абстрактные структуры имеют связь только с программированием, поскольку вы можете реализовать их в коде. Они существуют на более высоком уровне абстракции. Речь идет не о программировании, а о применении структур данных для решения проблем.
Если вы все же хотите иметь какое-то отношение к программированию, пожалуйста, обратите внимание на следующие моменты:
источник
Другие люди применяли DAG к данным, но я думаю, что это как минимум применимо (если не больше) к коду. Махбубур Р. Ааман упоминает об этом, так что на самом деле это скорее дополнение к его ответу, чем сам по себе полный ответ.
Мне кажется, что любая императивная компьютерная программа , свободная от бесконечных циклов (спасибо @AndresF.), Является Направленным ациклическим графом (DAG). Это означает, что возможные пути выполнения кода являются направленными (сначала то, потом то) и ациклическими (не образующими бесконечные циклы). Они представляют собой граф, потому что путь через любой значимый код редко бывает таким простым, как список или дерево.
Я работал в XSLT около 4 лет. Я ужасно пытался объяснить, почему это не был хороший язык программирования общего назначения, но причина в DAG. В частности, XSLT является языком данных. Вы определяете функции (да, в смысле функционального программирования), но вы не обязательно вызываете эти функции из своего кода. Скорее, XSLT устанавливает комбинацию выбора и итерации узлов входного XML-документа. Это позволяет структуре входных данных определять, какие функции вызываются и в каком порядке.
Это было очень интересно и очень круто, пока ваша программа не столкнулась с состоянием данных, которое вы не проверяли в 2:30, и вам не пришлось проснуться и исправить его. Когда вы позволяете данным определять DAG, тогда определение DAG становится всеми возможными входными условиями, которые для любого нетривиального бизнес-приложения не поддаются исчислению; они невообразимы.
Сначала я подумал, что функциональное программирование не может быть DAG, потому что программист иногда не понимает порядок выполнения или даже не думает о нем. Но функциональная программа определяет зависимости. Фактически, декларативную природу функционального программирования можно рассматривать как определение только зависимостей (a ^ 2 = b ^ 2 + c ^ 2) без указания порядка выполнения (не имеет значения, является ли 'b' или 'c' квадратным первым до тех пор, пока они оба будут в квадрате, прежде чем их сложить вместе).
Но в то время как функциональное программирование может быть преднамеренно неопределенным в отношении порядка операций на детальном уровне, оно совершенно ясно о зависимостях. Это те самые особенности, которые делают его доступным для параллелизма. В любом случае, в коде все еще есть граф путей, и этот граф все еще направлен (зависимости должны быть оценены перед зависимыми задачами), поэтому я думаю, что DAG также применяется и там.
Хороший вопрос - спасибо за публикацию!
источник
while (true) { print("hi"); }? Может быть, вы хотите исключить не завершающие программы?В настоящее время DAG недооценивается в программировании. Исторически многие вещи, связанные с разработкой, были сделаны с помощью деревьев и иерархий, потому что перемещение чего-либо в коробке удобно для нашего мозга, чтобы упростить управление сложными вещами. Но если вы посмотрите на события и то, как они зависят от других событий и состояний, вы получите DAG, потому что все в нашей жизни и в программе может зависеть от чего-либо в прошлом, но не в будущем, так что вы получите совершенно «ациклический» отношения должны быть применимы к концепции DAG. Хотя это редко используется явно в процессе разработки, это поможет понять вещи лучше
источник
DAG может использоваться для моделирования набора задач в последовательности с ограничением того, что некоторые задачи должны выполняться раньше других. Ecto является платформой обработки и использует DAG для моделирования графиков обработки, чтобы графики выполняли упорядоченное синхронное выполнение. Plasm в Ecto является DAG и планировщик работает на нем.
источник
В качестве примера из реальной жизни наше программное обеспечение похоже на IDE, где конечный пользователь может определить серию операций, выполняемых над изображением (проверка машинного зрения). Эти проверки могут зависеть от других проверок или могут зависеть от них. Поскольку все это настраивается конечным пользователем, мы не можем оптимизировать параллельную обработку во время разработки. Представляя эти проверки и зависимости в качестве группы обеспечения доступности баз данных, мы можем оптимизировать параллельность всей проверки для обеспечения максимальной производительности во время выполнения.
источник
Просто для другого примера, правила управления памятью в приложениях Какао сделаны так, что все сильные ссылки формируют направленный ациклический граф, который сделан, чтобы гарантировать отсутствие утечек.
источник
Добавив еще один ответ, вы еще не видели ссылки на системы сборки, в
makeкоторых используется DAG для определения зависимостей для сборки.Подробнее здесь
источник
make