.NET производительность: глубокая рекурсия против очереди

Question

Я пишу компонент, который должен пройти большие объектные графики, иногда на 20-30 уровней.

Какой самый характерный способ ходить по графику?

A. Встреча «шагов», чтобы избежать глубокой рекурсии

или же

B. DFS (глубина сначала поиск), который может превышать много уровней глубиной и иногда иметь «глубокий» след стека.

Я предполагаю, что вопрос, который я задаю: есть ли в .NET в .NET для выполнения DFS, который вызывает «глубокий» трассу? Если да, то какой удар? И будет ли я лучше с некоторыми BFS посредством очереди на шагов, с которыми можно было бы рекурсивно обращаться в DFS?

Извините, если мне неясно. Спасибо.

Answer 1

В среде выполнения нет ничего, что могло бы привести к тому, что выполнение кода в глубоком стеке будет медленнее, чем в неглубоком стеке вызовов. Для этого нет причин, потому что обычно выполнение кода не запускает ходьбу стека.

Когда я обычно говорю, это означает, что есть несколько исключений:

• Проверки безопасности/доказательств обычно ходят по стеку вызовов, чтобы определить текущий контекст безопасности
• Конечно, бросая и ловить исключения (вы все равно не хотите делать это в переходе дерева, за исключением его прервания)

Независимо от того, следует ли вам внедрить итерационное или рекурсивное обход деревьев, не зависит от того, даст ли время выполнения .NET вам лучшая производительность в одном сценарии по сравнению с другим, но вы должны принять решение на основе Big-O (время и память), Особенно, если это для больших деревьев. Я не думаю, что мне нужно напомнить вам о вероятности переполнения стека рекурсивным решением, учитывая, где мы есть ... Оптимизация хвоста возможна, хотя.

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

Answer 2

Видеть Почему .NET/C# оптимизируется для рекурсии для хвостового вызова?Анкет По-видимому, .net выполняет оптимизацию рецирсии хвоста на x86-64, так что если это ваша архитектура, а также Ваш код поддается такой оптимизации, придерживайтесь рекурсии.

Answer 3

Вы смешиваете два понятия, которые должны быть в некоторой степени отделены:

• Итерация структуры данных в зависимости от использования рекурсивных функций, где стек вызовов становится вашей структурой.

• Ширина-по сравнению с глубиной первой отрывок.

Они подключены, поскольку рекурсивные функции имеют тенденцию реализовать первые глубины. Однако при использовании очереди нет ничего, что не ограничивает вас до первой ширины.

Используйте очередь FIFO, если вы хотите, чтобы в первую очередь была очередь LIFO, если вы хотите сначала глубины. В любом случае, вы сохраняете накладные расходы на вызов функции (вероятно, довольно незначительные, и вызывные методы в очереди могут быть более дорогими, если они не будут внедрены оптимизатором) и использование пространства стека в стеке системных вызовов.