セットから要素を削除せずに取得するにはどうすればよいでしょうか?
https://stackoverflow.com/questions/59825
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
次のように仮定します。
>>> s = set([1, 2, 3])
から値（任意の値）を取得するにはどうすればよいですか s やらずに s.pop()?削除できると確信できるまで、項目をセット内に残しておきたいと考えています。これは、別のホストへの非同期呼び出しを行った後にのみ確認できます。
手早く汚い:
>>> elem = s.pop()
>>> s.add(elem)
しかし、もっと良い方法を知っていますか?理想的には一定時間内です。
解決
セット全体をコピーする必要のない 2 つのオプション:
for e in s:
break
# e is now an element from s
または...
e = next(iter(s))
ただし、一般に、セットはインデックス作成やスライスをサポートしません。
他のヒント
最小限のコードは次のようになります。
>>> s = set([1, 2, 3])
>>> list(s)[0]
1
明らかに、これはセットの各メンバーを含む新しいリストを作成することになるため、セットが非常に大きい場合には適していません。
さまざまなアプローチの背後にあるいくつかのタイミング図を提供するには、次のコードを検討してください。get() は Python の setobject.c に私がカスタムで追加したもので、要素を削除しない単なる Pop() です。
from timeit import *
stats = ["for i in xrange(1000): iter(s).next() ",
"for i in xrange(1000): \n\tfor x in s: \n\t\tbreak",
"for i in xrange(1000): s.add(s.pop()) ",
"for i in xrange(1000): s.get() "]
for stat in stats:
t = Timer(stat, setup="s=set(range(100))")
try:
print "Time for %s:\t %f"%(stat, t.timeit(number=1000))
except:
t.print_exc()
出力は次のとおりです。
$ ./test_get.py
Time for for i in xrange(1000): iter(s).next() : 0.433080
Time for for i in xrange(1000):
for x in s:
break: 0.148695
Time for for i in xrange(1000): s.add(s.pop()) : 0.317418
Time for for i in xrange(1000): s.get() : 0.146673
これは、 のために/休憩 ソリューションは最も高速です (場合によってはカスタム get() ソリューションよりも高速です)。
先生
for first_item in muh_set: break Python 3.x では依然として最適なアプローチです。 呪ってください、グイド。
あなたはこれをします
から推定された、さらに別の Python 3.x タイミングのセットへようこそ うーん。素晴らしい Python 2.x 固有の応答. 。とは異なり Aチャンピオンも同様に役に立ちます Python 3.x 固有の応答, 、以下のタイミング また 上記で提案された時間外れ値の解決策には、次のものが含まれます。
list(s)[0], ジョンさんの小説 シーケンスベースのソリューション.random.sample(s, 1), DF。の折衷的な RNGベースのソリューション.
大喜びのコード スニペット
電源を入れ、チューニングし、時間を計ります。
from timeit import Timer
stats = [
"for i in range(1000): \n\tfor x in s: \n\t\tbreak",
"for i in range(1000): next(iter(s))",
"for i in range(1000): s.add(s.pop())",
"for i in range(1000): list(s)[0]",
"for i in range(1000): random.sample(s, 1)",
]
for stat in stats:
t = Timer(stat, setup="import random\ns=set(range(100))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
すぐに時代遅れになる時代を超越したタイミング
見よ！ 最も速いスニペットから最も遅いスニペットの順に並べたもの:
$ ./test_get.py
Time for for i in range(1000):
for x in s:
break: 0.249871
Time for for i in range(1000): next(iter(s)): 0.526266
Time for for i in range(1000): s.add(s.pop()): 0.658832
Time for for i in range(1000): list(s)[0]: 4.117106
Time for for i in range(1000): random.sample(s, 1): 21.851104
家族全員のためのフェイスプラント
当然のことながら、 手動反復は少なくとも 2 倍の速度を維持します 次に速いソリューションとして。Bad Old Python 2.x の時代 (手動による反復処理が少なくとも 4 倍速かった) に比べてそのギャップは減少しましたが、これには期待外れです。 ペップ20 私の中では、最も冗長な解決策が最善であると信じています。少なくとも、セットの最初の要素を抽出するためだけにセットをリストに変換するのは、予想通りひどいことです。 グイドに感謝します。彼の光が私たちを導き続けてくれますように。
驚くべきことに、 RNG ベースのソリューションはまったくひどいものです。 リスト変換はダメですが、 random 本当に ひどいソースのケーキを受け取ります。についてはこれくらいです 乱数の神.
私はただ、不定形の彼らがPEPを立ち上げてくれることを願っています set.get_first() 私たちにとってはすでにメソッドです。あなたがこれを読んでいるなら、彼らはこう言っています。"お願いします。何かをしてください。」
ランダムな要素が必要なので、これも機能します。
>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]
ドキュメントにはパフォーマンスについては言及されていないようです random.sample. 。巨大なリストと巨大なセットを使った本当に簡単な経験的テストから、リストでは一定時間であるように見えますが、セットではそうではありません。また、セットに対する反復はランダムではありません。順序は未定義ですが、予測可能です。
>>> list(set(range(10))) == range(10)
True
ランダム性が重要であり、一定時間内に多数の要素 (大規模なセット) が必要な場合は、次のようにします。 random.sample まずリストに変換します。
>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time
さまざまなセットに対して関数がどのように実行されるのか疑問に思ったので、ベンチマークを実行しました。
from random import sample
def ForLoop(s):
for e in s:
break
return e
def IterNext(s):
return next(iter(s))
def ListIndex(s):
return list(s)[0]
def PopAdd(s):
e = s.pop()
s.add(e)
return e
def RandomSample(s):
return sample(s, 1)
def SetUnpacking(s):
e, *_ = s
return e
from simple_benchmark import benchmark
b = benchmark([ForLoop, IterNext, ListIndex, PopAdd, RandomSample, SetUnpacking],
{2**i: set(range(2**i)) for i in range(1, 20)},
argument_name='set size',
function_aliases={first: 'First'})
b.plot()
このプロットは、いくつかのアプローチ (RandomSample, SetUnpacking そして ListIndex) セットのサイズに依存するため、一般的なケースでは回避する必要があります (少なくともパフォーマンスが向上する場合)。 かもしれない 大切にしてください）。他の回答ですでに示されているように、最速の方法は ForLoop.
ただし、一定時間アプローチのいずれかを使用している限り、パフォーマンスの差は無視できます。
iteration_utilities (免責事項:私が作者です) には、このユースケースに便利な関数が含まれています。 first:
>>> from iteration_utilities import first
>>> first({1,2,3,4})
1
上記のベンチマークにも含めました。他の 2 つの「高速」ソリューションと競合する可能性がありますが、どちらの場合も大きな違いはありません。
私が作成したユーティリティ関数を使用します。その名前は、ランダムなアイテムかそのようなものである可能性を暗示しているため、やや誤解を招きます。
def anyitem(iterable):
try:
return iter(iterable).next()
except StopIteration:
return None
@wrをフォローしています。投稿すると、同様の結果が得られます（Python3.5の場合）
from timeit import *
stats = ["for i in range(1000): next(iter(s))",
"for i in range(1000): \n\tfor x in s: \n\t\tbreak",
"for i in range(1000): s.add(s.pop())"]
for stat in stats:
t = Timer(stat, setup="s=set(range(100000))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
出力：
Time for for i in range(1000): next(iter(s)): 0.205888
Time for for i in range(1000):
for x in s:
break: 0.083397
Time for for i in range(1000): s.add(s.pop()): 0.226570
ただし、基礎となるセットを変更する場合（例:に呼び出します remove()) 反復可能な例では事態は悪化します (for, iter):
from timeit import *
stats = ["while s:\n\ta = next(iter(s))\n\ts.remove(a)",
"while s:\n\tfor x in s: break\n\ts.remove(x)",
"while s:\n\tx=s.pop()\n\ts.add(x)\n\ts.remove(x)"]
for stat in stats:
t = Timer(stat, setup="s=set(range(100000))")
try:
print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
except:
t.print_exc()
結果:
Time for while s:
a = next(iter(s))
s.remove(a): 2.938494
Time for while s:
for x in s: break
s.remove(x): 2.728367
Time for while s:
x=s.pop()
s.add(x)
s.remove(x): 0.030272
どうでしょうか s.copy().pop()?時間を計っていませんが、うまくいくはずですし、簡単です。ただし、セット全体をコピーするため、小さなセットに最適です。
もう 1 つのオプションは、気にしない値を含む辞書を使用することです。例えば。、
poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...
キーは単なる配列であることを除き、セットとして扱うことができます。
keys = poor_man_set.keys()
print "Some key = %s" % keys[0]
この選択の副作用は、コードが古い以前のコードと下位互換性を持つことです。set Python のバージョン。それは最良の答えではないかもしれませんが、別の選択肢です。
編集：次のようなことを実行して、配列またはセットの代わりに辞書を使用したという事実を隠すこともできます。
poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
poor_man_set = poor_man_set.keys()
