在两个大名单和版本列表中检查版本更新

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