1

pythonのすべての値がlist2に存在するかどうかを確認する必要があるコードを少し書いてlist1いset(list2).difference(list1)ます。

list1だから私はそれが高速検索のための辞書になると思っていました...

したがって、リストにdictの一部ではない項目がある場合、抑止するための迅速な方法を見つけたいと思います

パフォーマンスに関して違いはありますか

d = {1: 1, 2:2, 3:3}
l = [3, 4, 5]

for n in l:
  if not n in d:
    do_stuff

対

for n in l:
  if not d[n]:
    do_stuff

そして、これらの両方がゴミであり、何かもっと早く知っている場合は教えてください.

Edit1: list1 または d には、list2 にない要素を含めることができますが、その逆はできません。

4

3 に答える 3

3

あなたが望むものを達成するための迅速な方法はall、ジェネレータ内包表記を使用することです。

s_list2 = set(list2)
all_present = all(l in s_list2 for l in list1)

これは、list1 の一部の要素が list2 に存在しない場合に有利です。

いくつかのタイミング。最初のリストのすべての値が 2 番目のリストに含まれている場合:

In [4]: l1 = range(100)
In [5]: l2 = range(1000)
In [6]: random.shuffle(l1)
In [9]: random.shuffle(l2)
In [20]: %timeit s2 = set(l2); all(l in s2 for l in l1)
10000 loops, best of 3: 26.4 us per loop
In [21]: %timeit s1 = set(l1); s2 = set(l2); s1.issubset(s2)
10000 loops, best of 3: 25.3 us per loop

最初のリストの一部の値が2 番目のリストに存在しない場合を見ると、次のようになります。

In [2]: l1 = range(1000)
In [3]: l2 = range(100)
In [4]: random.shuffle(l1)
In [5]: random.shuffle(l2)
In [6]: sl2 = set(l2)
In [8]: %timeit ss = set(l2); set(l1) & ss == ss
10000 loops, best of 3: 27.8 us per loop
In [10]: %timeit s1 = set(l1); s2 = set(l2); s2.issubset(s1)
10000 loops, best of 3: 24.7 us per loop
In [11]: %timeit sl2 = set(l2); all(l in sl2 for l in l1)
100000 loops, best of 3: 3.58 us per loop

この方法のパフォーマンスissubsetは最初のケースの と同等であり、2 番目のケースの方が高速であることがわかります。これは、回路が短絡し、2 つの中間セットを作成する必要がなくなるためです (必要なのは 1 つだけです)。

1 つの大きなリストと 1 つの小さなリストを持つことは、gencomp 法の利点を示しています。

In [7]: l1 = range(10)
In [8]: l2 = range(10000)
In [9]: %timeit sl2 = set(l2); all(l in sl2 for l in l1)
1000 loops, best of 3: 230 us per loop
In [10]: %timeit sl1 = set(l1); all(l in sl1 for l in l2)
1000000 loops, best of 3: 1.45 us per loop
In [11]: %timeit s1 = set(l1); s2 = set(l2); s1.issubset(s2)
1000 loops, best of 3: 228 us per loop
In [12]: %timeit s1 = set(l1); s2 = set(l2); s2.issubset(s1)
1000 loops, best of 3: 228 us per loop
于 2013-01-21T17:29:23.563 に答える
2

リストをセットに変換してから、メソッドissubset()を使用して、リストが別のセットのサブセットであるかどうかを確認できます。

In [78]: import random

In [79]: lis2=range(100)

In [80]: random.shuffle(lis2)

In [81]: lis1=range(1000)

In [82]: random.shuffle(lis1)

In [83]: s1=set(lis1)

In [84]: all(l in s1 for l in lis2)
Out[84]: True

In [85]: %timeit all(l in s1 for l in lis2)
10000 loops, best of 3: 28.6 us per loop

In [86]: %timeit s2=set(lis2);s2.issubset(s1)
100000 loops, best of 3: 12 us per loop

In [87]: s2.issubset(s1)
Out[87]: True
于 2013-01-21T17:29:39.423 に答える
1

両方のリストを並べ替えてから一緒にウォークスルーするのはO（n log n）です。すなわち：

l1.sort()
l2.sort()

j = 0
for i in range(0,len(l1)):
  while ((j < len(l2)) and (l1[i] == l2[j])):
    j = j+1
  if (j == len(l2)):
    break
  if (l1[i] > l2[j]):
    break

if (j == len(l2)): # all of l2 in l1

時間計算量の観点から、私が言ったように、これはソートのためにO（n log n）です（2番目のループはO（n）のループよりも小さいです）。ただし、Pythonでは組み込みのset操作よりも高速ではない場合があります。あなたはそれを試さなければならないでしょう。

[ところで、私が考えれば、おそらく最後の部分を理解して行うためのよりパイソンな方法です]

于 2013-01-21T21:31:02.967 に答える