4

在两个python列表的开头找到共同元素的最快方法是什么？我使用 for 循环对其进行了编码，但我认为用列表推导编写它会更快......不幸的是，我不知道如何在列表推导中打断。这是我写的代码：

import datetime

list1=[1,2,3,4,5,6]
list2=[1,2,4,3,5,6]

#This is the "for loop" version, and takes about 60 ms on my machine
start=datetime.datetime.now()
out=[]
    for (e1, e2) in zip(list1, list2):
    if e1 == e2:
        out.append(e1)
    else:
        break
end=datetime.datetime.now()
print out
print "Execution time: %s ms" % (float((end - start).microseconds) / 1000)

#This is the list-comprehension version, it takes about 15 ms to run,
#but unfortunately returns the wrong result because I can't break the loop.
start=datetime.datetime.now()
out = [ e1 for (e1, e2) in zip(list1, list2) if e1 == e2 ]
end=datetime.datetime.now()
print out
print "Execution time: %s ms" % (float((end - start).microseconds) / 1000)

没有列表理解也有好的解决方案吗？

4

5 回答 5

11 
>>> from operator import ne
>>> from itertools import count, imap, compress
>>> list1[:next(compress(count(), imap(ne, list1, list2)), 0)]
[1, 2]

时间：

from itertools import *
from operator import ne

def f1(list1, list2, enumerate=enumerate, izip=izip):
    out = []
    out_append = out.append
    for e1, e2 in izip(list1, list2):
        if e1 == e2:
            out_append(e1)
        else:
            break
    return out

def f2(list1, list2, list=list, takewhile=takewhile, izip=izip):
    return [i for i, j in takewhile(lambda (i,j):i==j, izip(list1, list2))]

def f3(list1, list2, next=next, compress=compress, count=count, imap=imap,
       ne=ne):
    return list1[:next(compress(count(), imap(ne, list1, list2)), 0)]

def f4(list1, list2):
    out = []
    out_append = out.append
    i = 0
    end = min(len(list1), len(list2))
    while i < end and list1[i]==list2[i]:
        out_append(list1[i])
        i+=1
    return out

def f5(list1, list2, len=len, enumerate=enumerate):
    if len(list1) > len(list2):
        list1, list2 = list2, list1
    for i, e in enumerate(list1):
        if list2[i] != e:
            return list1[:i]
    return list1[:]

def f6(list1, list2, enumerate=enumerate):
    result = []
    append = result.append
    for i,e in enumerate(list1):
        if list2[i] == e:
            append(e)
            continue
        break
    return result


from timeit import timeit
list1 =[1,2,3,4,5,6];list2=[1,2,4,3,5,6]
sol = f3(list1, list2)

for func in 'f1', 'f2', 'f3', 'f4', 'f5', 'f6':
    assert eval(func + '(list1, list2)') == sol, func + " produces incorrect results"
    print func
    print timeit(stmt=func + "(list1, list2)", setup='from __main__ import *')

f1
1.52226996422
f2
2.44811987877
f3
2.04677891731
f4
1.57675600052
f5
1.6997590065
f6
1.71103715897

对于定制的list1=[1]*100000+[1,2,3,4,5,6]; list2=[1]*100000+[1,2,4,3,5,6]时间，timeit100timeit(stmt=func + "(list1, list2)", setup='from __main__ import list1, list2, f1,f2,f3,f4', number=1000)

f1
14.5194740295
f2
29.8510630131
f3
12.6024291515
f4
24.465034008
f5
12.1111371517
f6
16.6644029617

所以@ThijsvanDien 的这个解决方案是最快的，紧随其后，但我仍然喜欢它的功能风格；）

但numpy总是赢（你应该总是使用numpy这样的东西）

>>> import numpy as np
>>> a, b = np.array([1,2,3,4,5,6]), np.array([1,2,4,3,5,6])
>>> def f8(a, b, nonzero=np.nonzero):
        return a[:nonzero(a!=b)[0][0]]

>>> f8(a, b)
array([1, 2])
>>> timeit(stmt="f8(a, b)", setup='from __main__ import *')
6.50727105140686
>>> a, b = np.array([1]*100000+[1,2,3,4,5,6]), np.array([1]*100000+[1,2,4,3,5,6])
>>> timeit(stmt="f8(a, b)", setup='from __main__ import *', number=1000)
0.7565150260925293

可能有更快的numpy解决方案，但这表明它有多快。

于 2013-05-20T09:15:52.850 回答
4 
>>> from itertools import izip, takewhile
>>> list1=[1,2,3,4,5,6]
>>> list2=[1,2,4,3,5,6]
>>> list(takewhile(lambda (i,j):i==j, izip(list1, list2)))
[(1, 1), (2, 2)]

或者

>>> list(takewhile(lambda i,j=iter(list2):i==next(j), list1))
[1, 2]
于 2013-05-20T09:12:08.140 回答
2

我不明白为什么人们会痴迷于在一行中这样做。这是我的解决方案：编辑： @roots 建议在本地存储append方法。result

result = []
append = result.append
for i,e in enumerate(List1):
    if List2[i] == e:
        append(e)
        continue
    break

有输入：

List1 = [1,2,3,4,5,9,8,1,2,3]
List2 = [1,2,3,5,5,9,8,1,2,3]

生产

>>> 
[1, 2, 3]

根据@jamylak 的测试：（a.py）

print(timeit.timeit("""
result = []
append = result.append
for i,e in enumerate(List1):
    if List2[i] == e:
        append(e)
        continue
    break""",
setup="List1 =[1]*10000+[1,2,3,4,5,6];List2=[1]*10000+[1,2,4,3,5,6]",number=1000))

我明白了

Microsoft Windows [Version 6.2.9200]
(c) 2012 Microsoft Corporation. All rights reserved.

C:\Users\Henry\Desktop>a.py
0.770009684834

这使得它非常接近@dugres 解决方案，该解决方案在0.752079322295

于 2013-05-20T10:22:24.060 回答
2

此解决方案受@HennyH 启发，与@jamylak 的长列表最快速度一样快，而短列表速度更快，并且可以说更具可读性：

def f5(list1, list2):
    if len(list1) > len(list2):
        list1, list2 = list2, list1
    for i, e in enumerate(list1):
        if list2[i] != e:
            return list1[:i]
    return list1[:]

时间安排（针对短名单）：

f1
1.17119693756
f2
1.82656407356
f3
1.51235413551
f4
1.45300602913
f5
1.13586807251

时间安排（对于长列表）：

f1
1.52571296692
f2
2.99596500397
f3
1.02547097206
f4
2.44235897064
f5
1.02724885941

请注意使用 PyPy 2.0.1 时非常有趣的结果：

f1
0.221760034561
f2
0.210422992706
f3
5.4270939827
f4
0.20907497406
f5
0.0702250003815
于 2013-05-20T10:36:29.210 回答
1

没有“压缩”和“附加”会更快： 

i = 0
while list1[i]==list2[i]:
    i+=1
out = list1[:i]
于 2013-05-20T09:22:47.960 回答