Um Python zu beschleunigen, fassen Sie den Umfang der Berechnung des Sammlungstyps (Liste / Tupel / Wörterbuch / Satz) für jeden Zweck zusammen.

Es ist der 6. Tag von Python Part 2 Adventskalender 2019. Gestern war Mr. bluepost59 Notation für extreme Inklusion. Eine umfassende Einführung in Einschlussnotationsmuster, die zur Beschleunigung nützlich sind.

Dieser Artikel soll auch beschleunigen. Um die Leistung einer grundlegenderen Verarbeitung zu organisieren, möchte ich den Umfang der Berechnung des Python-Sammlungstyps (Liste / Tupel / Wörterbuch / Satz) nach Verwendung zusammenfassen.

Im Folgenden finden Sie einen detaillierten Artikel, in dem der Berechnungsaufwand für jeden Sammlungstyp zusammengefasst ist.

• The Python Wiki >>TimeComplexity
• Python Like You Mean It
• Peinliche Menge an Berechnungen, wenn Sie Pythonista nicht kennen

Auf der anderen Seite gab es nicht viele Artikel, in denen verschiedene Berechnungen vom Typ Sammlung für jede Anwendung übersehen werden konnten. Daher möchte ich etwas schreiben, das aus einem anderen Blickwinkel als Referenz verwendet werden kann.

Außerdem werde ich über Python schreiben, eine CPython-Implementierung. Daher ist es für andere Implementierungen wie PyPy möglicherweise nicht hilfreich.

Ausdrucksnotation des Berechnungsbetrags

In diesem Artikel wird die Zeitberechnung in $ O $ -Notation ausgedrückt. Sofern nicht anders angegeben, werden wir den ** durchschnittlichen Berechnungsbetrag ** erörtern. In diesem Artikel bezieht sich $ n $ auf die Länge des Zielsammlungstyps und $ k $ auf die Länge des Sammlungstyps, der hinzugefügt oder gelöscht werden soll.

Ref: Informationen zur Berechnungsreihenfolge

Überprüfungsumgebung

• Python: 3.6.5 --Ausführungsgeschwindigkeitsmessung: Jupyter Magic Command (Timeit)

Verwendungsliste

