如何快速比较列表和集合?

2024-03-28 09:17:00 发布

您现在位置:Python中文网/ 问答频道 /正文

假设我有一张单子

l = [1, 1 , 1, 2, 3, 4, 5, 5]

以及两个长度相等的不相交的集合

a = (1, 3)b = (2, 5)

我想分别得到l中的元素,也就是ab中的元素

[1, 1, 1, 3][2, 5, 5]

我尝试了列表理解,比如[x for x in l if x in a],但是如果lab的长度是10^5,那就需要很长时间

编辑:集合是长度相等的不相交集合。你知道吗

编辑:我需要做的是计算l中的元素,这在a中是常见的(有重复项),减去bl的元素(也有重复项)。所以上面的例子应该输出1。问题是列表和集合的长度是否与10E5一样长。使用filter和itertools仍然需要很长时间。你知道吗

编辑:我现在明白了!显然,我必须用set()包装输入集!一开始我没有(我只是通过input().split()得到的),因为输入已经是唯一的,但不知道列表和集合非常不同,集合更快!好吧,直到我。你知道吗


Tags: in元素编辑列表forinputiffilter
3条回答

快点?你知道吗

由于Kasramvd提出了一种聪明的方法,Wesley的马力框架也被提出了,所以让我来设定一个定量的尺度,使之能够处理单个的解决方案。你知道吗

让我们既公平又量化:

更多的,一旦10E+5项目在游戏中。处理的效率和速度、内存处理、矢量化潜在的和(可能)隐藏的不良副作用、CPU缓存延迟掩蔽较差或较好的非CPU数据访问时间(以及更多的troll)-这些都是敌人,我们必须在生产中生活:


总结:

Nathan基于set的方法对于所有被测试的量表来说都要快得多。你知道吗

Nathan的方法处理小的,1E+41E+6缩放集的速度要快得多,它利用了隐藏在set-s中独特元素的python哈希集合中的有利搜索能力(正如set类型正是为其引入的)。你知道吗

然而,O( m*n )/O( n^2 )不能被证明。你知道吗

这些假定的复杂度模型应该意味着,随着mn规模的增长,基于numpy的方法与基于相同list/set数据集的基于set的方法相比,对更大的mn数据集的不利性能惩罚将增长并加速

随着set尺度的增大,初始边缘在更大尺度上变得更小。你知道吗

1:3速度优势在1E+4尺度上有所下降,但部分
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] )

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+41E+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

您可以使用来自itertools模块的chainrepeat函数:

>>> 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返回一个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])

根本的问题是您没有为作业使用适当的数据结构。 在这种情况下,使用元组表示集合可能是ok对于small集合, 但是对于大型集合,您可以期望搜索平均值 列表中每个元素的集合总大小的一半 这实际上是其中一组。 对于列表中不是的每个元素, 我们必须搜索两个集合的所有元素来确定这一点。你知道吗

所以任何基于这些数据结构的算法 (即,用元组表示集合) 充其量是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"

相关问题 更多 >