如何快速比较列表和集合？
How can I quickly compare a list and a set?
假设我有一个列表
l = [1, 1 , 1, 2, 3, 4, 5, 5]
和两个不相交组等长
a = (1, 3) 和 b = (2, 5)
我想分别获取 a 和 b 中 l 中的元素，例如
[1, 1, 1, 3] 和 [2, 5, 5]
我尝试了像 [x for x in l if x in a] 这样的列表理解，但是如果 l、a 和 b 的长度是 10^5[=29，那需要很长时间=]
编辑：集合是等长的不相交集合。
编辑：我需要做的是计算 l 中常见的 a 中的元素（重复项）减去 [=15= 中的 l 中的元素]（也有重复项）。所以上面的例子应该输出1。问题是列表和集合是否与 10E5 一样长。使用过滤器和 itertools 仍然需要很长时间。
编辑：我现在明白了！显然我必须用 set() 包装输入集！一开始我不知道（我只是通过 input().split() 得到的）因为输入已经是唯一的但不知道列表和集合有很大的不同而且集合更快！好吧，直到我。
您可以使用 itertools 模块中的 chain 和 repeat 函数：
>>> from itertools import repeat,chain
>>> a={1,3}
>>> list(chain.from_iterable((repeat(i,l.count(i)) for i in a)))
[1, 1, 1, 3]
注意：作为一种更有效的方法，您可以为 a 使用 set 容器，它的成员检查复杂度为 O(1)，并且您不需要调用 list 如果您不需要结果作为列表，chain.from_iterable returns 一个 iterator.
或者作为一种非常优化的方法，您可以使用 numpy，这在处理大型列表时特别强大：
>>> import numpy as np
>>> l = np.array([1, 1 , 1, 2, 3, 4, 5, 5])
>>> a = (1, 3)
>>> l[np.in1d(l,a)]
array([1, 1, 1, 3])
l = [1, 1 , 1, 2, 3, 4, 5, 5]
a = (1, 3)
b = (3, 5)
l2 = list(filter(a.__contains__, l)) # [1, 1, 1, 3]
l3 = list(filter(b.__contains__, l)) # [3, 5, 5]
我很想知道这对您的数据集有何影响。
from pandas import Series
l = Series([1, 1 , 1, 2, 3, 4, 5, 5])
a = Series((1, 3))
b = Series((3, 5))
a_answer, b_answer = list(l[l.isin(a)]), list(l[l.isin(b)])
原因：Pandas 的调用实现级别低于 Python，因此根据数字的数据类型，它可能比纯粹的 python 解决方案更适合您。
快吗？
Kasramvd 提出了一个聪明的 np.in1d() 方法和 Wesley 的强大 pandas 框架还建议，让我设置定量标准 以便能够处理个别解决方案的质量。
让我们既公平又量化：
越多，一旦10E+5个物品进入游戏。 处理效率和速度，内存处理，矢量化潜力和（也许）隐藏不利的副作用，CPU-缓存延迟掩蔽更差或更好的关闭-CPU数据访问时间（以及更多的巨魔）-这些都是敌人，我们必须在生产中忍受：
摘要：
Nathan 基于 set 的方法对于所有测试的量表都更快。
Nathan 的方法处理小型 1E+4 和 1E+6 缩放集的速度相当快，利用隐藏在 python 中独特元素的可哈希集合中的有利搜索功能的成果 set-s（因为 set 类型正是为 引入的）。
然而，O( m*n ) / O( n^2 )无法证明。
这些假设的复杂性模型应该意味着，随着 m、n 规模的增长，与 [=20] 相比，基于 numpy 的方法的不利性能损失=] 基于相同 list/set-dataSets 的方法应增长并加速更大的 m,n-s.
增加 set 尺度表明初始边缘在更大的尺度上变得更小。
1:3 在 1E+4 规模上的速度优势降级到仍然尊重，但一些[=109 的优势较小=]1:2 1E+6 规模上的速度优势。
真正的代码执行已经做出了任务 O(m*n)/O(n^2) 复杂度的先验假设，无法在体内确认。
如何测试？
>>> import numpy as np
>>> from zmq import Stopwatch
>>> aStopWATCH = Stopwatch()
>>> l = [1, 1 , 1, 2, 3, 4, 5, 5]
>>> a = (1, 3)
>>> b = (3, 5)
>>> npL = np.array( l )
>>> npL
array([1, 1, 1, 2, 3, 4, 5, 5])
>>> npA = np.array( a )
>>> npA
array([1, 3])
>>> import numba # ______________________________was not me who has said QUICKLY
>>> @numba.jit # QUICKLY
... def getLinA( aListAsNumpyARRAY, aSetAsNumpyARRAY ): # << Kasramvd
... return aListAsNumpyARRAY[ np.in1d( aListAsNumpyARRAY,
aSetAsNumpyARRAY
)
]
>>>
>>> aStopWATCH.start();getLinA( npL, npA );aStopWATCH.stop()
array([1, 1, 1, 3])
113513L # runs a JIT-compiler on a first call ... pay 113,51 [ms]
>>> aStopWATCH.start();getLinA( npL, npA );aStopWATCH.stop()
array([1, 1, 1, 3])
653L # runs a pre-compiled code on 2nd+ ...... wow 0,65 [ms]
855L # runs a pre-compiled code on 2nd+ ...... wow 0,86 [ms]
857L # runs a pre-compiled code on 2nd+ ...... wow 0,86 [ms]
698L # runs a pre-compiled code on 2nd+ ...... wow 0,7 [ms]
690L # runs a pre-compiled code on 2nd+ ...... wow 0,7 [ms]
提示：
是的，没有免费的晚餐。
如您所见，一旦我们不得不为 JIT 编译付出代价。
但是，多亏了 Travis OLIPHANT 出色的 numba 工具，没有人可以阻止我们 "pre-mini-call"（让 JIT 编译器完成它的职责）
getLinA( npL[:2], npA[:2] )
然后重新 运行 已编译的全尺寸
getLinA( npL[:1E+9], npA[:1E+9] )
Ex post 受与 Nathan Davis
思想交流启发的讨论
>>> def NathanListPROCESSOR( aList = [1,1,3,2,5,7,8,3,2,1],
setA = set( ( 1, 3 ) ),
setB = set( ( 2, 3 ) )
):
... accumulator = 0
... for item in aList:
... if item in setA:
... accumulator += 1
... elif item in setB:
... accumulator -= 1
... print accumulator
... return
...
>>> NathanListPROCESSOR() #_______________________EXPECTED: == 2
3 #_______________________O/P DEFINED: == 1
时间：请参考。随着实际代码执行工件的出现，计时结果发生变化（缓存脏度发生变化，）
>>> aStopWATCH.start();NathanListPROCESSOR();aStopWATCH.stop()
3
1207L
491L
279L
350L
1478L
1172L
1698L
1488L
1449L
9688L
1466L
对于缩放到 1E+4 和 1E+6 大小的对象：
>>> aStopWATCH.start();NathanListPROCESSOR( aLIST, setA, setB );aStopWATCH.stop()
-1
2582L
2673L
2529L
2524L
2888L
2693L
>>> aStopWATCH.start();getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
0
129983L
12068L
10699L
10930L
10857L
10999L
10954L
10994L
在 numba 的帮助下：
>>> @numba.jit
... def numba_getLISTinSET( npList, npSetA, npSetB ):
... return ( len( npList[ np.in1d( npList, npSetA ) ] ) -
len( npList[ np.in1d( npList, npSetB ) ] )
)
>>> aStopWATCH.start();numba_getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
0
165320L
7047L
7328L
7378L
7898L
7519L
7556L
7277L
7296L
7292L
7303L
7302L
7426L
7369L
7307L
终于几乎-1E+6天平:
>>> setA = generateSet( 1000000 )
>>> len( setA ) # the cost of uniqueness
235836
>>> setB = generateSet( 1000000 )
>>> npSetA = np.array( list( setA ), dtype = np.int )
>>> npSetB = np.array( list( setB ), dtype = np.int )
>>> aLIST = list( ( np.random.random( 1000000 * 1.1 + 10 ) * 1000000 * 10000 ).astype( np.int ) )[:1000000]
>>> len( aLIST )
1000000
>>> npLIST = np.array( aLIST, dtype = np.int )
#----------------------vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv-------------
#---------------------| |-------------
>>> aStopWATCH.start();numba_getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
6
406061L
403946L
409831L
409329L
408920L
#----------------------vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv-------------
#---------------------| |-------------
>>> aStopWATCH.start();NathanListPROCESSOR( aLIST, setA, setB );aStopWATCH.stop()
785334
200755L
196791L
195540L
196606L
202483L
197094L
199481L
196651L
200969L
198856L
202039L
200152L
202364L
根本问题是您没有为工作使用适当的数据结构。
在这种情况下，对于 small 集合，使用元组表示集合可能 ok，
但是对于 large 集，您可以期望搜索平均
列表中每个元素的集合组合大小的一半
那实际上是在其中一个集合中。
对于列表中每个集合中 not 的元素，
我们必须搜索两个集合的所有个元素以确定。
所以任何基于这些数据结构的算法
（即，使用元组表示集合）
最好是 O(m*n)，其中 m 是列表的大小
n 是集合的大小。
我们确实没有任何方法可以减少 m 组件
— 我们必须检查列表的每个元素以确定哪个集合
（如果有的话）它属于。
但是，我们可以减少 n 分量。
如何？通过为我们的集合使用更高效的数据结构。
幸运的是，这并不难，因为 Python 包含一个内置的 set 类型。
所以第一步是构建两个集合：
a = set((1, 3))
b = set((2, 5))
现在，我们可以轻松（高效）确定元素 e 是否在其中一个集合中：
e = 1
e in a # => True
e in b # => False
现在，我们只需要遍历输入列表并累加结果：
l = [1, 1, 3, 2, 5, 7, 8, 3, 2, 1]
result = 0 # accumulator for result
for e in l:
if e in a:
result += 1
elif e in b:
result -= 1
print result # prints "2"
假设我有一个列表
l = [1, 1 , 1, 2, 3, 4, 5, 5]
和两个不相交组等长
a = (1, 3) 和 b = (2, 5)
我想分别获取 a 和 b 中 l 中的元素，例如
[1, 1, 1, 3] 和 [2, 5, 5]
我尝试了像 [x for x in l if x in a] 这样的列表理解，但是如果 l、a 和 b 的长度是 10^5[=29，那需要很长时间=]
编辑：集合是等长的不相交集合。
编辑：我需要做的是计算 l 中常见的 a 中的元素（重复项）减去 [=15= 中的 l 中的元素]（也有重复项）。所以上面的例子应该输出1。问题是列表和集合是否与 10E5 一样长。使用过滤器和 itertools 仍然需要很长时间。
编辑：我现在明白了！显然我必须用 set() 包装输入集！一开始我不知道（我只是通过 input().split() 得到的）因为输入已经是唯一的但不知道列表和集合有很大的不同而且集合更快！好吧，直到我。
您可以使用 itertools 模块中的 chain 和 repeat 函数：
>>> from itertools import repeat,chain
>>> a={1,3}
>>> list(chain.from_iterable((repeat(i,l.count(i)) for i in a)))
[1, 1, 1, 3]
注意：作为一种更有效的方法，您可以为 a 使用 set 容器，它的成员检查复杂度为 O(1)，并且您不需要调用 list 如果您不需要结果作为列表，chain.from_iterable returns 一个 iterator.
或者作为一种非常优化的方法，您可以使用 numpy，这在处理大型列表时特别强大：
>>> import numpy as np
>>> l = np.array([1, 1 , 1, 2, 3, 4, 5, 5])
>>> a = (1, 3)
>>> l[np.in1d(l,a)]
array([1, 1, 1, 3])
l = [1, 1 , 1, 2, 3, 4, 5, 5]
a = (1, 3)
b = (3, 5)
l2 = list(filter(a.__contains__, l)) # [1, 1, 1, 3]
l3 = list(filter(b.__contains__, l)) # [3, 5, 5]
我很想知道这对您的数据集有何影响。
from pandas import Series
l = Series([1, 1 , 1, 2, 3, 4, 5, 5])
a = Series((1, 3))
b = Series((3, 5))
a_answer, b_answer = list(l[l.isin(a)]), list(l[l.isin(b)])
原因：Pandas 的调用实现级别低于 Python，因此根据数字的数据类型，它可能比纯粹的 python 解决方案更适合您。
快吗？
Kasramvd 提出了一个聪明的 np.in1d() 方法和 Wesley 的强大 pandas 框架还建议，让我设置定量标准 以便能够处理个别解决方案的质量。
让我们既公平又量化：
越多，一旦10E+5个物品进入游戏。 处理效率和速度，内存处理，矢量化潜力和（也许）隐藏不利的副作用，CPU-缓存延迟掩蔽更差或更好的关闭-CPU数据访问时间（以及更多的巨魔）-这些都是敌人，我们必须在生产中忍受：
摘要：
Nathan 基于 set 的方法对于所有测试的量表都更快。
Nathan 的方法处理小型 1E+4 和 1E+6 缩放集的速度相当快，利用隐藏在 python 中独特元素的可哈希集合中的有利搜索功能的成果 set-s（因为 set 类型正是为 引入的）。
然而，O( m*n ) / O( n^2 )无法证明。
这些假设的复杂性模型应该意味着，随着 m、n 规模的增长，与 [=20] 相比，基于 numpy 的方法的不利性能损失=] 基于相同 list/set-dataSets 的方法应增长并加速更大的 m,n-s.
增加 set 尺度表明初始边缘在更大的尺度上变得更小。
1:3 在 1E+4 规模上的速度优势降级到仍然尊重，但一些[=109 的优势较小=]1:2 1E+6 规模上的速度优势。
真正的代码执行已经做出了任务 O(m*n)/O(n^2) 复杂度的先验假设，无法在体内确认。
如何测试？
>>> import numpy as np
>>> from zmq import Stopwatch
>>> aStopWATCH = Stopwatch()
>>> l = [1, 1 , 1, 2, 3, 4, 5, 5]
>>> a = (1, 3)
>>> b = (3, 5)
>>> npL = np.array( l )
>>> npL
array([1, 1, 1, 2, 3, 4, 5, 5])
>>> npA = np.array( a )
>>> npA
array([1, 3])
>>> import numba # ______________________________was not me who has said QUICKLY
>>> @numba.jit # QUICKLY
... def getLinA( aListAsNumpyARRAY, aSetAsNumpyARRAY ): # << Kasramvd
... return aListAsNumpyARRAY[ np.in1d( aListAsNumpyARRAY,
aSetAsNumpyARRAY
)
]
>>>
>>> aStopWATCH.start();getLinA( npL, npA );aStopWATCH.stop()
array([1, 1, 1, 3])
113513L # runs a JIT-compiler on a first call ... pay 113,51 [ms]
>>> aStopWATCH.start();getLinA( npL, npA );aStopWATCH.stop()
array([1, 1, 1, 3])
653L # runs a pre-compiled code on 2nd+ ...... wow 0,65 [ms]
855L # runs a pre-compiled code on 2nd+ ...... wow 0,86 [ms]
857L # runs a pre-compiled code on 2nd+ ...... wow 0,86 [ms]
698L # runs a pre-compiled code on 2nd+ ...... wow 0,7 [ms]
690L # runs a pre-compiled code on 2nd+ ...... wow 0,7 [ms]
提示：
是的，没有免费的晚餐。
如您所见，一旦我们不得不为 JIT 编译付出代价。
但是，多亏了 Travis OLIPHANT 出色的 numba 工具，没有人可以阻止我们 "pre-mini-call"（让 JIT 编译器完成它的职责）
getLinA( npL[:2], npA[:2] )
然后重新 运行 已编译的全尺寸
getLinA( npL[:1E+9], npA[:1E+9] )
Ex post 受与 Nathan Davis
思想交流启发的讨论
>>> def NathanListPROCESSOR( aList = [1,1,3,2,5,7,8,3,2,1],
setA = set( ( 1, 3 ) ),
setB = set( ( 2, 3 ) )
):
... accumulator = 0
... for item in aList:
... if item in setA:
... accumulator += 1
... elif item in setB:
... accumulator -= 1
... print accumulator
... return
...
>>> NathanListPROCESSOR() #_______________________EXPECTED: == 2
3 #_______________________O/P DEFINED: == 1
时间：请参考。随着实际代码执行工件的出现，计时结果发生变化（缓存脏度发生变化，）
>>> aStopWATCH.start();NathanListPROCESSOR();aStopWATCH.stop()
3
1207L
491L
279L
350L
1478L
1172L
1698L
1488L
1449L
9688L
1466L
对于缩放到 1E+4 和 1E+6 大小的对象：
>>> aStopWATCH.start();NathanListPROCESSOR( aLIST, setA, setB );aStopWATCH.stop()
-1
2582L
2673L
2529L
2524L
2888L
2693L
>>> aStopWATCH.start();getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
0
129983L
12068L
10699L
10930L
10857L
10999L
10954L
10994L
在 numba 的帮助下：
>>> @numba.jit
... def numba_getLISTinSET( npList, npSetA, npSetB ):
... return ( len( npList[ np.in1d( npList, npSetA ) ] ) -
len( npList[ np.in1d( npList, npSetB ) ] )
)
>>> aStopWATCH.start();numba_getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
0
165320L
7047L
7328L
7378L
7898L
7519L
7556L
7277L
7296L
7292L
7303L
7302L
7426L
7369L
7307L
终于几乎-1E+6天平:
>>> setA = generateSet( 1000000 )
>>> len( setA ) # the cost of uniqueness
235836
>>> setB = generateSet( 1000000 )
>>> npSetA = np.array( list( setA ), dtype = np.int )
>>> npSetB = np.array( list( setB ), dtype = np.int )
>>> aLIST = list( ( np.random.random( 1000000 * 1.1 + 10 ) * 1000000 * 10000 ).astype( np.int ) )[:1000000]
>>> len( aLIST )
1000000
>>> npLIST = np.array( aLIST, dtype = np.int )
#----------------------vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv-------------
#---------------------| |-------------
>>> aStopWATCH.start();numba_getLISTinSET( npLIST, npSetA, npSetB );aStopWATCH.stop()
6
406061L
403946L
409831L
409329L
408920L
#----------------------vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv-------------
#---------------------| |-------------
>>> aStopWATCH.start();NathanListPROCESSOR( aLIST, setA, setB );aStopWATCH.stop()
785334
200755L
196791L
195540L
196606L
202483L
197094L
199481L
196651L
200969L
198856L
202039L
200152L
202364L
根本问题是您没有为工作使用适当的数据结构。 在这种情况下，对于 small 集合，使用元组表示集合可能 ok， 但是对于 large 集，您可以期望搜索平均 列表中每个元素的集合组合大小的一半 那实际上是在其中一个集合中。 对于列表中每个集合中 not 的元素， 我们必须搜索两个集合的所有个元素以确定。
所以任何基于这些数据结构的算法
（即，使用元组表示集合）
最好是 O(m*n)，其中 m 是列表的大小
n 是集合的大小。
我们确实没有任何方法可以减少 m 组件
— 我们必须检查列表的每个元素以确定哪个集合
（如果有的话）它属于。
但是，我们可以减少 n 分量。
如何？通过为我们的集合使用更高效的数据结构。
幸运的是，这并不难，因为 Python 包含一个内置的 set 类型。
所以第一步是构建两个集合：
a = set((1, 3))
b = set((2, 5))
现在，我们可以轻松（高效）确定元素 e 是否在其中一个集合中：
e = 1
e in a # => True
e in b # => False
现在，我们只需要遍历输入列表并累加结果：
l = [1, 1, 3, 2, 5, 7, 8, 3, 2, 1]
result = 0 # accumulator for result
for e in l:
if e in a:
result += 1
elif e in b:
result -= 1
print result # prints "2"