在兩個大名單和版本列表中檢查版本更新

Question

我有兩個非常大的軟件包列表及其版本，我試圖比較它們以確定是否有更高版本的軟件包。我的數據的一個例子：

listOne = ['autoconf-2.69-4', 'b43-fwcutter-019-1', 'binutils-2.28.0-3'] 
listTwo = ['autoconf-2.69-4', 'automake-1.16-1', 'binutils-2.29.0-1'] 

現在我需要找到一個比一個那麼listOne高版本的軟件包。在上面的例子中，只有binutils符合條件。

這些列表是有序的，但每個列表具有獨特的相同版本的只有自己，共享套餐，以及同名的包，但只有一個不同版本的軟件包。那些是我正在尋找的。最終列表的順序是必需的，並且軟件包必須保持其當前的命名方案。

我當前的代碼要做到這一點，如下所示：

listOne = ['autoconf-2.69-4', 'b43-fwcutter-019-1', 'binutils-2.28.0-3'] 
listTwo = ['autoconf-2.69-4', 'automake-1.16-1', 'binutils-2.29.0-1'] 

uniqPackages = sorted(list(set(listTwoPackages) - set(listOnePackages))) 

for package in uniqPackages: 
    for packageFull in listOne: 
     if packageFull.rsplit("-", 2)[0] == package.rsplit("-", 2)[0]: 
      versionValue = compareVersions(packageFull.rsplit("-", 2)[1] + "-" + packageFull.rsplit("-", 2)[2], \ 
       package.rsplit("-", 2)[1] + "-" + package.rsplit("-", 2)[2]) 
      if versionValue: 
       print(package.rsplit("-", 2)[0] + "-" + package.rsplit("-", 2)[1] + "-" + package.rsplit("-", 2)[2]) 

功能compareVersions是一個自定義函數，將返回True如果第二個版本比第一個值更新。有一些版本較低，我不想要。

這段代碼有點笨拙，而且相當慢，因爲我的列表非常龐大。無論如何，我可以加快這個比較過程嗎？

在此先感謝。

Answer 1

你就錯了： 爲每包在一個列表中，則遍歷所有第二。 複雜性是M x N（M，N = len（first），len（second））。

由於包是有序的，你可以在合併算法使用迭代像（使在第一或第二陣列，它曾經是因爲它去越小，打印結果步驟）。所以，複雜性將是線性的（M + N），而不是方形。

只是爲了比較的暗示 - 我建議看看成標準庫distutils.version.LooseVersion

它可以從任何字符串被實例化，然後進行比較：

LooseVersion('19.1-alpha') < LooseVersion('19.3') 
LooseVersion('19.10-alpha') > LooseVersion('19.3') 

Some docs over the internet

由於對於其他小優化，請注意，有很多重複的相同值計算，如調用.rsplit，更好地引入變量並重用它。

這是我將如何實現它：

from distutils.version import LooseVersion 

def compare_versions(a, b): 
    return LooseVersion(a) < LooseVersion(b) 

i, j = 0, 0 
M, N = len(first_packages), len(second_packages) 

while i < M and j < N: 
    package_f, version_f, minor_f = first_packages[i].rsplit('-', 2) 
    package_s, version_s, minor_s = second_packages[j].rsplit('-', 2) 

    if package_f == package_s: 
     if compare_versions(
      '-'.join((version_f, minor_f)), 
      '-'.join((version_s, minor_s)) 
     ): 
      print(second_packages[j]) 
     i += 1 
     j += 1 
    else: 
     if package_f < package_s: 
      i += 1 
     else: 
      j += 1 

使用heapq模塊另一種實現，它可能更快：

import heapq 
last = '' 
name = lambda p: p.rsplit('-', 2)[0] 
version = lambda p: '-'.join(p.rsplit('-', 2)[-2:]) 
for pckg in heapq.merge(first_packages, second_packages, key=name): 
    if last and name(last) == name(pckg) and compareVersions(
     version(last), version(pckg) 
    ): 
     print(pckg) 
    else: 
     last = pckg