J'ai dû mettre en place un certain processus. Le processus est le suivant. "Pour chaque objet de la liste, supprimez-le de la liste s'il est inférieur au nouvel objet." Qu'est-ce qui est inférieur? Cependant, en supposant que l'objet est représenté par un taple, le nouvel objet est «n» et l'objet à l'origine dans la liste est «x».
[n[i] > x[i] for i in range(len(n))]
Supposons que le résultat de soit «[True, True, ..., True]» (tout est vrai).
Cependant, cela dépend du problème si chaque indice doit avoir une valeur plus grande ou une valeur plus petite (c'est-à-dire que le programme doit le traiter). Par exemple, si le 1er axe est maximisé et le 2ème axe est minimisé, les conditions pour les objets à supprimer sont les suivantes.
n[0] > x[0] and n[1] < x[1]
Dans ce qui suit, j'écrirai ce processus en Python pour le moment, puis j'aimerais l'améliorer étape par étape.
C'est pourquoi c'est un programme qui implémente le traitement expliqué. Qu'il soit maximisé ou minimisé sur chaque axe est passé dans l'argument maximiser (bien que le nom de la variable ne soit pas assez bon).
filters.py
def filter00(l, n, maximize):
nl = []
for x in l:
remove = True
for i in range(len(x)):
if maximize[i]:
if n[i] > x[i]:
pass
else:
remove = False
else:
if n[i] < x[i]:
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Vérifiez en supposant qu'il sera supprimé et s'il existe un axe pour lequel «x» est meilleur, annulez la suppression. Je pense qu'il est redondant que if is pass and else et que remove soit False, mais je pense que retourner la condition ou ajouter non réduira la lisibilité, donc je vais le laisser tel quel (je l'améliorerai quand même)
Le code suivant pour la fonction filter00,
for i in range(len(x)):
if maximize[i]:
if n[i] > x[i]:
pass
else:
remove = False
else:
if n[i] < x[i]:
pass
else:
remove = False
maximiser est passé comme argument et ne change pas dans la boucle. Je pense que c'est un processus supplémentaire pour créer une branche conditionnelle à chaque fois. Alors, réfléchissons à la question de savoir si nous pouvons extraire ʻif maxim [i] `.
La méthode consiste à transformer n [i]> x [i] et n [i] <x [i] en expressions lambda. Python a un module opérateur qui exécute la fonction correspondant à l'opérateur, réécrivons-le donc en l'utilisant.
filters.py
import operator
def filter01(l, n, maximize):
cond = []
for m in maximize:
cond.append(operator.gt if m else operator.lt)
nl = []
for x in l:
remove = True
for i in range(len(x)):
if cond[i](n[i],x[i]):
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Au fait, j'ai supprimé la branche conditionnelle qui ne change pas en fonction de la boucle, mais est-ce vraiment plus rapide? Mesurons correctement, pas le sentiment. Cette fois, j'ai réalisé le script de mesure suivant.
perf.py
import filters
import time
import random
import numpy as np
random.seed(123)
def perf(ll, n, m, f):
elapsed = []
for l in ll:
start = time.time()
f(l, n, m)
end = time.time()
elapsed.append(end - start)
print(f.__name__, np.average(elapsed))
LOOP = 100
SIZE = 1000
n = (70, 70)
m = (True, True)
ll = [[(random.randint(0, 99), random.randint(0, 99)) for _ in range(SIZE)] for _ in range(LOOP)]
perf(ll, n, m, filters.filter00)
perf(ll, n, m, filters.filter01)
Il y a un risque que Masakari vole si vous comparez uniquement avec la valeur moyenne, mais veuillez ne pas lancer Masakari car le résultat de l'enquête préliminaire est que la valeur moyenne est correcte (rires)
Eh bien, résultat de l'exécution
filter00 0.00383123636246 filter01 0.00437139987946
De manière inattendue, il avait 5 millisecondes de retard. Il est possible que le coût de la modification de la comparaison d'une opération à un appel de fonction ait dépassé le coût de suppression de la branche conditionnelle qui ne change pas avec la boucle.
Je voulais parler d'être heureux parce que le code était plus court et plus rapide, mais j'ai trébuché au début. En fait, cette amélioration a été trouvée par un examen de la vitesse après avoir raccourci le code, mais comme il est possible de garder le code lent, il est préférable d'utiliser la fonction zip lors du traitement de plusieurs listes dans une boucle. J'ai demandé, mais j'ai essayé de voir comment c'était.
filters.py
def filter02(l, n, maximize):
cond = []
for m in maximize:
cond.append(operator.gt if m else operator.lt)
nl = []
for x in l:
remove = True
for c, a, b in zip(cond, n, x):
if c(a, b):
pass
else:
remove = False
if not remove:
nl.append(x)
return nl
Résultat de la mesure. De plus, les valeurs de filter00 et filter01 sont exactement les mêmes que précédemment, mais les valeurs mesurées lors du résultat final du programme d'amélioration sont données en petites quantités. Pas mal.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483
vite. C'est plus rapide que le code initial.
La différence entre «filter01» et «filter02» est de savoir s'ils font référence à «cond», «n», «x» avec des indices ou reçoivent ce que la fonction zip renvoie. L'accès en indice est appelé la méthode __getitem__, il semble donc que le coût de l'appel de la fonction ait disparu. En disant cela, même la fonction zip doit appeler __getitem__, mais cela m'intéresse car elle est traitée au niveau C, mais je vais améliorer le code pour le moment.
Notation inclusive que tout le monde aime. C'est trop maladroit pour écrire une boucle for bâclée. Écrivons soigneusement en utilisant la notation d'inclusion.
filters.py
def filter03(l, n, maximize):
cond = [operator.gt if m else operator.lt for m in maximize]
return [x for x in l if not all([c(a, b) for c, a, b in zip(cond, n, x)])]
Soudain trop! Je vais avoir un tsukkomi, alors je vais l'expliquer correctement. Oh, mais avant ça. Tout d'abord, ce code est très court en termes de lignes, mais c'est vraiment lent. Donc, si vous voulez connaître le code rapide, passez à l'amélioration n ° 5.
Maintenant, parlons de filter03. Cette fonction utilise la notation à double inclusion. L'explication intérieure d'abord.
[c(a, b) for c, a, b in zip(cond, n, x)]
Cette partie est presque la même que la boucle interne écrite dans filter02. La plupart du temps, dans filter02, le branchement conditionnel a été effectué et la valeur a été définie dans une seule variable remove, mais dans la notation d'inclusion ci-dessus,
[True, True]
La différence est que la liste est renvoyée comme ceci. C'est là que se pose le problème ennuyeux. Pour décider de partir ou non, vous devez en faire un scalaire, pas une liste. Utilisez la fonction all pour cela. La fonction all est une fonction qui renvoie True si la liste (ou itérable) est entièrement True. En utilisant ceci, il est possible de réaliser le processus dans lequel le branchement conditionnel est effectué avec «filter02» et «remove» est mis à False dans le cas de else. (Si vous ne perdez sur aucun axe, au moins une des listes sera False et l'ensemble sera False)
C'est pourquoi je connaissais l'intérieur, donc cette fois c'est l'extérieur.
[x for x in l if not all([c(a, b) for c, a, b in zip(cond, n, x)])]
Comment cela fonctionne
x est utilisé pour évaluer la partie ʻif ...`Ainsi, la notation d'inclusion externe correspond au code qui traitait «filter02» pour ne pas ajouter en fonction de la valeur de «remove» (déterminée par la boucle interne).
Eh bien, c'est la vitesse d'exécution tant attendue.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542
lent. Cela a été beaucoup plus lent que jamais. En fait, la notation d'inclusion semble avoir une surcharge en raison de l'apparence de la fonction & all qui est exécutée fonctionnellement.
Eh bien, il n'y a déjà pas d'avantage de vitesse, mais il y a un avantage dans la quantité de description du code, donc je vais améliorer un peu plus le code d'amélioration 3. Ce qui était difficile à comprendre avec filter03, c'est la notation à double inclusion, donc j'utiliserai une fonction interne pour rendre cette partie un peu plus froide.
filters.py
def filter04(l, n, maximize):
cond = [operator.gt if m else operator.lt for m in maximize]
def dominated(x, n):
return all([c(a, b) for c, a, b in zip(cond, n, x)])
return [x for x in l if not dominated(x, n)]
En changeant la notation d'inclusion (et toutes les fonctions) écrites après «sinon» en une fonction interne appelée «dominée», il est devenu possible d'expliquer ce que vous faites en un mot, et la lisibilité s'est améliorée.
La vitesse d'exécution est la plus lente que vous pouvez imaginer.
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528
Maintenant, regardons cela en arrière.
Donc, le code est basé sur ceux-ci. De plus, «filter021» signifie qu'il a été modifié en fonction de «filter02».
filters.py
def filter021(l, n, maximize):
nl = []
for x in l:
remove = True
for a, b, m in zip(n, x, maximize):
remove = remove and (a > b if m else a < b)
if not remove:
nl.append(x)
return nl
Comme la boucle interne et l'opérateur ne peuvent pas être utilisés, je l'ai rendu compact en utilisant l'opérateur and et l'opérateur conditionnel.
Eh bien, le temps d'exécution
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528 filter021 0.00255712985992
Le plus rapide: v:
L'histoire n'est pas encore terminée. Ne pouvons-nous pas en quelque sorte le rendre plus rapide? L'idée est de changer le code selon qu'il est utilisé fréquemment ou non (général). En d'autres termes, même si vous dites "N variables, maximum et minimum peuvent être mélangés", vous pouvez écrire comme suit si vous dites "2 variables, les deux axes maximisent" dans la plupart des utilisations.
filters.py
def filter02X(l, n, maximize):
if len(n) == 2 and maximize == (True, True):
return [x for x in l if not (n[0] > x[0] and n[1] > x[1])]
else:
return filter021(l, n, maximize)
Résultat de la mesure
filter00 0.00383123636246 filter01 0.00437139987946 filter02 0.0029260468483 filter03 0.00512305736542 filter04 0.00578190803528 filter021 0.00255712985992 filter02X 0.000690214633942
C'est une vitesse extraordinaire: v :: v: Dans le cas de 2 variables et 3 variables dans l'implémentation du système de traitement du langage, cela signifie que c'est plus que cela.
Dans cet article, nous avons progressivement amélioré le programme solide. L'idée initiale était de faire du code qui ne ressemble pas à Python (code que les gens qui ont appris d'autres langages ont tendance à écrire lors de l'écriture de programmes en Python) devienne semblable à Python, ce qui le rend plus lisible et plus rapide, et le rend heureux. Je voulais, mais quand je l'ai mesuré, j'ai trouvé que ce n'était pas le cas, alors j'ai un peu changé l'histoire. En résumé, il y a les trois points suivants.
Cela fait 3 ans que l'article a été publié. À ce moment-là, la puissance de numpy était encore faible, et j'ai pensé: "L'amélioration de la vitesse que j'ai écrite dans cet article, maintenant je me demande si je peux utiliser numpy pour le rendre encore plus rapide", mais je n'y ai pas touché. D'un autre côté, quand j'ai maintenu le programme qui était la source de cet article pour la première fois depuis un moment, j'étais désespéré qu'il soit trop lent et utilisé numpy pour l'accélérer.
Il y a quelque chose dans filter021 que numpy ○ chi ne peut pas pardonner.
Oui, c'est une déclaration for.
C'est pourquoi je l'ai effacé.
filters.py
def filter05(l, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
npa = np.array(l)
check = np.empty(npa.shape, dtype=np.bool)
for i, c in enumerate(cond):
check[:, i] = c(n[i], npa[:, i])
#Les éléments qui perdent tous les axes à n (les expressions conditionnelles sont toutes vraies) sont supprimés, sinon pas supprimés
not_remove = (check.sum(axis=1) != len(n))
return [x for x, nr in zip(l, not_remove) if nr]
Je ne peux pas l'effacer! Il y a une raison pour que le code ci-dessus soit une excuse.
―― Comme il est différent pour chaque axe qu'il soit maximisé ou minimisé (avec ma puissance numpy), il ne peut pas être écrit avec une expression conditionnelle.
[^ 1]: Cela ne répond pas aux spécifications, mais j'ai essayé d'utiliser l'index booléen, mais cela n'a pas accéléré.
Mesurons quand même le temps.
filter00 0.0037975716590881348 filter01 0.004087417125701904 filter02 0.003038032054901123 filter03 0.004926862716674804 filter04 0.005476489067077637 filter021 0.002838168144226074 filter02X 0.0006895852088928222 filter05 0.002588319778442383
C'est une erreur. La raison pour laquelle cela ne va pas plus vite semble être la surcharge de la conversion de la liste en numpy. Si len (l) >> len (n), l'instruction for qui compare chaque axe peut être ignorée.
Comme mentionné ci-dessus, le programme de matériel d'origine ne peut pas supposer un tableau numpy comme entrée, il ne peut donc pas être rendu plus rapide, mais j'ai essayé de voir à quelle vitesse ce serait si l'entrée et la sortie pouvaient être un tableau numpy.
filters.py
def filter06(a, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
check = np.empty(a.shape, dtype=np.bool)
for i, c in enumerate(cond):
check[:, i] = c(n[i], a[:, i])
not_remove = (check.sum(axis=1) != len(n))
return a[not_remove]
Faites-en un tableau numpy avant de l'appliquer à la mesure.
perf.py
a = np.array(ll)
perf(a, n, m, filters.filter06)
résultat. Après tout, il est rapide s'il ne peut être complété qu'avec numpy.
filter00 0.0037975716590881348 filter01 0.004087417125701904 filter02 0.003038032054901123 filter03 0.004926862716674804 filter04 0.005476489067077637 filter021 0.002838168144226074 filter02X 0.0006895852088928222 filter05 0.002588319778442383 filter06 0.00030982017517089844
Ou plutôt, la version spécialisée (filter02X) est si rapide. Au fait, j'ai créé une version spécialisée de «filter05» et «filter06» et je l'ai mesurée, mais le résultat était presque le même (plutôt plus lent).
Je me suis demandé s'il y avait un moyen de tout faire en même temps en comparant chaque axe de filter06, mais je ne pouvais pas éliminer la comparaison par axe, mais j'ai trouvé un moyen de supprimer la somme après pour.
filers.py
def filter061(a, n, maximize):
cond = [np.greater if m else np.less for m in maximize]
check = np.ones(a.shape[0], dtype=np.bool)
for i, c in enumerate(cond):
check = check & c(n[i], a[:, i])
not_remove = ~check
return a[not_remove]
Il sera environ deux fois plus rapide lorsqu'il est mesuré. J'ai également appliqué la même amélioration à filter05, mais la surcharge de conversion était encore plus importante.
filter06 0.0003197813034057617 filter061 0.00017987966537475587
Si vous inversez l'opération de comparaison elle-même et supprimez le dernier «~», ce sera 10 à 20% plus rapide, mais la lisibilité diminuera.
filters.py
def filter062(a, n, maximize):
cond = [np.less if m else np.greater for m in maximize]
not_remove = np.zeros(a.shape[0], dtype=np.bool)
for i, c in enumerate(cond):
not_remove = not_remove | c(n[i], a[:, i])
return a[not_remove]