質問: 失礼します。 pythonで幅優先探索のアルゴリズムを組む時、 `1, 条件を満たす、もしくは元のqueueが空になるまで、一つのqueueに対してappend、popする` よりも、 `2, 都度新しいqueue(new_queue)を作って、その中にappendし、前のqueueが空になったら入れ替える` とした方が速度が上がります。 rubyとかでコードを書いた際は大差がないのに不思議でした。 どなたか理由をご存知のかた、教えてください。お願いいたします。 追記 1の方法で作ったアルゴリズムと結果(53ms) http://yukicoder.me/submissions/157478 2の方法で作ったアルゴリズムと結果(36ms) http://yukicoder.me/submissions/157479 誤差と言えば誤差になるのでしょうが........偶然なのでしょうか?
回答: とりあえず 1000 回ずつ 4 回やってみました。 方法は、1 から 10000 までのランダムな数字を 1000 個作り、それを配列に入れて入力としました。 1~2 試行は 1 を先に、3~4 試行は 2 を先に行っています。 | 試行 | 1 の結果(秒) | 2 の結果(秒) | | --- | --- | --- | | 1 | 84.7457154 | 83.3414437 | | 2 | 85.0808272 | 83.7006912 | | 3 | 85.6457193 | 83.9414727 | | 4 | 84.7167015 | 83.9267958 | 試行回数は少ないのですが、表より、誤差は 1000 回で 0.7 秒程度ではないかと推定されます。 誤差以上の開きがあり、1 の最短より 2 の最長の方が短いので、もっと試行回数を増やしてみないとはっきりしたことは言えませんが、2 の方が有利という可能性が高いのではないかと思いました。 理由ははっきりしません。これは仮説なのですが、キューは配列で実装されていて、ポップする際に配列の中身全体を移動するのではないか、あるいはプッシュする際にバッファが足りなくなり、新たに配列を確保して既存の内容をコピーすることがあるのではないかと推察します。