[解決済み] リストからランダムな要素をポップする最も効率的な方法は何ですか？

質問

あるリストがあるとします x があり、そこからランダムに1つの要素をポップして、リストがその要素を含まないようにしたいとします。これを行うための最もpythonicな方法は何ですか？

私は、かなり手間のかかる pop , random.randint そして len といった、より短い、あるいはより良い解決策を見たいと思います。

import random
x = [1,2,3,4,5,6]
x.pop(random.randint(0,len(x)-1))

私が実現しようとしているのは、リストからランダムな要素を連続的にポップすることです。(すなわち、ある要素をランダムにポップして辞書に移動し、別の要素をランダムにポップして別の辞書に移動する、...)

私はPython 2.6を使用しており、検索機能を介して任意のソリューションを見つけることができなかったことに注意してください。

どのように解決するのですか？

あなたがしようとしていることは、そもそもPython的ではなさそうです。リストの途中のものを削除してはいけません。なぜなら、私が知っているすべてのPythonの実装では、リストは配列として実装されているので、これは O(n) の操作になります。

アルゴリズムの一部としてこの機能が本当に必要であれば、以下のようなデータ構造をチェックアウトする必要があります。 blist のような、中間からの効率的な削除をサポートするデータ構造をチェックする必要があります。

純粋なPythonでは、残りの要素にアクセスする必要がない場合にできることは、最初にリストをシャッフルして、それに対して反復処理を行うだけです。

lst = [1,2,3]
random.shuffle(lst)
for x in lst:
  # ...

もし、あなたが 本当に必要なら が必要な場合 (これはちょっとしたコード臭です、IMHO)、少なくともあなたは pop() をリストの最後から呼び出すことができます（これは速いです！）。

while lst:
  x = lst.pop()
  # do something with the element      

一般に、（リストで行うような）状態の変異ではなく、より関数的なスタイルでプログラムを表現した方が、よりエレガントな表現ができることが多いようです。