在2个python列表的开头找到公共元素的最快方法是什么？

Question

在两个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)

在没有列表理解的情况下也有好的解决方案吗？

Answer 1

>>> 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

对于具有定制为100计时的timeit的list1=[1]*100000+[1,2,3,4,5,6]; list2=[1]*100000+[1,2,4,3,5,6]，timeit(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解决方案，但这显示了它有多快。

Answer 2

>>> 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]

Answer 3

我不明白为什么人们总是痴迷于用一句话来做这件事。这是我的解决方案：EDIT:，@roots建议将result的append方法存储在本地。

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上发布