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

Question

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

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

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

или

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

• Ширина в ширину против обхода в глубину.

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

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

Answer 3

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