Die Art des Tupel-Arrays kann durch Angabe des Schlüssels (Python) beschleunigt werden.

Einführung

Als ich mir Sorgen um "TLE, obwohl es pünktlich zum Berechnungsbetrag zu sein scheint ..." machte, während ich mich dem Wettbewerbsprofi widmete, stellte sich heraus, dass der sortierte Teil der Vorbereitung ein Engpass war. Teilen Sie die Punkte, nach denen Sie süchtig sind.

Art Tupel-Array

Ich werde kurz den Unterschied zwischen mit und ohne Schlüsselspezifikation erklären.

Schlüssel angegeben

a = [(3,3), (2,2), (3,1), (4,2)]
a.sort(key=lambda x: x[0])
print(a) # => [(2, 2), (3, 3), (3, 1), (4, 2)]

Die Sortierung erfolgt nach der Größe des angegebenen Schlüssels. Wenn die Elemente des Schlüssels gleich sind, bleibt die Reihenfolge erhalten.

Die sort () -Methode ist garantiert stabil. Die Sortierung ist stabil, solange garantiert wird, dass sich die relative Reihenfolge gleicher Elemente nicht ändert. (Offizielles Dokument)

(x[0],x[1]))Es ist möglich, mehrere Schlüssel mit Tupel wie in anzugeben, aber

 In diesem Artikel wird die Angabe eines einzelnen Elements als Schlüssel in Betracht gezogen.



## Kein Schlüssel angegeben
 Wenn Sie keinen Schlüssel angeben
 "Größenvergleich mit dem 0. Element des Tupels" -> "Größenvergleich mit dem 1. Element, wenn sie gleich sind" -> "..."
 Die Sortierung erfolgt auf diese Weise.

```python
a = [(3,3), (2,2), (3,1), (4,2)]
a.sort()
print(a) # => [(2, 2), (3, 1), (3, 3), (4, 2)]

Zu diesem Zeitpunkt scheint die Vergleichsoperation zwischen Tupeln intern durchgeführt zu werden.

key gibt eine Funktion an, die ein Argument akzeptiert und zum Abrufen des Vergleichsschlüssels aus jedem Element der Liste verwendet wird (z. B. key = str.lower). Der jedem Artikel entsprechende Schlüssel wird einmal berechnet und für den gesamten Sortiervorgang verwendet. ** Der Standardwert None bedeutet, dass die Werte in der Liste direkt sortiert werden, ohne einen anderen Schlüsselwert zu berechnen. ** (Offizielles Dokument)

Wenn Sie nur "nach dem ersten Element des Tupels sortieren", können Sie den Zweck mit oder ohne Schlüsselspezifikation erreichen. Wenn Sie den Schlüssel hier nicht angeben und denken ** "Dann müssen Sie den Schlüssel nicht angeben" **, können Sie in eine unerwartete Falle geraten. ** Der Vergleich zwischen Tupeln ist langsam. ** **.

Experiment

"Vergleich zwischen Tupeln" vs. "Vergleich zwischen Tupelelementen"

Überprüfen Sie, wie groß der Geschwindigkeitsunterschied zwischen den beiden ist. Die Ausführungsumgebung ist der Code-Test von AtCoder (PyPy3). Jedes Tupel enthält 3 Elemente.

import random
random.seed(1)

''' n:3 Möglichkeiten
N = 1*(10**3)
N = 3*(10**3)
N = 5*(10**3)
'''

tl = [] # list of tuples
for i in range(N):
    l = random.randint(1,N)
    r = random.randint(1,N)
    tl.append((l,r,i)) # 3 elements in tuple

''' 
# 1.Vergleich zwischen Tupeln
for i in range(N):
    for j in range(N):
        res = tl[i] < tl[j]
# 2.Vergleich von Tupelelementen
for i in range(N):
    for j in range(N):
        res = tl[i][0] < tl[j][0]
'''

Die Messergebnisse sind wie folgt.

Da es drei Elemente des Tapples gibt, dachte ich: "Ist es ein Fehler von höchstens dreimal?", Aber es gab einen großen Unterschied. erschrocken.

Tupel-Array-Sortierung "Schlüssel nicht angegeben" vs. "Schlüssel angegeben"

import random
random.seed(1)

''' n:3 Möglichkeiten
N = 1*(10**5)
N = 3*(10**5)
N = 5*(10**5)
'''

tl = [] # list of tuples
for i in range(N):
    l = random.randint(1,N)
    r = random.randint(1,N)
    tl.append((l,r,i)) # 3 elements in tuple

'''
3. tl.sort()
4. tl.sort(key=lambda x:x[0])
'''

Die Messergebnisse sind wie folgt.

Obwohl nicht so groß wie im ersten Experiment, war der Unterschied etwa doppelt so groß.

abschließend

Es mag kein großer Unterschied sein, aber je nach Problem kann dies süchtig machen. Einige Leute haben vielleicht den Code des Experiments gesehen und sich gefragt: "Ist das das Problem?" Übrigens scheint es, dass `itemgetter``` für die Schlüsselspezifikation schneller ist als` Lambda```.