Q&A
ソースを提示してください。
失礼します。
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
誤差と言えば誤差になるのでしょうが........偶然なのでしょうか？
Zuishinさん。ご返答ありがとうございます！ 承知致しました。URLを貼っておきます！
ありがとうございます。17ms の違いでは誤差の問題になりそうですね。これを十万回くらい繰り返したら差が出るかどうかわかるかもしれませんが。後でやってみます。
回答2件
0
ベストアンサー
実際に試して見ました。
検証に使った問題: No.277 根掘り葉掘り - yukicoder
Rubyでキューひとつ 318 ms
Rubyでキュー入れ替え 322 ms
Python3でキューひとつ(list使用) 2369 ms
Python3でキュー入れ替え(list使用) 2331 ms
PyPy3でキュー一つ(list使用) TLE
PyPy3でキュー入れ替え(list使用) TLE
Python3でキューひとつ(deque使用) 987 ms
Python3でキュー入れ替え(deque使用 1004ms
(作り方がRuby脳なのかな…全く同じアルゴリズムの筈だけどPythonだと遅すぎるし、PyPy3だと逆にTLEとか、なぜだ…)
問題によるかもしれませんが、私の実装では誤差程度しか出ませんでした。
以下のようなプログラムを作り、配列のサイズによってpop()がどうなるかを試しました。
Python
1import random 2import time 3 4while True: 5 n, m = [int(i) for i in input().split()] 6 if n <= 0: 7 break 8 list = [random.randrange(n) for _ in range(n)] 9 10 start_time = time.time() 11 for _ in range(m): 12 list.pop(0) 13 end_time = time.time() 14 15 print("%.8f" % (end_time - start_time))
Python3 3.6.0 macOS Siera
|配列サイズ|取出数|試行回数|平均|最小|最大|
|---|---|---|---|---|
|10|10|10|0.00000560|0.00000286|0.00002098|
|100|10|10|0.00000367|0.00000262|0.00000405|
|1000|10|10|0.00000801|0.00000477|0.00001383|
|10000|10|10|0.00004036|0.00003099|0.00005794|
|100000|10|10|0.00100026|0.00080609|0.00132823|
|1000000|10|10|0.01386561|0.01161385|0.01659012|
TimeComplexity - Python Wikiによるとlistの削除はO(n)らしく、pop(0)もO(n)と思われます。なお、deque版も作りましたが、資料でO(1)とある通りに一定サイズ以上はほぼ同じ速度になります。Ruby 2.4.0のArray#shiftについても同様にO(1)のようで、一定サイズ以上はほぼ同じ速度です。
このことから、一定サイズ以上のlistをキューに使用するとかなり遅くなる場合があり得ます。キューにはdequeを使って回避するのが良いでしょう。
【蛇足】
なぜ、RubyのArray#shiftは速いのか？
RubyのArray#shiftは、配列が一定サイズ以上の場合、メモリ上の配列はそのままで先頭のポインタをずらすという手法を採っています。メモリ的には不利ですが、速度的には有利になります。サイズの大きさで処理を変えることで、同じ書き方でもなるべく高速に動作させるという戦略のようです。
https://github.com/ruby/ruby/blob/ruby_2_4/array.c#L1000
投稿2017/03/12 03:40
編集2017/03/12 14:21
総合スコア21735
raccyさん。
ご返答ありがとうございます！
私もまさにyukicoderでやっていたので、一応そのURLを貼りました。
20msくらいは誤差とみていいのでしょうか？
実行すると100msぐらい違うことはよくあることです。とくにPythonのようなインタプリンタ言語はインタプリンタそのものの起動に時間がかかる場合がありますので、実行する度に数十msの違うことがあります。
多くのパターンを何度も実行するなどしないと、本当に差があるかはわかりません。
raccyさん
実際にテストを実施、及び丁寧に解説していただき、誠に感謝いたします。
おかげさまで大変勉強になりました。Rubyとpythonとではそのような違いがあるのですね。
本当にありがとうございました。
すごくいい質問と回答でした。勉強になりました。
0
とりあえず 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 の方が有利という可能性が高いのではないかと思いました。
理由ははっきりしません。これは仮説なのですが、キューは配列で実装されていて、ポップする際に配列の中身全体を移動するのではないか、あるいはプッシュする際にバッファが足りなくなり、新たに配列を確保して既存の内容をコピーすることがあるのではないかと推察します。
投稿2017/03/12 12:06
編集2017/03/12 12:15総合スコア28660
Zuishinさん。
実際にタイムまで計測していただいて、誠に感謝いたします。
おかげさまで様々な可能性を知ることができました。
本当にありがとうございました！
あなたの回答
tips
プレビュー
