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

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 是一个自定义函数，如果第二个版本比第一个值更新，它将 return 为真。有的是低版本的，我不要。

这段代码有点笨拙，而且速度很慢，因为我的列表非常庞大。无论如何我可以加快这个比较过程吗？

提前致谢。

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

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

Checking for version updates in two large lists of names and versions

python

optimization

performance

package-managers

python-3.x