Le tri du tableau de tuple peut être accéléré en spécifiant une clé (Python)

introduction

Quand je m'inquiétais de "TLE même s'il semble être à temps pour le montant du calcul ..." en me consacrant à la concurrence, on a découvert que le genre de préparation était un goulot d'étranglement. Partagez les points auxquels vous êtes accro.

sorte de tableau tuple

Je vais expliquer brièvement la différence entre avec et sans spécification de clé.

clé spécifiée

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

Le tri est effectué en fonction de la taille de la clé spécifiée. Si les éléments de clé sont égaux, l'ordre est conservé.

La méthode sort () est garantie pour être stable. Le tri est stable tant qu'il est garanti que l'ordre relatif des éléments égaux ne changera pas. (Document officiel)

(x[0],x[1]))Il est possible de spécifier plusieurs clés avec tuple comme dans, mais

 Dans cet article, nous envisagerons de spécifier un seul élément comme clé.



## Aucune clé spécifiée
 Si vous ne spécifiez aucune clé
 "Comparer la taille au 0ème élément du tuple" → "Comparer la taille au 1er élément s'ils sont identiques" → "..."
 Le tri se fait de cette manière.

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

À ce stade, il semble que l'opération de comparaison entre les tuples soit effectuée en interne.

key spécifie une fonction qui prend un argument et est utilisée pour récupérer la clé de comparaison de chaque élément de la liste (par exemple, key = str.lower). La clé correspondant à chaque article est calculée une fois et utilisée pour tout le processus de tri. ** La valeur par défaut Aucun signifie que les valeurs de la liste seront triées directement sans calculer une autre valeur de clé. ** (Document officiel)

Si vous "triez simplement par le premier élément du tuple", vous pouvez atteindre l'objectif avec ou sans spécification de clé. Si vous ne spécifiez pas la clé ici, en pensant ** "Alors vous n'avez pas besoin de spécifier la clé" **, vous risquez de tomber dans un piège inattendu. ** La comparaison entre les tuples est lente. ** **

Expérience

"Comparaison entre les tuples" et "Comparaison entre les éléments de tuples"

Vérifiez la différence de vitesse entre les deux. L'environnement d'exécution est le test de code d'AtCoder (PyPy3). Il y a 3 éléments dans chaque tuple.

import random
random.seed(1)

''' n:3 façons
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.Comparaison entre les tuples
for i in range(N):
    for j in range(N):
        res = tl[i] < tl[j]
# 2.Comparaison des éléments de tuple
for i in range(N):
    for j in range(N):
        res = tl[i][0] < tl[j][0]
'''

Les résultats de mesure sont les suivants.

Puisqu'il y a trois éléments du tapple, j'ai pensé: "Est-ce une erreur d'environ 3 fois au maximum?", Mais il y avait une grande différence. effrayé.

tri par tableau de tuple "clé non spécifiée" vs "clé spécifiée"

import random
random.seed(1)

''' n:3 façons
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])
'''

Les résultats des mesures sont les suivants.

Bien que pas autant que dans la première expérience, la différence était environ deux fois plus grande.

en conclusion

Ce n'est peut-être pas une grande différence, mais selon le problème, cela peut créer une dépendance. Certaines personnes ont peut-être vu le code de l'expérience et se sont demandé: "Est-ce là le problème?" Au fait, il semble que itemgetter soit plus rapide que `` `lambda``` pour la spécification de clé.