• [Länge abrufen](# Länge abrufen)
• Referenzwert
• Italation
• [im Operator](#in Operator)
• [Wertzuweisung](# Wertzuweisung)
• [Mehrwert](# Mehrwert)
• [Wert löschen](# Wert löschen)

Länge bekommen

Sie können die Länge jeder Datenstruktur unabhängig von ihrer Größe mit derselben Verarbeitungsgeschwindigkeit abrufen. Da die Länge nicht berechnet wird, sondern die Länge selbst gespeichert wird, sind nur die Referenzkosten erforderlich und betragen $ O (1) $.

Wertreferenz

Werte können für jede Datenstruktur unabhängig von ihrer Größe mit derselben Geschwindigkeit referenziert werden. Der Slice hängt jedoch von der Länge des referenzierten Bereichs ab.

Wiederholung

Jede Datenstruktur kann unabhängig von ihrer Größe mit ungefähr derselben Verarbeitungsgeschwindigkeit iteriert werden.

Allein in Bezug auf den Rechenaufwand entspricht das Iterieren des Index und das Verweisen auf den Wert in der Schleife der in der Tabelle beschriebenen Verarbeitung, in der Realität besteht jedoch ein erheblicher Geschwindigkeitsunterschied, der durch die in der Tabelle angegebene Methode kursiv dargestellt wird. Ich denke es ist gut.

def iter_index(seq:List[int], index:List[int]):
    """Itulate Index und verweisen in einer Schleife darauf"""
    for idx in index:
        seq[idx]

seq = list(range(10000))
index = list(range(len(seq)))
%timeit iter_index(seq, index)
# >>> 281 µs ± 4.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

def iter_list(seq:List[int]):
    """Direkte Iteration des Sammlungstyps"""
    for item in seq:
        item
        
%timeit iter_list(seq)
# >>> 119 µs ± 2.08 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# 2 ~3 mal schneller

im Betreiber

Wie Sie intuitiv sehen können, ist list / tuple $ O (n) $. Außerdem ist dictionary.values () $ O (n) $. Ich denke, es lohnt sich daran zu denken, dass der Rest $ O (1) $ ist. Dies liegt daran, dass der Schlüssel für den Wörterbuchtyp und der Satztyp in der Hash-Tabelle implementiert sind. Weitere Informationen finden Sie im folgenden Artikel. ref: Der Grund, warum es explosiv wurde, indem es in Python von "in list" zu "in set" wechselte

Fall, in dem "im Satz" langsamer ist

Es ist schneller, den Set-Typ für den In-Operator zu verwenden, aber in Wirklichkeit wird der Listentyp häufiger verwendet. Ich denke, dass es viele Fälle gibt, in denen der Listentyp in den Set-Typ konvertiert und dann an den In-Operator übergeben wird. .. In Anbetracht der Konvertierungskosten ist Vorsicht geboten. (Im Folgenden werden wir nur die Liste untersuchen, aber das gleiche Argument wird mit Tupel anstelle von Liste vorgebracht.) Wenn ich tatsächlich "in Liste", "in Satz" und "Umwandlung von Liste in Satz & in Satz" gemessen habe, wurden die folgenden Ergebnisse erhalten.

# 「in list」
lists = list(range(100000))
%timeit 50000 in lists
# >>> 622 µs ± 47.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# 「in set」
sets = set(lists)
%timeit 50000 in sets
# >>> 54.8 ns ± 4.39 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

#"Konvertierung von Liste zu Set& in set」
%timeit 50000 in set(lists)
# >>> 2.94 ms ± 61.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Bei der Messung der Dampfbehandlung mit verschiedenen Größen,

Mit anderen Worten

• "In Set" ist schneller als "In List". Je größer die Größe, desto größer ist der lineare Geschwindigkeitsunterschied
• "Konvertierung von Liste zu Set & in Set" ist jedoch ** etwa 3 bis 5 mal langsamer als "in Liste" **

Daher kann in den folgenden Fällen die Verwendung von "in set" ** eher langsamer werden **.

--Liste zum Festlegen der erforderlichen Konvertierung --Und die Häufigkeit, mit der "im Satz" im konvertierten Satz verwendet wird, beträgt weniger als etwa das Fünffache

Wertzuweisung

Die Zuweisung bezieht sich auf eine Operation, die den Wert und nicht die Länge ändert. Der Wert von set kann nicht geändert werden und muss gelöscht und hinzugefügt werden.

Mehrwert

Der Umfang der Berechnung für die Liste hängt davon ab, wo Sie den Wert hinzufügen. Ich denke, der Algorithmus sollte den Wert am Ende so weit wie möglich enthalten. Außerdem sind alle oben genannten Ergänzungen destruktiv (es sind keine mehr vorhanden, bevor sie hinzugefügt werden), sodass Sie unerwartete negative Auswirkungen haben können, wenn Sie den Umfang der Variablen nicht berücksichtigen.

Sequentielles Hinzufügen oder Verbinden

Bei der Entscheidung, welcher Wert nach dem Filtern mit einem bedingten Ausdruck hinzugefügt werden soll, stehen zwei Optionen zur Verfügung.

• Fügen Sie während des Filters nacheinander Werte hinzu
• Kombinieren Sie diese nach dem Erstellen eines Sammlungstyps von Werten, die vom Filter hinzugefügt werden sollen

Intuitiv scheint es weniger verschwenderisch zu sein, nacheinander hinzuzufügen, aber in Python ist for langsam und es ist besser, die Einschlussnotation so oft wie möglich zu verwenden, so dass es ein subtiles Problem ist. Die Ergebnisse des Versuchs sind unten gezeigt. Aus dem Ergebnis geht hervor, dass es keinen großen Geschwindigkeitsunterschied gibt. Ich möchte diejenige verwenden, die bequem ist. Persönlich bevorzuge ich die letztere Methode, weil die Einschlussnotation weniger Nebenwirkungen hat (weil sie weniger Wertzuweisung / Definition erfordert).

aufführen

Wenn die Iteration des hinzuzufügenden Werts lang ist, scheint es schneller zu sein, eine Liste einmal in der Einschlussnotation zu erstellen und sie dann zu erweitern. Hinweis 1) Wenn Sie eine destruktive Addition vornehmen, ändert sich die Größe und die Messung ist ungenau. Kopieren Sie die Liste und senden Sie sie an die Funktion. Hinweis.2) Das Anhängen ist bekanntermaßen langsam. Weisen Sie es daher einer Variablen zu und verwenden Sie es dann in einer Schleife (Referenz: Geschwindigkeit der Python-Listeneinschlussnotation fr / items / 43f90e07e4cebe63aeb6)))

def addition_extend(base:List[int], add:List[int]):
    add = [f for f in add if f]
    base.extend(add)
    return base

def addition_append(base:List[int], add:List[int]):
    base_a = base.append
    for ad in add:
        if ad:
            base_a(ad)
    return base

base = list(range(10000))
add = list(range(10))
%timeit addition_extend(copy(base), add)
# >>> 43.9 µs ± 6.94 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit addition_append(copy(base), add)
# >>> 39 µs ± 66.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

base = list(range(10))
add = list(range(10000))
%timeit addition_extend(copy(base), add)
# >>> 373 µs ± 45.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_append(copy(base), add)
# >>> 540 µs ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Wörterbuch

Ich habe auch das Wörterbuch ausprobiert. Das Wörterbuch scheint für die sequentielle Zuweisung schneller zu sein. Da die Schwankung jedoch groß ist, scheint es keinen großen Unterschied zu geben.

def addition_update(base:Dict[str, int], add:Dict[str, int]):
    add = {f: g for f, g in add.items() if g}
    base.update(add)
    return base

def addition_assign(base:Dict[str, int], add:Dict[str, int]):
    for ad, val in add.items():
        if val:
            base[ad] = val
    return base

base = {str(f): f for f in range(10000)}
add = {str(f): f for f in range(10)}
%timeit addition_update(copy(base), add)
# >>> 365 µs ± 62.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_assign(copy(base), add)
# >>> 312 µs ± 16.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


base = {str(f): f for f in range(10)}
add = {str(f): f for f in range(10000)}
%timeit addition_update(copy(base), add)
# >>> 1.16 ms ± 35.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_assign(copy(base), add)
# >>> 919 µs ± 45.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Wert löschen

Die Liste sollte beim Löschen von Werten so weit wie möglich auf die Rückseite beschränkt sein. Das Problem ist, was passiert, wenn mehrere Werte gelöscht werden müssen. Intuitiv scheint die Wiederherstellung schneller zu sein, wenn die Anzahl der zu löschenden Werte zunimmt. Wir werden diesbezüglich die folgenden zwei Punkte untersuchen. Ich werde das Ergebnis zuerst schreiben.

--pop vs Slice: ** Slice ** sieht besser aus --delete vs recreate: ** recreate ** sieht besser aus

pop vs slice Pop eine Liste der Größe n k mal für $ O (k) $ und Slice für $ O (n-k) $. Wenn jedoch n> k ist, kann es kein Pop sein, und wenn n <k, kann es kein Slice sein, also habe ich die Geschwindigkeit mit dem folgenden Code gemessen.

def pop(seq:List[int], num:int):
    for i in range(num):
        seq.pop()

def slices(seq:List[int], num:int):
    seq[:-num]

Unten finden Sie eine Tabelle, die das Ausführungsgeschwindigkeitsverhältnis von Pop und Slice durch Ändern der Länge der Liste und der Anzahl der Löschvorgänge misst. *** Dies ist der Fall, wenn die Scheibe schneller war als der diagonale Teil ***. Grundsätzlich scheint Slice besser zu sein.

löschen vs neu erstellen

Wenn Sie die Liste der Größe n k Mal löschen, ist sie $ O (kn) $, und wenn Sie sie neu erstellen, ist sie $ O (n) $. Natürlich scheint es schneller zu sein, es neu zu erstellen, aber ich habe die Geschwindigkeit mit dem folgenden Code gemessen.

def delete(lists:List[int], cond:Set[int]):
    for con in cond:
        try:
            lists.remove(con)
        except ValueError:
                pass
    return lists

def recreate(lists:List[int], cond:Set[int]):
    return [f for f in lists if f not in cond]

In der folgenden Tabelle wird das Ausführungsgeschwindigkeitsverhältnis von Löschen und Neuerstellen durch Ändern der Länge der Liste und der Anzahl der Löschvorgänge gemessen. *** Dies ist der Fall, wenn der Wiederaufbau für den schrägen Teil schneller war ***. Grundsätzlich scheint die Neuerstellung besser zu sein.

Zusammenfassung

Der Umfang der Berechnung des Sammeltyps wird nach Verwendung zusammengefasst. Python soll eine langsame Sprache sein, aber ich hoffe, es hilft Ihnen, die Verarbeitungszeit zu bekommen, die Sie tolerieren können!

Morgen ist typecprint!

refs

• The Python Wiki >>TimeComplexity
• Python Like You Mean It
• Peinliche Menge an Berechnungen, wenn Sie Pythonista nicht kennen
• Berechnungsreihenfolge
• Angelegenheit, die nur durch den Wechsel von "in list" zu "in set" in Python und dem Grund explosiv wurde
• Notation der Geschwindigkeit der Python-Liste