0

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

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

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

4

2 回答 2

1

我知道您要求提供特定于 Android 的答案，但我认为这与您的问题无关。两个备注

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

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

于 2012-05-17T23:05:33.377 回答
0

我的直觉是你即将犯下早期优化的罪过。您是否有任何计算或测量表明您将用完 RAM？

我建议您使用最简单的算法。但是，您可能希望使用 AsyncTask 以免冻结 UI，即使是一秒钟。

于 2012-05-17T23:15:47.367 回答