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

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（第一），len（第二））

假设包是有序的，您可以像在合并算法中一样使用迭代（在第一个或第二个数组上进行步进，这两个数组越小，就越打印结果）。因此，复杂性将是线性的（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