C'est le 6ème jour du Calendrier de l'Avent Python Partie 2 2019. Hier, c'était M. bluepost59 Notation d'inclusion extrême. Une introduction complète des modèles de notation d'inclusion utiles pour accélérer.
Cet article vise également à accélérer. Afin d'organiser les performances d'un traitement plus basique, je voudrais résumer la quantité de calcul du type de collection de python (liste / tuple / dictionnaire / ensemble) en fonction de l'utilisation.
Voici un article détaillé qui résume le montant du calcul pour chaque type de collection.
D'un autre côté, il n'y avait pas beaucoup d'articles qui pouvaient ignorer divers calculs de type collection pour chaque application, alors j'aimerais écrire quelque chose qui puisse être utilisé comme référence sous un angle différent.
De plus, j'écrirai sur Python, qui est une implémentation CPython. Par conséquent, cela peut ne pas être utile pour d'autres implémentations telles que PyPy.
Dans cet article, le temps de calcul est exprimé en notation $ O $. Sauf indication contraire, nous discuterons du ** montant moyen du calcul **. De plus, dans cet article, $ n $ fait référence à la longueur du type de collection cible et $ k $ fait référence à la longueur du type de collection à ajouter ou à supprimer.
| symbole | Montant du calcul | Aperçu |
|---|---|---|
| Temps constant | La vitesse de traitement ne dépend pas de la taille | |
| Temps linéaire | La vitesse de traitement est proportionnelle à la taille du premier ordre |
ref: À propos de l'ordre de calcul
| Structure de données | Montant du calcul | notation |
|---|---|---|
| list/tuple | len(seq) | |
| dictionary | len(dic) | |
| set | len(sets) |
Vous pouvez obtenir la longueur de n'importe quelle structure de données, quelle que soit sa taille, avec la même vitesse de traitement. Puisque la longueur n'est pas calculée, mais que la longueur elle-même est stockée, seul le coût de référence est requis, et il est $ O (1) $.
| Structure de données | Montant du calcul | notation |
|---|---|---|
| list/tuple | seq[i] | |
| seq[i:j] | ||
| dictionary | dic[key] | |
| set | sets[i] |
Les valeurs peuvent être référencées à la même vitesse pour toute structure de données, quelle que soit leur taille. Cependant, la tranche dépend de la longueur de la plage référencée.
| Structure de données | Montant du calcul | notation |
|---|---|---|
| list/tuple | for item in seq | |
| dictionary | for key in dic.keys() | |
| for item in dic.values() | ||
| for key, item in dic.items() | ||
| set | for item in sets |
Toute structure de données peut être itérée à peu près à la même vitesse de traitement, quelle que soit sa taille.
En termes de quantité de calcul uniquement, itérer l'index et se référer à la valeur dans la boucle est le même que le traitement décrit dans le tableau, mais en réalité il y a une différence de vitesse considérable, donc il est mis en italique par la méthode dans le tableau. Je pense que c'est bien.
def iter_index(seq:List[int], index:List[int]):
"""Itulate index et s'y référer en boucle"""
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]):
"""Itération directe du type de collection"""
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 fois plus vite
| Structure de données | Montant du calcul | notation |
|---|---|---|
| list/tuple | item in seq | |
| dictionary | key in dic.keys() | |
| item in dic.values() | ||
| (key, item) in dic.items() | ||
| set | item in sets |
Comme vous pouvez le voir intuitivement, liste / tuple est $ O (n) $. De plus, dictionary.values () est $ O (n) $. Je pense qu'il vaut la peine de se rappeler que le reste est $ O (1) $. Cela est dû au fait que la clé de type de dictionnaire et le type d'ensemble sont implémentés dans la table de hachage. Veuillez vous référer à l'article suivant pour plus de détails. ref: La raison pour laquelle il est devenu explosif simplement en passant de "dans la liste" à "dans le jeu" en Python
Il est plus rapide d'utiliser le type set pour l'opérateur in, mais en réalité, le type liste est utilisé plus fréquemment, donc je pense qu'il existe de nombreux cas où le type liste est converti en type set puis passé à l'opérateur in. .. Compte tenu du coût de la conversion, une certaine prudence s'impose. (Ci-après, nous examinerons uniquement la liste, mais le même argument sera fait avec tuple au lieu de liste.) Quand j'ai réellement mesuré «dans la liste», «dans l'ensemble» et «la conversion de la liste à l'ensemble et dans l'ensemble», les résultats suivants ont été obtenus.
# 「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)
#"Conversion de la liste à l'ensemble& in set」
%timeit 50000 in set(lists)
# >>> 2.94 ms ± 61.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Lors de la mesure du traitement à la vapeur avec différentes tailles,
| size | in set /en rapport de liste | in set(list) /en rapport de liste |
|---|---|---|
| 10 | 3 | 4 |
| 100 | 19 | 3 |
| 1000 | 112 | 3 |
| 10000 | 1118 | 3 |
| 100000 | 11350 | 5 |
En d'autres termes
Par conséquent, dans les cas suivants, l'utilisation de "in set" peut ** plutôt ralentir **.
--Liste pour définir la conversion requise --Et le nombre de fois à utiliser "dans l'ensemble" dans l'ensemble converti est inférieur à environ 5 fois
| Structure de données | Montant du calcul | notation |
|---|---|---|
| list | seq[i] = item | |
| seq[i:j] = lists | ||
| dictionary | dic[key] = item |
L'affectation fait référence à une opération qui modifie la valeur et ne modifie pas la longueur. La valeur de set ne peut pas être modifiée et doit être supprimée et ajoutée.
| Structure de données | Montant du calcul | notation | Remarques |
|---|---|---|---|
| list | seq.append(item) | Ajouter de la valeur au dos | |
| seq.insert(item, i) | Ajouter de la valeur à i th | ||
| seq.extend(list) | Combiner les listes derrière | ||
| dictionary | dic[key] = item | Ajouter un élément au dictionnaire | |
| dic.update(dic2) | Combiner des dictionnaires | ||
| set | sets.add(item) | Ajouter un élément à définir |
La quantité de calcul pour la liste dépend de l'endroit où vous ajoutez la valeur. Je pense que l'algorithme devrait inclure la valeur à la fin autant que possible. De plus, tous les ajouts ci-dessus sont destructifs (il n'en reste plus avant qu'ils ne soient ajoutés), vous pouvez donc avoir un effet négatif inattendu si vous ne faites pas attention à la portée de la variable.
Lorsque vous décidez de la valeur à ajouter après l'avoir filtrée avec une expression conditionnelle, il existe deux options comme suit.
Intuitivement, il semble qu'il soit moins coûteux d'ajouter séquentiellement, mais en python, car c'est lent et il vaut mieux utiliser la notation d'inclusion autant que possible, donc c'est un problème subtil. Les résultats de l'essai sont présentés ci-dessous. D'après le résultat, il semble qu'il n'y ait pas beaucoup de différence de vitesse. J'aimerais utiliser celui qui me convient. Personnellement, je préfère cette dernière méthode car la notation d'inclusion a moins d'effets secondaires (car elle nécessite moins d'attribution / définition de valeurs).
Si l'itération de la valeur à ajouter est longue, il semble plus rapide de créer une liste une fois dans la notation d'inclusion puis de l'étendre. Remarque: 1) Si vous faites un ajout destructeur, la taille changera et la mesure sera inexacte, alors copiez la liste et envoyez-la à la fonction. Note.2) append est connu pour être lent, alors assignez-le à une variable puis utilisez-le dans une boucle (Référence: Speed of Python list inclusion notation 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)
J'ai aussi essayé le dictionnaire. Le dictionnaire semble être plus rapide pour l'affectation séquentielle. Cependant, comme la fluctuation est importante, il semble qu'il n'y ait pas beaucoup de différence.
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)
| Structure de données | Montant du calcul | notation | Remarques |
|---|---|---|---|
| list | seq.pop() | Supprimer la valeur derrière | |
| seq.delete(i) | Supprimer la i-ième valeur | ||
| dictionary | dic.pop(key) | Supprimer en spécifiant la clé | |
| set | sets.discard(item) | Supprimer en spécifiant une valeur |
La liste doit être limitée au dos autant que possible lors de la suppression de valeurs. Le problème est ce qui se passe lorsqu'il y a plusieurs valeurs à supprimer. Intuitivement, il semble qu'il sera plus rapide de recréer à mesure que le nombre de valeurs à supprimer augmente. Nous examinerons les deux points suivants à cet égard. J'écrirai d'abord le résultat.
--pop vs slice: ** slice ** semble mieux --delete vs recréer: ** recréer ** semble mieux
pop vs slice Pop une liste de taille n k fois pour $ O (k) $ et tranche pour $ O (n-k) $. Cependant, si n> k, il ne peut pas être pop, et si n <k, il ne peut pas être découpé, j'ai donc mesuré la vitesse avec le code suivant.
def pop(seq:List[int], num:int):
for i in range(num):
seq.pop()
def slices(seq:List[int], num:int):
seq[:-num]
Vous trouverez ci-dessous un tableau qui mesure le rapport de vitesse d'exécution de pop et slice en modifiant la longueur de la liste et le nombre de suppressions. *** C'est le cas où la tranche était plus rapide dans la partie oblique ***. Fondamentalement, la tranche semble être meilleure.
| pop /rapport de tranche | Nombre de suppressions: 1 | 10 | 100 | 1000 |
|---|---|---|---|---|
| list size: 10 | 1.2 | 3.0 | ||
| 100 | 1.0 | 1.6 | 10.9 | |
| 1000 | 0.6 | 0.7 | 2.1 | 32.5 |
| 10000 | 0.6 | 0.5 | 0.5 | 1.7 |
Si vous supprimez la liste de taille n k fois, ce sera $ O (kn) $, et si vous la recréez, ce sera $ O (n) $. Évidemment, il semble plus rapide de le recréer, mais j'ai mesuré la vitesse avec le code suivant.
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]
Vous trouverez ci-dessous un tableau qui mesure le taux de vitesse d'exécution de la suppression et de la recréation en modifiant la longueur de la liste et le nombre de suppressions. *** C'est le cas où la reconstruction a été plus rapide pour la partie oblique ***. Fondamentalement, recréer semble être mieux.
| delete /recréer le ratio | Nombre de suppressions: 1 | 10 | 100 | 1000 |
|---|---|---|---|---|
| list size: 10 | 0.7 | 1.5 | ||
| 100 | 0.3 | 1.3 | 3.5 | |
| 1000 | 0.2 | 1.2 | 12.8 | 6.0 |
| 10000 | 0.3 | 1.8 | 114.7 | 117.4 |
La quantité de calcul du type de collection est résumée par utilisation. on dit que python est un langage lent, mais j'espère qu'il vous aidera à obtenir le temps de traitement que vous pouvez tolérer!
Demain, c'est typecprint!
refs
Recommended Posts