android - Android 上的搜索算法 : stack or preallocated buffer?

Question

我正在为 Android 游戏开发一个寻路算法，我可以编写一个递归版本(这很好，但需要一个大堆栈，所以我可能需要为此创建一个具有更大堆栈大小的专用线程)，以及一个使用缓冲区(而不是递归)的“循环”版本。提前不知道buffer的大小也是个大问题，所以目前看来只有基于栈的方案可行。

我知道这可能是一个算法理论或一般计算机科学问题，但也可能是特定于 Android 的，因为堆栈大小毕竟是系统特定的功能。

一般来说，Android 上哪个应该更高效(速度)？堆栈一个，还是依赖缓冲区(堆)的那个？请注意，问题在架构方面接近问题(假设算法的复杂性不取决于算法是递归的还是基于循环的)。

Answer 1

我知道您要求的是 Android 特定的答案，但我认为它与您的问题无关。两点说明

1. 您不一定需要基于堆栈的解决方案来实现递归算法，你可以用一个模拟堆上的堆栈基于栈的数据结构。不过，有时您甚至不需要这个。这需要更多的工作，但不要将您的算法基于人为的架构约束。
2. 有很多非递归寻路、最短路径算法，即Bellman-Ford

对于问题的最佳递归解决方案是否会优于 Android 上的最佳迭代解决方案，我无法发表评论。通常，在所有其他条件相同的情况下，迭代解决方案会更快，但是当您遇到比斐波那契数更复杂的算法时，递归地实现迭代算法或反之亦然可能会有所不同。