Вопрос про декларативные графы.
Итак, расхожим мифом является мнение, что декларативные графы нельзя построить иначе, как с оверхедом O(logN) (N - число узлов (дуг)). Это проистекает из-за того, что отображение Узел→Дуги хранится в сбалансированном дереве.
Две статьи на эту тему:
Чуть более тщательное, чем обычно, чтение статей показало, что реализация на отображения деревьях приводит к константному замедлению и это замедление колеблется от 3 раз (для depth-first search) до - барабанная дробь! - 0.47! То есть, использование деревьев ускоряет некоторые операции вдвое.
И нигде - вообще нигде, - нет зависимости наподобие O(logN).
Да даже если бы и была, logN для больших N практически константа. Что в лоб, что по лбу. ;)
Вот. Если кто что будет еще говорить, буду посылать сюда. ;)
Две статьи на эту тему:
- Inductive Graphs and Functional Graph Algorithms, Martin Erwig.
- Fully Persistent Graphs - Which One to Choose?, Martin Erwig
Чуть более тщательное, чем обычно, чтение статей показало, что реализация на отображения деревьях приводит к константному замедлению и это замедление колеблется от 3 раз (для depth-first search) до - барабанная дробь! - 0.47! То есть, использование деревьев ускоряет некоторые операции вдвое.
И нигде - вообще нигде, - нет зависимости наподобие O(logN).
Да даже если бы и была, logN для больших N практически константа. Что в лоб, что по лбу. ;)
Вот. Если кто что будет еще говорить, буду посылать сюда. ;)