J'effectue une analyse de données à l'aide d'un script python et j'ai appris du profilage que plus de 95% du temps de calcul est pris par la ligne qui effectue l'opération suivante np.sum (C [np.isin (A, b)]) , où A , C sont des tableaux 2D NumPy de dimension égale mxn , et b est un tableau 1D de longueur variable. Je me demande si ce n'est pas une fonction NumPy dédiée, y a-t-il un moyen d'accélérer un tel calcul?
Tailles typiques de A (int64) , C (float64) : 10M x 100
Taille typique de b (int64) : 1000
3 Réponses :
Je suppose que vous avez changé int64 en int8 chaque fois que nécessaire.
Vous pouvez utiliser la fonctionnalité Parallèle et It de Numba pour des calculs Numpy plus rapides et utiliser les cœurs.
@numba.jit(nopython=True, parallel=True)
def (A,B,c):
return np.sum(C[np.isin(A, b)])
Non, j'utilise toujours int64 pour la plage. C'est une bonne idée cependant, aura une empreinte mémoire moindre. J'ai vérifié la documentation pour Numba et il s'avère que np.isin () n'est pas une fonction universelle prise en charge par Numba en mode nopython .
Comme vos libellés proviennent d'une petite plage d'entiers, vous devriez obtenir une accélération considérable en utilisant Sur ma plate-forme, le numba soln ( Le code du module pythran: [subsum.py] La compilation est aussi simple que Exemple d'exécution: np.bincount ( pp ) ci-dessous. Vous pouvez également accélérer la recherche en créant un masque ( p2 ). Ceci --- tout comme votre code d'origine --- permet de remplacer np.sum par math.fsum qui garantit un résultat exact dans la précision de la machine ( p3 ). Alternativement, nous pouvons le pythraniser pour une autre accélération de 40% ( p4 ). mx ) est d'environ aussi vite que pp mais peut-être que je ne le fais pas correctement. 41330.15849965791 41330.15849965748 41330.15849965747 41330.158499657475 41330.15849965791 41330.158499657446
OP 1963.3807722493657
pp 53.23419079941232
p2 21.8758742994396
p3 26.829131800332107
p4 12.988955597393215
mx 52.37018179905135
import numpy as np
#pythran export pflat(int[:], float[:], int[:], int)
def pflat(A, C, b, MAXIND):
grid = np.zeros(MAXIND, bool)
grid[b] = True
return C[grid[A]].sum()
pythran subsum.py import numpy as np
import math
from subsum import pflat
MAXIND = 120_000
def OP():
return sum(C[np.isin(A, b)])
def pp():
return np.bincount(A.reshape(-1), C.reshape(-1), MAXIND)[np.unique(b)].sum()
def p2():
grid = np.zeros(MAXIND, bool)
grid[b] = True
return C[grid[A]].sum()
def p3():
grid = np.zeros(MAXIND, bool)
grid[b] = True
return math.fsum(C[grid[A]])
def p4():
return pflat(A.ravel(), C.ravel(), b, MAXIND)
import numba as nb
@nb.njit(parallel=True,fastmath=True)
def nb_ss(A,C,b):
s=set(b)
sum=0.
for i in nb.prange(A.shape[0]):
for j in range(A.shape[1]):
if A[i,j] in s:
sum+=C[i,j]
return sum
def mx():
return nb_ss(A,C,b)
sh = 100_000, 100
A = np.random.randint(0, MAXIND, sh)
C = np.random.random(sh)
b = np.random.randint(0, MAXIND, 1000)
print(OP(), pp(), p2(), p3(), p4(), mx())
from timeit import timeit
print("OP", timeit(OP, number=4)*250)
print("pp", timeit(pp, number=10)*100)
print("p2", timeit(p2, number=10)*100)
print("p3", timeit(p3, number=10)*100)
print("p4", timeit(p4, number=10)*100)
print("mx", timeit(mx, number=10)*100)
Merci pour la solution Paul. Le calcul à l'aide de np.bincount est presque 60 fois plus rapide sur np.isin et np.in1d après avoir été réduit à une dimension. Bien que les deux calculs doivent aboutir à une valeur identique, je vois une légère différence dans le résultat final. OP = 1273046188243834,8 et pp = 1273046188243834,5. Je n'ai pas vu de différence entre les deux implémentations qui pourraient causer une telle différence. Une idée?
@Viswanath Ouais, c'est probablement l'ordre de sommation. Votre implémentation fait la somme de l'ensemble des hits en une seule fois, tandis que la mienne additionne d'abord chaque étiquette, puis additionne les sous-sommes. Mais la différence est minime, dans votre exemple, elle ne peut être résolue qu'avec la précision de la machine (essayez np.nextafter (OP, 0) et vous obtiendrez pp ).
Wow, tu as raison. Ce n'est qu'une différence de valeur à virgule flottante unique. Merci beaucoup @Paul. D'un autre côté, si vous avez eu l'occasion de regarder les autres solutions de cet article, avez-vous des commentaires sur l'implémentation de Numba?
@Viswanath Non, moi numba noob. Mais j'ai ajouté une autre solution ( p2 ) qui est encore 2,5 fois plus rapide sur l'exemple et toujours seulement trois lignes. Et en prime, si les petites différences numériques vous dérangent, il peut être combiné avec math.fsum pour un résultat exact garanti ( p3 ) à un coût de calcul modeste.
@Viswanath Pas encore fait ;-) Si ce n'est toujours pas assez rapide: Vous pouvez utiliser pythran sur le code p2 pour une autre accélération ( p4 ).
Je ne sais pas pourquoi np.isin est si lent, mais vous pouvez implémenter votre fonction beaucoup plus rapidement.
La solution Numba suivante utilise un ensemble pour une recherche rapide de valeurs et est parallélisée. L'empreinte mémoire est également plus petite que dans l'implémentation Numpy.
Code
MAXIND = 120_000 sh = 100_000, 100 A = np.random.randint(0, MAXIND, sh) C = np.random.random(sh) b = np.random.randint(0, MAXIND, 1000) MAXIND = 120_000 %timeit res_1=np.sum(C[np.isin(A, b)]) 1.5 s ± 10.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) %timeit res_2=pp(A,C,b) 62.5 ms ± 624 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) %timeit res_3=nb_pp(A,C,b) 17.1 ms ± 141 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) MAXIND = 10_000_000 %timeit res_1=np.sum(C[np.isin(A, b)]) 2.06 s ± 27.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) %timeit res_2=pp(A,C,b) 206 ms ± 3.67 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) %timeit res_3=nb_pp(A,C,b) 17.6 ms ± 332 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) MAXIND = 100 %timeit res_1=np.sum(C[np.isin(A, b)]) 1.01 s ± 20.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) %timeit res_2=pp(A,C,b) 46.8 ms ± 538 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) %timeit res_3=nb_pp(A,C,b) 3.88 ms ± 84.8 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
Timings
L'implémentation pp et le premier exemple de données sont issus de la réponse de Paul Panzers ci-dessus.
import numpy as np
import numba as nb
@nb.njit(parallel=True,fastmath=True)
def nb_pp(A,C,b):
s=set(b)
sum=0.
for i in nb.prange(A.shape[0]):
for j in range(A.shape[1]):
if A[i,j] in s:
sum+=C[i,j]
return sum
Merci pour la solution intéressante. D'une manière ou d'une autre, je n'ai pas pu faire fonctionner numba avec mon code. J'obtiens cette erreur: numba.errors.TypingError: Échec du pipeline en mode nopython (étape: nopython frontend)
@Viswanath Fonctionne-t-il avec les sampledata? C'est une erreur typique si les entrées sont de types non pris en charge (par exemple, listes avec dtype mixte). Sont-ils tous des tableaux vraiment numpy ou quelque chose de différent?
@ max9111 Je ne pense pas que MAXIND soit le bon paramètre pour varier au-delà des valeurs 12'000 et 120'000 données par OP. Il devrait avoir la taille de b et dans une moindre mesure sh , vous ne pensez pas?
@ max9111 J'ai ajouté votre soln à mes horaires mais ce n'est pas aussi rapide que prévu sur ma machine. Quelque chose d'évident que je pourrais faire mal?
@Paul Panzer Vous mesurez un mélange de compilation et d'exécution. Lors d'un deuxième appel de print ("mx", timeit (mx, number = 10) * 100) vous devriez obtenir le runtime.
@ max9111 mais j'appelle mx une fois avant (imprimer la déclaration ci-dessus timeit import), ce n'est pas suffisant? Quoi qu'il en soit, si j'appelle timeit une seconde fois, cela ne va pas plus vite. Doit-on configurer numba d'une manière ou d'une autre? (J'exécute ceci sur une nouvelle installation de pip.)
@Paul Panzer Non pas pour cet exemple. Pour les fonctions transcendantales, Intel SVML peut fournir une certaine accélération. numba.pydata.org/numba-doc/dev/user/ performance-tips.html Je mesure 98ms pour un seul thread et 17ms pour la version multithread (facteur 5,7 sur un processeur 6C / 6T). Peut-être avez-vous moins de cœurs disponibles?
@ max9111 probablement, quand je mets parallel = False j'obtiens 150ms qui est juste en dessous de 3 fois la valeur parallel = True . Eh bien, merci pour le pointeur et les explications.
Quelle est la taille d'un
btypique et à quoi ressemblent ses éléments?Merci pour le commentaire Paul. J'ai maintenant ajouté les informations dans le message.
Les valeurs de
Aetbproviennent-elles d'une plage limitée ou partout?Non,
Aetbsont limités dans la plage. À l'heure actuelle, ils vont de 0 à 11 999. Cependant, ils peuvent augmenter de 10x à 119 999 lorsque j'améliore le système à l'avenir.