Wydajna obsługa duplikatów na liście Pythona - python, algorytm, numpy, grouping, graph-algorithm

Szukam zwartej reprezentacji duplikatów w tablicy Python / 1D numpy. Na przykład powiedzmy, że mamy

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

ta tablica ma kilka zduplikowanych elementów, które mogą być reprezentowane przez

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

tak, że wszystkie duplikaty w danym klastrze zostaną znalezione za pomocą x[group_id==<some_id>].

Lista duplikatów par może być efektywnie obliczona za pomocą sortowania,

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

gdzie para s_idx[diff_idx] <-> s_idx[diff_idx+1] odpowiadają indeksom w oryginalnej tablicy, które są duplikatami. (tutaj array([1, 2, 3]) <-> array([2, 5, 4])).

Nie wiem jednak, jak skutecznie obliczyć cluster_id z tej informacji o powiązaniach dla dużych rozmiarów tablic (N > 10⁶).

Edytować: jak sugeruje @ Chris_Rands, rzeczywiście można to zrobić 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

jednak skalowanie wydaje się być O (n ^ 2), a to nie skaluje się do mojego przypadku użycia (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

i wierzę, że użycie duplikatów informacji o powiązaniach byłoby bardziej wydajne jako obliczanie duplikatów par N=200000 trwa tylko 6,44 µs w porównaniu.

Odpowiedzi:

1 dla odpowiedzi № 1

Możesz użyć 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])

(Identyfikatory klastra są przypisywane w kolejności posortowanych unikalnych wartości, a nie w kolejności pierwszego pojawienia się wartości na wejściu.)

Lokalizacje elementów w klastrze 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 dla odpowiedzi nr 2

Oto podejście z wykorzystaniem np.unique zachować porządek zgodnie z pierwszym pojawieniem się numeru -

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

Przykładowy przebieg -

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])

---