找到兩個列表相同的基於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的位置

回答

相關問題