Ottieni un elenco di tutti gli indici di elementi ripetuti in un array numpy

Question

Sto cercando di ottenere l'indice di tutti gli elementi ripetuti in un array numpy, ma la soluzione che ho trovato per il momento è DAVVERO inefficiente per un grande (> 20000 elementi) array di input (ci vogliono più o meno 9 secondi). L'idea è semplice:

1. records_array è una matrice NumPy di ​​timestamp (TimeDate) da cui vogliamo estrarre gli indici di timestamp ripetute

2. time_array è un array NumPy contenente tutti i timestamp che sono ripetuto in records_array

3. records è un QuerySet di django (che può essere facilmente convertito in un elenco) contenente alcuni oggetti Record. Vogliamo creare un elenco di coppie formate da tutte le possibili combinazioni di attributi tagId di Record corrispondenti ai timestamp ripetuti trovati da records_array.

Ecco il lavoro (ma inefficiente) codice che ho per il momento:

tag_couples = []; 
for t in time_array: 
    users_inter = np.nonzero(records_array == t)[0] # Get all repeated timestamps in records_array for time t 
    l = [str(records[i].tagId) for i in users_inter] # Create a temporary list containing all tagIds recorded at time t 
    if l.count(l[0]) != len(l): #remove tuples formed by the first tag repeated 
     tag_couples +=[x for x in itertools.combinations(list(set(l)),2)] # Remove duplicates with list(set(l)) and append all possible couple combinations to tag_couples 

Sono abbastanza sicuro che questo può essere ottimizzato utilizzando Numpy, ma non riesco a trovare un modo per confrontare records_array con ogni elemento di time_array senza utilizzare un ciclo for (questo non può essere confrontato utilizzando solo ==, poiché sono entrambi gli array).

Answer 1

Soluzione basata come al solito con numpy sulla magia di unique(), senza anse né list comprehension:

records_array = array([1, 2, 3, 1, 1, 3, 4, 3, 2]) 
idx_sort = argsort(records_array) 
sorted_records_array = records_array[idx_sort] 
vals, idx_start, count = unique(sorted_records_array, return_counts=True, 
           return_index=True) 

# sets of indices 
res = split(idx_sort, idx_start[1:]) 
#filter them with respect to their size, keeping only items occurring more than once 

vals = vals[count > 1] 
res = filter(lambda x: x.size > 1, res) 

EDIT: il seguente è stata la mia risposta precedente, che ha richiesto un più memoria po ', utilizzando numpy radiodiffusione e chiamando unique due volte:

records_array = array([1, 2, 3, 1, 1, 3, 4, 3, 2]) 
vals, inverse, count = unique(records_array, return_inverse=True, 
           return_counts=True) 

idx_vals_repeated = where(count > 1)[0] 
vals_repeated = vals[idx_vals_repeated] 

rows, cols = where(inverse == idx_vals_repeated[:, newaxis]) 
_, inverse_rows = unique(rows, return_index=True) 
res = split(cols, inverse_rows[1:]) 

con come previsto res = [array([0, 3, 4]), array([1, 8]), array([2, 5, 7])]

Answer 2

Si potrebbe fare qualcosa sulla falsariga di:

1. add original index ref so [[1,0],[2,1],[3,2],[1,3],[1,4]... 
2. sort on [:,0] 
3. use np.where(ra[1:,0] != ra[:-1,0]) 
4. use the list of indexes from above to construct your final list of lists 

EDIT - OK così dopo la mia risposta rapida Sono stato via per un po 'e vedo che ho votato in giù che è abbastanza più equo numpy.argsort() è un modo molto migliore del mio suggerimento. Ho votato la risposta numpy.unique() in quanto questa è una caratteristica interessante. Tuttavia, se si utilizza timeit troverete che

idx_start = np.where(sorted_records_array[:-1] != sorted_records_array[1:])[0] + 1 
res = np.split(idx_sort, idx_start) 

è marginalmente più veloce di

vals, idx_start = np.unique(sorted_records_array, return_index=True) 
res = np.split(idx_sort, idx_start[1:]) 

Nuova interrogazione modifica seguito da @Nicolas

Non sono sicuro che si può. Sarebbe possibile ottenere due schiere di indici in corrispondenza con i punti di rottura, ma non si può rompere diverse 'linee' della matrice in pezzi di dimensioni diverse utilizzando np.split così

a = np.array([[4,27,42,12, 4 .. 240, 12], [3,65,23...] etc]) 
idx = np.argsort(a, axis=1) 
sorted_a = np.diagonal(a[:, idx[:]]).T 
idx_start = np.where(sorted_a[:,:-1] != sorted_a[:,1:]) 

# idx_start => (array([0,0,0,..1,1,..]), array([1,4,6,7..99,0,4,5])) 

ma che potrebbe essere abbastanza buono a seconda di cosa vuoi fare con le informazioni.

Answer 3

quindi ero in grado di sbarazzarsi del ciclo for, ma ero in grado di coppia verso il basso per utilizzare il ciclo for marginalmente utilizzando il tipo di dati set e il metodo list.count():

data = [1,2,3,1,4,5,2,2] 
indivs = set(data) 

multi_index = lambda lst, val: [i for i, x in enumerate(lst) if x == val] 

if data != list(indivs): 
    dupes = [multi_index(data, i) for i in indivs if data.count(i) > 1] 

Dove si esegue un ciclo sul set indivs, che contiene i valori (senza duplicati) e quindi passa in rassegna l'elenco completo se trovi un elemento con un duplicato. Sto cercando un'alternativa numpy se questo non è abbastanza veloce per te. Gli oggetti del generatore potrebbero anche velocizzarlo se necessario.

Modifica: la risposta di gg349 contiene la soluzione numpy su cui stavo lavorando!

Answer 4

È c anche fare questo:

a = [1,2,3,1,1,3,4,3,2] 
index_sets = [np.argwhere(i==a) for i in np.unique(a)] 

questo vi darà set di matrici con indici di elementi unici.

[array([[0],[3],[4]], dtype=int64), 
array([[1],[8]], dtype=int64), 
array([[2],[5],[7]], dtype=int64), 
array([[6]], dtype=int64)] 

Aggiunto: ulteriore variazione di di lista può anche scartare valori unici singoli e affrontare il problema della velocità in caso di molti unici singoli elementi che si verificano:

new_index_sets = [np.argwhere(i[0]== a) for i in np.array(np.unique(a, return_counts=True)).T if i[1]>=2] 

questo dà:

[array([[0],[3],[4]], dtype=int64), 
array([[1],[8]], dtype=int64), 
array([[2],[5],[7]], dtype=int64)]