Algoritmo veloce per trovare indici in cui più array hanno lo stesso valore

Question

Sto cercando modi per accelerare (o sostituire) il mio algoritmo per il raggruppamento dei dati.

Ho una lista di array numpy. Voglio generare un nuovo array numpy, in modo tale che ogni elemento di questo array sia lo stesso per ogni indice in cui anche gli array originali sono uguali. (E diverso dove questo non è il caso.)

Sembra tipo di scomodo, in modo da avere un esempio:

# Test values: 
values = [ 
    np.array([10, 11, 10, 11, 10, 11, 10]), 
    np.array([21, 21, 22, 22, 21, 22, 23]), 
    ] 

# Expected outcome: np.array([0, 1, 2, 3, 0, 3, 4]) 
#        *   * 

nota che gli elementi sono contrassegnati (indici 0 e 4) del risultato atteso avere la stesso valore (0) perché anche i due array originali erano uguali (ovvero 10 e 21). Simile per gli elementi con indici 3 e 5 (3).

L'algoritmo deve gestire un numero arbitrario di matrici di input (uguali alle dimensioni) e anche restituire, per ciascun numero risultante, i valori delle matrici originali a cui corrispondono. (Così, per questo esempio, "3" si riferisce a (11, 22).)

Ecco il mio algoritmo attuale:

import numpy as np 

def groupify(values): 
    group = np.zeros((len(values[0]),), dtype=np.int64) - 1 # Magic number: -1 means ungrouped. 
    group_meanings = {} 
    next_hash = 0 
    matching = np.ones((len(values[0]),), dtype=bool) 
    while any(group == -1): 
     this_combo = {} 

     matching[:] = (group == -1) 
     first_ungrouped_idx = np.where(matching)[0][0] 

     for curr_id, value_array in enumerate(values): 
      needed_value = value_array[first_ungrouped_idx] 
      matching[matching] = value_array[matching] == needed_value 
      this_combo[curr_id] = needed_value 
     # Assign all of the found elements to a new group 
     group[matching] = next_hash 
     group_meanings[next_hash] = this_combo 
     next_hash += 1 
    return group, group_meanings 

Si noti che l'espressione value_array[matching] == needed_value viene valutato molte volte per ogni singolo indice, che è dove la lentezza viene da.

Non sono sicuro che il mio algoritmo possa essere velocizzato molto di più, ma non sono nemmeno sicuro se sia l'algoritmo ottimale per iniziare. C'è un modo migliore per farlo?

Answer 1

Incrinato finalmente per una soluzione vettoriale! È stato un problema interessante Il problema era che dovevamo taggare ogni coppia di valori presi dai corrispondenti elementi dell'array della lista. Quindi, dovremmo etichettare ciascuna di queste coppie in base alla loro unicità tra le coppie othet. Quindi, possiamo usare np.unique abusando di tutti gli argomenti opzionali e infine fare qualche lavoro aggiuntivo per mantenere l'ordine per l'output finale.Ecco l'implementazione sostanzialmente fatto in tre fasi -

# Stack as a 2D array with each pair from values as a column each. 
# Convert to linear index equivalent considering each column as indexing tuple 
arr = np.vstack(values) 
idx = np.ravel_multi_index(arr,arr.max(1)+1) 

# Do the heavy work with np.unique to give us : 
# 1. Starting indices of unique elems, 
# 2. Srray that has unique IDs for each element in idx, and 
# 3. Group ID counts 
_,unq_start_idx,unqID,count = np.unique(idx,return_index=True, \ 
             return_inverse=True,return_counts=True) 

# Best part happens here : Use mask to ignore the repeated elems and re-tag 
# each unqID using argsort() of masked elements from idx 
mask = ~np.in1d(unqID,np.where(count>1)[0]) 
mask[unq_start_idx] = 1 
out = idx[mask].argsort()[unqID] 

prova Runtime

Mettiamo a confronto l'approccio vectorized proposto contro il codice originale. Dal momento che il codice proposto ci ottiene solo gli ID di gruppo, quindi per un benchmark corretto, limitiamo le parti del codice originale che non sono usate per darci questo. Così, qui sono le definizioni di funzione -

