質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.95%

pythonでqueueを使うときの方法について

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,096

score 347

失礼します。

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

誤差と言えば誤差になるのでしょうが........偶然なのでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Zuishin

    2017/03/12 08:43

    ソースを提示してください。

    キャンセル

  • dialbird

    2017/03/12 14:08

    Zuishinさん。ご返答ありがとうございます! 承知致しました。URLを貼っておきます!

    キャンセル

  • Zuishin

    2017/03/12 14:22

    ありがとうございます。17ms の違いでは誤差の問題になりそうですね。これを十万回くらい繰り返したら差が出るかどうかわかるかもしれませんが。後でやってみます。

    キャンセル

回答 2

checkベストアンサー

+5

実際に試して見ました。

検証に使った問題: 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()がどうなるかを試しました。

import random
import time

while True:
    n, m = [int(i) for i in input().split()]
    if n <= 0:
        break
    list = [random.randrange(n) for _ in range(n)]

    start_time = time.time()
    for _ in range(m):
        list.pop(0)
    end_time = time.time()

    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 14:14

    raccyさん。
    ご返答ありがとうございます!

    私もまさにyukicoderでやっていたので、一応そのURLを貼りました。
    20msくらいは誤差とみていいのでしょうか?

    キャンセル

  • 2017/03/12 15:07

    実行すると100msぐらい違うことはよくあることです。とくにPythonのようなインタプリンタ言語はインタプリンタそのものの起動に時間がかかる場合がありますので、実行する度に数十msの違うことがあります。

    多くのパターンを何度も実行するなどしないと、本当に差があるかはわかりません。

    キャンセル

  • 2017/03/13 10:41

    raccyさん
    実際にテストを実施、及び丁寧に解説していただき、誠に感謝いたします。
    おかげさまで大変勉強になりました。Rubyとpythonとではそのような違いがあるのですね。
    本当にありがとうございました。

    キャンセル

  • 2017/03/13 10:44

    すごくいい質問と回答でした。勉強になりました。

    キャンセル

+2

とりあえず 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/13 10:37

    Zuishinさん。

    実際にタイムまで計測していただいて、誠に感謝いたします。
    おかげさまで様々な可能性を知ることができました。
    本当にありがとうございました!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.95%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る