Manipuler efficacement les doublons dans une liste Python - python, algorithme, numpy, grouping, graphe-algorithme

Je cherche à représenter de manière compacte les doublons dans un tableau Python list / 1D numpy. Par exemple, supposons que nous ayons

 x = np.array([1, 0, 0, 3, 3, 0])

ce tableau a plusieurs éléments en double, qui peuvent être représentés avec un

 group_id = np.array([0, 1, 1, 2, 2, 1])

de sorte que tous les doublons d’un cluster donné soient trouvés avec x[group_id==<some_id>].

La liste des paires en double peut être efficacement calculée avec le tri,

s_idx = np.argsort(x)
diff_idx = np.nonzero(x[s_idx[:-1]] == x[s_idx[1:]])[0]

où la paire s_idx[diff_idx] <-> s_idx[diff_idx+1] correspondent aux index du tableau d'origine qui sont en double. (ici array([1, 2, 3]) <-> array([2, 5, 4])).

Cependant, je ne sais pas comment calculer efficacement cluster_id à partir de ces informations de liaison pour les grandes tailles de tableaux (N > 10⁶).

Modifier: comme suggéré par @Chris_Rands, cela peut en effet être fait avec itertools.groupby,

 import numpy as np
import itertools

def get_group_id(x):
group_id = np.zeros(x.shape, dtype="int")
for i, j in  itertools.groupby(x):
j_el = next(j)
group_id[x==j_el] = i
return group_id

cependant, la mise à l'échelle semble être O (n ^ 2), et cela ne serait pas adapté à mon cas d'utilisation (N > 10⁶),

  for N in [50000, 100000, 200000]:
%time _ = get_group_id(np.random.randint(0, N, size=N))

CPU times: total: 1.53 s
CPU times: total: 5.83 s
CPU times: total: 23.9 s

et je crois que l’utilisation des informations de liaison en double serait plus efficace que le calcul des paires en double pour N=200000 prend seulement 6,44 µs en comparaison.

Réponses:

1 pour la réponse № 1

Vous pourriez utiliser numpy.unique:

In [13]: x = np.array([1, 0, 0, 3, 3, 0])

In [14]: values, cluster_id = np.unique(x, return_inverse=True)

In [15]: values
Out[15]: array([0, 1, 3])

In [16]: cluster_id
Out[16]: array([1, 0, 0, 2, 2, 0])

(Les ID de cluster sont attribués dans l’ordre des valeurs uniques triées, et non dans l’ordre de la première apparition d’une valeur dans l’entrée.)

Emplacement des éléments du groupe 0:

In [22]: cid = 0

In [23]: values[cid]
Out[23]: 0

In [24]: (cluster_id == cid).nonzero()[0]
Out[24]: array([1, 2, 5])

---

1 pour la réponse № 2

Voici une approche utilisant np.unique garder l'ordre en fonction de la première apparition d'un numéro -

unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1)
out = first_idx.argsort().argsort()[ID]

Exemple de cycle -

In [173]: x
Out[173]: array([1, 0, 0, 3, 3, 0, 9, 0, 2, 6, 0, 0, 4, 8])

In [174]: unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1)

In [175]: first_idx.argsort().argsort()[ID]
Out[175]: array([0, 1, 1, 2, 2, 1, 3, 1, 4, 5, 1, 1, 6, 7])

---