def groupify(values): # Original code 
    group = np.zeros((len(values[0]),), dtype=np.int64) - 1 
    next_hash = 0 
    matching = np.ones((len(values[0]),), dtype=bool) 
    while any(group == -1): 

     matching[:] = (group == -1) 
     first_ungrouped_idx = np.where(matching)[0][0] 

     for curr_id, value_array in enumerate(values): 
      needed_value = value_array[first_ungrouped_idx] 
      matching[matching] = value_array[matching] == needed_value 
     # Assign all of the found elements to a new group 
     group[matching] = next_hash 
     next_hash += 1 
    return group 

def groupify_vectorized(values): # Proposed code 
    arr = np.vstack(values) 
    idx = np.ravel_multi_index(arr,arr.max(1)+1) 
    _,unq_start_idx,unqID,count = np.unique(idx,return_index=True, \ 
             return_inverse=True,return_counts=True)  
    mask = ~np.in1d(unqID,np.where(count>1)[0]) 
    mask[unq_start_idx] = 1 
    return idx[mask].argsort()[unqID] 

risultati runtime in un elenco con grandi array -

In [345]: # Input list with random elements 
    ...: values = [item for item in np.random.randint(10,40,(10,10000))] 

In [346]: np.allclose(groupify(values),groupify_vectorized(values)) 
Out[346]: True 

In [347]: %timeit groupify(values) 
1 loops, best of 3: 4.02 s per loop 

In [348]: %timeit groupify_vectorized(values) 
100 loops, best of 3: 3.74 ms per loop 

Answer 2

Se ho capito correttamente, si sta tentando di eseguire i valori di hash in base alle colonne. È meglio convertire le colonne in valori arbitrari da soli, quindi trovare gli hash da essi.

Quindi in realtà si desidera eseguire l'hash su list(np.array(values).T).

Questa funzionalità è già integrata in Pandas. Non hai bisogno di scriverlo. L'unico problema è che richiede un elenco di valori senza ulteriori elenchi al suo interno. In questo caso, puoi semplicemente convertire l'elenco interno in string map(str, list(np.array(values).T)) e ridurlo in fattori!

>>> import pandas as pd 
>>> pd.factorize(map(str, list(np.array(values).T))) 
(array([0, 1, 2, 3, 0, 3, 4]), 
array(['[10 21]', '[11 21]', '[10 22]', '[11 22]', '[10 23]'], dtype=object)) 

Ho convertito tua lista di array in un array, e poi in una stringa ...

Answer 3

Questo dovrebbe funzionare, e dovrebbe essere notevolmente più veloce, dal momento che stiamo utilizzando broadcasting e NumPy di ​​intrinsecamente veloce confronti booleani:

import numpy as np 

# Test values: 
values = [ 
    np.array([10, 11, 10, 11, 10, 11, 10]), 
    np.array([21, 21, 22, 22, 21, 22, 23]), 
    ] 
# Expected outcome: np.array([0, 1, 2, 3, 0, 3, 4]) 

# for every value in values, check where duplicate values occur 
same_mask = [val[:,np.newaxis] == val[np.newaxis,:] for val in values] 

# get the conjunction of all those tests 
conjunction = np.logical_and.reduce(same_mask) 

# ignore the diagonal 
conjunction[np.diag_indices_from(conjunction)] = False 

# initialize the labelled array with nans (used as flag) 
labelled = np.empty(values[0].shape) 
labelled.fill(np.nan) 

# keep track of labelled value 
val = 0 
for k, row in enumerate(conjunction): 
    if np.isnan(labelled[k]): # this element has not been labelled yet 
     labelled[k] = val  # so label it 
     labelled[row] = val # and label every element satisfying the test 
     val += 1 

print(labelled) 
# outputs [ 0. 1. 2. 3. 0. 3. 4.] 

si tratta di un fattore di 1,5 volte più veloce rispetto la versione quando si tratta con i due array, ma ho il sospetto l'aumento di velocità dovrebbe essere migliore per i più array.

Answer 4

Il numpy_indexed pacchetto (disclaimer: io sono il suo autore) contiene varianti generalizzate delle operazioni arrayset numpy , che può essere utilizzato per risolvere il problema in un elegante ed efficiente (vectorized) modalità:

import numpy_indexed as npi 
unique_values, labels = npi.unique(tuple(values), return_inverse=True) 

Quanto sopra funziona per tipo combin arbitrario ni, ma in alternativa, il seguito sarà ancora più efficace se i valori è un elenco di molti array dello stesso DTYPE:

unique_values, labels = npi.unique(np.asarray(values), axis=1, return_inverse=True)