找到两个列表相同的基于1的位置

挑战是编写一个函数来比较两个相当小的整数列表（每个小于10个元素）。一个列表可能是这样的：找到两个列表相同的基于1的位置

self = [0, 0, 1, 2]

名单，它是要比较有可能看起来像以下示例之一：

other1 = [] 
other2 = [0, 0, 1] 
other3 = [0, 0, 1, 2, 0] 
other4 = [0, 1, 1, 2] 
other5 = something

正如你所看到的，重复的元素是相当普遍元素的顺序很重要。

预期结果应该是一个整数，表示self和other是相同的长度，从开始算起。因此，根据另一方面，其结果必然是：

result1 = 0 
result2 = 3 
result3 = 4 
result4 = 1 
result5 = 0

的代码应该是最有效的，因为它是使用约100次，每个用户交互。

我编码以下，它的工作原理是需要，但似乎是一种缓慢：

def match(self, other): 
    if self == other: 
     return len(self) 
    element = -1 
    for element in range(min(len(self), len(other))): 
     if self[element] != other[element]: 
      element -= 1 
      break 
    return element +1

第一个if语句已增强加快速度，但解决方案还是有些慢，也看起来有点笨拙，对所有对名为element的变量和两个return语句进行更正。

有没有人比这个函数的名字比'match'或'compare'更好？

来源

2013-03-17 Richard

'common_prefix_size（list1，list2）'可能比'match'更好的名字 – jfs 2013-03-18 14:41:08

在related question，我发表了以下可能的解决方案：

def while_equal(seq, other): 
    for this, that in zip(seq, other): 
     if this != that: 
      return 
     yield this 

def match(seq, other): 
    return sum(1 for _ in while_equal(seq, other))

和

def match_loop(seq, other): 
    count = 0 
    for this, that in zip(seq, other): 
     if this != that: 
      return count 
     count += 1 
    return count

这些版本比其他给定的解决方案速度更快（第二个是最快），而且，我认为，更具可读性。

来源

2013-03-18 13:41:28

它肯定更具可读性！谢谢。 – Richard 2013-03-18 14:26:14

>>> from itertools import takewhile, izip 
>>> def F(seq1, seq2): 
     return sum(1 for x in takewhile(lambda x: x[0] == x[1], izip(seq1, seq2))) 

>>> F([0, 0, 1, 2], [0, 0, 1, 2, 0]) 
4

来源

2013-03-17 05:43:14 jamylak

它的文档可以在http://docs.python.org/2/library/collections.html和http：// docs.python.org/2/library/itertools.html – Richard 2013-03-17 09:50:49

令人惊讶的性能结果：http://stackoverflow.com/questions/15477314/performance-of-library-itertools-compared-to-python-code – Richard 2013-03-18 12:54:22

@Richard我didn预计这在原始速度上是最快的，我为了清晰起见而编写了它，但它被写为最快的算法，我同意其他答案的清晰度是最重要的。如果你想完全优化运行时间，只需用C语言编写。另外你也可以在其他答案中看到，你可以做更多的调整来加快python的速度，但我总是喜欢优雅的代码。 – jamylak 2013-03-18 17:49:17

编辑：为jamylak指出的那样，我的解决方法是错误的。我会把它留在这里，所以每个想回答这个问题的人都会看到整个问题，而不仅仅是前两种情况。

另一种不需要itertools的解决方案虽然效率不如jamylak's solution。

def compareLists(list1, list2): 
    return sum(map(lambda (x,y): 1 if x == y else 0, zip(list1, list2)))

来源

2013-03-17 09:00:36 aga

我之前做过类似的事情，但后来我意识到这并不止于此。尝试案例4 – jamylak 2013-03-17 09:08:26

@ jamylak你是完全正确的，我没有考虑过案例4. :) – aga 2013-03-17 09:17:35

找到两个列表相同的基于1的位置

回答

相关问题