Überprüfen auf Versionsaktualisierungen in zwei großen Listen von Namen und Versionen

Question

Ich habe zwei sehr große Listen von Paketen mit ihren Versionen, und ich versuche, sie zu vergleichen, um festzustellen, ob es irgendwelche gibt, die von einer höheren Version sind. Ein Beispiel meiner Daten:

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'] 

Jetzt muss ich die Pakete finden, die eine höhere Version als ListOne sind. Im obigen Beispiel entsprechen nur binutils den Kriterien.

Diese Listen sind bestellt, aber jede Liste Pakete eindeutig nur selbst, gemeinsame Pakete von der gleichen Version, sowie Pakete mit dem gleichen Namen, sondern nur eine andere Version. Das ist, wonach ich suche. Die Reihenfolge der endgültigen Liste ist erforderlich, und die Pakete müssen ihr aktuelles Benennungsschema beibehalten.

Mein aktueller Code, dies zu tun, ist wie folgt:

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]) 

Die Funktion compareVersions ist eine benutzerdefinierte Funktion, die Wahr zurück, wenn die zweite Version neuer ist als der erste Wert ist. Es gibt einige, die von einer niedrigeren Version sind, die ich nicht will.

Dieser Code ist eine Art Clodgy, und ziemlich langsam, da meine Listen sehr groß sind. Kann ich diesen Vergleichsprozess trotzdem beschleunigen?

Vielen Dank im Voraus.

Answer 1

Sie tun es falsch: für jedes Paket in einer Liste, Sie alle über die zweite iterieren. Komplexität ist M x N (M, N = len (erste), len (zweite)).

Da Pakete bestellt, Sie Iterationen wie in verschmelzenden Algorithmen (macht Schritt auf dem ersten oder zweiten Arrays, die immer kleiner, Drucker, wie es geht) verwenden können. Die Komplexität ist also linear (M + N), nicht quadratisch.

nur ein Hinweis für den Vergleich - würde ich einen Blick in Standardbibliothek nehmen empfehlen distutils.version.LooseVersion

Es kann aus einem beliebigen Zeichenfolge instanziert wird, und dann verglichen werden:

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

Some docs over the internet

Wie Für andere kleine Optimierungen, beachten Sie, dass es eine Menge von gleichwertigen Berechnungen gibt, wie .rsplit Aufrufe, besser eine Variable einführen und wiederverwenden.

Hier ist, wie ich es umsetzen würde:

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 

Eine weitere Implementierung heapq Modul verwenden, kann es schneller sein:

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