Étant donné un tableau 1D X de longueur n dans Numpy avec k valeurs distinctes, je veux résumer pour chacune de ces valeurs distinctes c dans un autre tableau 1D Y de la même longueur, tous ces éléments Y [idx] où X [idx] == c de la manière la plus efficace.
Exemple:
X = [1, 3, 2, 1, 2] et Y = [0.1 , 0,2, 0,5, 2,0, 0,3] . La longueur n est de 5 et nous avons k = 3 valeurs distinctes dans X . Cela signifie que le résultat de notre opération est un vecteur des k = 3 éléments distincts [1, 3, 2] dans X et le sommes correspondantes à partir des éléments de Y qui est [2.1, 0.2, 0.8] . C'est également très bien si les éléments distincts sont ordonnés. Ainsi [1, 2, 3] avec [2.1, 0.8, 0.2] serait aussi une solution.
J'ai déjà recherché diverses fonctions dans Numpy et le plus proche de ce que je veux est np.unique (X, return_counts = True) mais il renvoie les décomptes et non les sommes en Y.
On pourrait, de Bien sûr, résolvez le tout avec une boucle désagréable comme:
(array([1, 2, 3]), array([2.1, 0.8, 0.2]))
menant au résultat ordonné:
import numpy as np
X = np.array([1, 3, 2, 1, 2])
Y = np.array([0.1, 0.2, 0.5, 2.0, 0.3])
def unique_sums(x, y):
distinct_x = np.unique(x)
y_sums = np.empty(distinct_x.shape)
for idx, val in enumerate(distinct_x):
y_sums[idx] = np.sum(y[x == val])
return distinct_x, y_sums
unique_sums(X, Y)
Y a-t-il une opération vectorisée comme celle-ci dans Numpy ou dans toute autre bibliothèque Python commune? Sinon, quelle serait l'implémentation la plus efficace en Cython?
4 Réponses :
Je pense que vous voudriez utiliser une table de hachage. Le dict de Python sera suffisamment efficace pour les petits ensembles de données. Vous devrez certainement lancer votre propre algorithme pour cela.
def unique_sums(x, y):
xd = {}
for i, number in enumerate(y):
xd[x[i]] = xd.get(x[i], 0) + number
return xd.keys(), xd.values()
Je pense que votre solution est O (n ^ 2) à cause de np.sum (y [x == val ]) mais le mien ci-dessus est O (n).
Merci pour votre suggestion, j'aurais dû mentionner mon cas d'utilisation. Il ferait partie d'un Bayes naïf catégorique pondéré par des poids d'échantillons. Ainsi, je traite des tableaux assez volumineux comme ~ 10k à ~ 100k et plus.
Ce n'est pas trop mal, je pense qu'un dict devrait bien fonctionner pour vous. Vous n'allez pas être O (len (Y)) au moins, et si dict n'est pas assez rapide pour vous, vous devriez pouvoir implémenter cet algorithme avec une table de hachage personnalisée en C.
Alors que théoriquement, un dict est O (1), je pense qu'il y a beaucoup de surcharge due au hachage, à la mémoire non contiguë, etc. Une boucle en Cython devrait faire passer X et Y une seule fois chacun, je suppose. Je me demandais simplement si Cython est la seule solution ou peut-être qu'il existe une application intelligente de np.where ou np.choose ou une fonction dont je ne suis pas au courant.
Vous avez demandé la «mise en œuvre la plus efficace». Vous n'avez pas spécifié en termes de temps d'exécution ou de mémoire, j'ai donc supposé le temps d'exécution. Le plus efficace est O (n), et c'est une solution à cela. Si vous ne souhaitez pas utiliser le hachage, vous devez modifier votre question pour stipuler «l'implémentation la plus efficace sans hachage».
@fwilhelm, étant donné que vous aurez 10k à 100k éléments, il vaut probablement la peine de passer du temps à tester les performances avec des tableaux de cette taille. Pour les petits tableaux, l'utilisation de np.unique peut gagner, mais à mesure que vous augmentez la taille des tableaux, la méthode avec une complexité temporelle plus faible finira par gagner. Les tests vous permettront de savoir si vous avez atteint ce point.
Je n'ai jamais dit que par plus efficace, j'entends avoir la moindre complexité d'exécution en notation O. C'est quelque chose que vous avez supposé, même si j'aurais dû préciser plus clairement que je voulais une solution basée sur un tableau Numpy si possible. La fonction np.unique utilise sûrement une sorte de hachage en interne, mais elle est plus efficace car elle se produit en C sans aucune surcharge Python.
@WarrenWeckesser, j'ai fait un court test d'exécution avec n = 1000000 et votre approche était encore 3 fois plus rapide que l'approche de @ tom-lubenow.
Voilà:
In [21]: u, inv = np.unique(X, return_inverse=True) In [22]: sums = np.zeros(len(u), dtype=Y.dtype) In [23]: np.add.at(sums, inv, Y) In [24]: sums Out[24]: array([2.1, 0.8, 0.2])
Ceci remplace votre boucle for par la méthode astucieuse numpy.add.at . p>
Notez que np.unique trie X , donc cette méthode est O (n * log (n)). Ce n'est pas la meilleure complexité temporelle possible pour ce problème.
Je suis vraiment impressionné! Exactement ce que je cherchais. Je n'étais pas au courant de ces fonctions ufunc.at dans Numpy.
Nous pouvons utiliser ici une scipy.sparse.csr_matrix pour une solution plus efficace
Configuration
X = np.random.randint(0, 100, 100_000)
Y = np.random.rand(100_000)
In [11]: %%timeit
...: sparse.csr_matrix(
...: (Y, X, np.arange(Y.shape[0]+1)),
...: (Y.shape[0], X.max()+1)
...: ).sum(0).A1
...:
1.15 ms ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [13]: %%timeit
...: u, inv = np.unique(X, return_inverse=True)
...: sums = np.zeros(len(u), dtype=Y.dtype)
...: np.add.at(sums, inv, Y)
...:
16.5 ms ± 161 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [16]: %timeit unique_sums(X, Y)
16.6 ms ± 169 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
array([[1. , 2.1],
[2. , 0.8],
[3. , 0.2]])
u = np.unique(X) np.column_stack((u, res[u]))
Voici une liste de sommes de 0 -> k , où k est la valeur maximale de votre tableau X . Toute entrée où une clé n'existe pas dans X sera évidemment 0 . Pour obtenir un meilleur mappage, vous pouvez utiliser np.unique et une certaine indexation:
array([0. , 2.1, 0.8, 0.2])
from scipy import sparse
res = sparse.csr_matrix(
(Y, X, np.arange(Y.shape[0]+1)),
(Y.shape[0], X.max()+1)
).sum(0).A1
Merci, bonne idée. Est-ce que j'obtiens également la liste correspondante de valeurs distinctes dans votre solution?
Non, non. Si vous en avez besoin, vous devrez utiliser np.unique . Cependant, en fonction de mes horaires, l'utilisation de np.unique n'ajoute pas suffisamment de frais généraux pour rendre l'une des autres solutions plus rapide que celle-ci. Par exemple, avec n = 100_000 , cela ajoute environ 3 ms au temps total, ce qui se traduit toujours par 3 fois plus rapide que les autres solutions.
Ok, compris. Le seul inconvénient de votre solution est alors que je ne peux traiter que des entiers dans X, non? Si j'appliquais cela dans un contexte Scikit-Learn où la plupart des matrices X sont flottantes, cela pourrait être un problème.
C'est correct. Bien que cela gâcherait toutes les solutions ici. J'ai ajouté un exemple de lien entre les valeurs uniques et les résultats dans ma réponse btw
Merci, gentil. J'ai juste essayé la solution de @WarrenWeckesser avec des valeurs flottantes dans X et cela fonctionnait toujours. Pourquoi serait-il en panne?
Nous allons essayer de tirer parti de pandas.factorize pour obtenir efficacement des identifiants uniques basés sur des int, puis utiliser numpy.bincount pour obtenir une sommation basée sur les identifiants. Ainsi, la solution ressemblerait à ceci -
In [24]: X = np.array([ 1, 3, 2, 1, 2]).astype(float)
...: Y = np.array([0.1, 0.2, 0.5, 2.0, 0.3])
In [25]: unique_sums_factorize_bincount(X,Y)
Out[25]: (array([1., 3., 2.]), array([2.1, 0.2, 0.8]))
Exemple d'exécution -
import pandas as pd
def unique_sums_factorize_bincount(X, Y):
ids,unq = pd.factorize(X)
return unq, np.bincount(ids,Y)
Pouvez-vous publier quelque part comment les approches publiées sont justes sur vos ensembles de données de taille ~ 10k à ~ 100k? Je suppose que les performances, c'est-à-dire l'exécution, sont votre priorité, il serait donc bon de voir comment celles-ci s'empilent.