Aperçu

Lors de l'exécution d'une opération de consigne, la vitesse d'exécution peut être améliorée en réduisant le nombre d'éléments du résultat obtenu. Le résultat de l'opération étant renvoyé dans un nouvel objet set, la création de l'objet prend du temps si le nombre d'éléments est important.

Contexte

Dans ABC157 D Friend Suggestions, lorsque j'ai défini len (XYZ) pour calculer le nombre d'éléments dans un certain ensemble, il est devenu TLE. AC a été fait avec len (X) -len (X & (Y | Z)) `. J'ai essayé de vérifier pourquoi la vitesse est différente.

|X|Quand est grand

Sur la prémisse du problème|X|,|Y|,|Z| \leq 10^5Mais cette fois je l'ai rencontré|X| \gg |Y|,|Z|Mesurons la condition de.

from timeit import timeit

xyz = 'X=set(range(10**5)); Y=set(range(10)); Z=set(range(5,15))' 

timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.3884289239649661

timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 0.0001103340182453394

Bien que les résultats soient les mêmes, il existe une différence de temps d'exécution de 3520 fois.

Lorsque le contenu de X, Y, Z est le même

Ensuite, soit X, Y, Z tous le même élément de 10 $ ^ 5 $.

from timeit import timeit

xyz = 'X=set(range(10**5)); Y=set(range(10**5)); Z=set(range(10**5))'

timeit('len(X-Y-Z)', setup=xyz, number=100)
# 0.28364974400028586

timeit('len(X)-len(X&(Y|Z))', setup=xyz, number=100)
# 1.1718004010035656

La prochaine foislen(X)-len(X&(Y|Z))Était plus lent.X&(Y|Z)Est le même que l'ensemble d'origine, et on considère que le nombre d'éléments dans le résultat a augmenté. D'autre part, "len (X-Y-Z)" a été raccourci à environ 1/3, probablement parce qu'un ensemble vide a été obtenu au stade de "X-Y".

Ensemble de différences vs ensemble de produits

Simplifiez le problème et comparez uniquement la différence et les opérations du produit. L'autre côté du calcul est un ensemble vide, et les côtés gauche et droit sont échangés.

from timeit import timeit

xy = 'X=set(range(10**5)); Y=set()'

timeit('X-Y', setup=xy, number=100)
# 0.16930873499950394
timeit('Y-X', setup=xy, number=100)
# 1.7047044821083546e-05

timeit('X&Y', setup=xy, number=100)
# 1.0746996849775314e-05
timeit('Y&X', setup=xy, number=100)
# 1.502997474744916e-05

Même dans l'ensemble de différences, il est rapide lorsque le nombre d'éléments dans le résultat est petit. Apparemment, la différence de vitesse n'est pas le contenu du calcul.

Génération d'ensemble

Voir documentation Python set.difference

Renvoie un nouvel ensemble avec des éléments inclus dans l'ensemble et non inclus dans tous les autres.

une. Par conséquent, mesurons le temps de génération d'un ensemble avec un grand nombre d'éléments.

from timeit import timeit

timeit('set(X)', setup='X=set(range(10**5))', number=100)
# 0.16229172004386783

Après tout, lorsque le nombre d'éléments dans le résultat était important, la génération de l'ensemble renvoyé ne prenait que longtemps.