0

私は Android ゲーム用のパスファインディング アルゴリズムを開発しています。再帰バージョン (これは素晴らしいですが、大きなスタックが必要なので、より大きなスタックサイズで専用のスレッドを作成する必要があるかもしれません) と「ループ」を作成できます。 (再帰の代わりに) バッファを使用するバージョン。バッファのサイズが事前にわからないことも大きな問題であるため、現在のところ、スタックベースのソリューションのみが実行可能に見えます。

これはアルゴリズム理論または一般的なコンピューター サイエンスの質問かもしれませんが、スタック サイズは結局システム固有の機能であるため、Android 固有の可能性があります。

一般的に、Android ではどちらがより効率的 (速度) である必要がありますか? スタックのものですか、それともバッファ (ヒープ) に依存するものですか? 質問はアーキテクチャ的に問題にアプローチすることに注意してください（アルゴリズムの複雑さは、アルゴリズムが再帰的かループベースかに依存しないと仮定します）。

4

2 に答える 2

1

Android 固有の回答を求められたことは承知していますが、それはあなたの問題とはあまり関係がないと思います。2つの備考

  1. 再帰アルゴリズムを実装するために必ずしもスタック ベースのソリューションが必要なわけではありません。スタック ベースのデータ構造を使用して、ヒープ上のスタックをエミュレートできます。ただし、これが必要ない場合もあります。これにはもう少し手間がかかりますが、人工的なアーキテクチャ上の制約に基づいてアルゴリズムを作成しないでください。
  2. Bellman-Fordなど、非再帰的な経路探索、最短経路アルゴリズムがたくさんあります。

問題に対する最適な再帰ソリューションが、Android での最適な反復ソリューションよりも優れているかどうかについてはコメントできません。通常、他のすべての条件が同じであれば、反復ソリューションの方が高速になりますが、フィボナッチ数などよりも複雑なアルゴリズムになると、反復アルゴリズムを再帰的に実装したり、その逆を行ったりすると、違いが生じる可能性があります。

于 2012-05-17T23:05:33.377 に答える
0

私の直感では、早期最適化の罪を犯そうとしているようです。RAM が不足することを示す計算または測定値はありますか?

できるだけ単純なアルゴリズムを使用することをお勧めします。ただし、UI が一瞬でもフリーズしないように、AsyncTask を使用することをお勧めします。

于 2012-05-17T23:15:47.367 に答える