NumPy - arg-sorta veloce e stabile di grandi array per frequenza

Oct 07 2020

Ho un grande array NumPy 1D adi qualsiasi comparabile dtype, alcuni dei suoi elementi possono essere ripetuti.

Come trovo gli indici di ordinamento ixche eseguiranno l' ordinamento stabile (stabilità in un certo senso qui descritta ) in abase alle frequenze dei valori in ordine decrescente / crescente?

Voglio trovare il modo più semplice e veloce per farlo. Forse esiste una funzione numpy standard esistente per farlo.

C'è un'altra domanda correlata qui, ma chiedeva specificamente di rimuovere i duplicati degli array, cioè produrre solo valori ordinati univoci, ho bisogno di tutti i valori dell'array originale inclusi i duplicati.

Ho programmato la mia prima prova per eseguire l'attività, ma non è la più veloce (utilizza il ciclo di Python) e probabilmente non è la forma più breve / più semplice possibile. Questo ciclo Python può essere molto costoso se la ripetizione di elementi uguali non è elevata e l'array è enorme. Inoltre sarebbe bello avere una funzione breve per fare tutto questo se disponibile in NumPy (ad esempio immaginario np.argsort_by_freq()).

Provalo online!

import numpy as np
np.random.seed(1)
hi, n, desc = 7, 24, True
a = np.random.choice(np.arange(hi), (n,), p = (
    lambda p = np.random.random((hi,)): p / p.sum()
)())
us, cs = np.unique(a, return_counts = True)
af = np.zeros(n, dtype = np.int64)
for u, c in zip(us, cs):
    af[a == u] = c
if desc:
    ix = np.argsort(-af, kind = 'stable') # Descending sort
else:
    ix = np.argsort(af, kind = 'stable') # Ascending sort
print('rows: i_col(0) / original_a(1) / freqs(2) / sorted_a(3)')
print('    / sorted_freqs(4) / sorting_ix(5)')
print(np.stack((
    np.arange(n), a, af, a[ix], af[ix], ix,
), 0))

uscite:

rows: i_col(0) / original_a(1) / freqs(2) / sorted_a(3)
    / sorted_freqs(4) / sorting_ix(5)
[[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23]
 [ 1  1  1  1  3  0  5  0  3  1  1  0  0  4  6  1  3  5  5  0  0  0  5  0]
 [ 7  7  7  7  3  8  4  8  3  7  7  8  8  1  1  7  3  4  4  8  8  8  4  8]
 [ 0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  5  5  5  5  3  3  3  4  6]
 [ 8  8  8  8  8  8  8  8  7  7  7  7  7  7  7  4  4  4  4  3  3  3  1  1]
 [ 5  7 11 12 19 20 21 23  0  1  2  3  9 10 15  6 17 18 22  4  8 16 13 14]]

Risposte

1 Nick Oct 07 2020 at 06:49

Potrei perdere qualcosa, ma sembra che con a Counterpuoi quindi ordinare gli indici di ogni elemento in base al conteggio del valore di quell'elemento, usando il valore dell'elemento e quindi l'indice per rompere i legami. Per esempio:

from collections import Counter

a = [ 1,  1,  1,  1,  3,  0,  5,  0,  3,  1,  1,  0,  0,  4,  6,  1,  3,  5,  5,  0,  0,  0,  5,  0]
counts = Counter(a)

t = [(counts[v], v, i) for i, v in enumerate(a)]
t.sort()
print([v[2] for v in t])
t.sort(reverse=True)
print([v[2] for v in t])

Produzione:

[13, 14, 4, 8, 16, 6, 17, 18, 22, 0, 1, 2, 3, 9, 10, 15, 5, 7, 11, 12, 19, 20, 21, 23]
[23, 21, 20, 19, 12, 11, 7, 5, 15, 10, 9, 3, 2, 1, 0, 22, 18, 17, 6, 16, 8, 4, 14, 13]

Se vuoi mantenere l'ordine crescente degli indici con gruppi con conteggi uguali, puoi semplicemente usare una funzione lambda per l'ordinamento decrescente:

t.sort(key = lambda x:(-x[0],-x[1],x[2]))
print([v[2] for v in t])

Produzione:

[5, 7, 11, 12, 19, 20, 21, 23, 0, 1, 2, 3, 9, 10, 15, 6, 17, 18, 22, 4, 8, 16, 14, 13]

Se si desidera mantenere l'ordine degli elementi nell'ordine in cui sono apparsi originariamente nell'array se i loro conteggi sono gli stessi , piuttosto che ordinare in base ai valori, ordinare in base all'indice della loro prima occorrenza nell'array:

a = [ 1,  1,  1,  1,  3,  0,  5,  0,  3,  1,  1,  0,  0,  4,  6,  1,  3,  5,  5,  0,  0,  0,  5,  0]
counts = Counter(a)

idxs = {}
t = []
for i, v in enumerate(a):
    if not v in idxs:
        idxs[v] = i
    t.append((counts[v], idxs[v], i))

t.sort()
print([v[2] for v in t])
t.sort(key = lambda x:(-x[0],x[1],x[2]))
print([v[2] for v in t])

Produzione:

[13, 14, 4, 8, 16, 6, 17, 18, 22, 0, 1, 2, 3, 9, 10, 15, 5, 7, 11, 12, 19, 20, 21, 23]
[5, 7, 11, 12, 19, 20, 21, 23, 0, 1, 2, 3, 9, 10, 15, 6, 17, 18, 22, 4, 8, 16, 13, 14]

Per ordinare in base al conteggio e quindi alla posizione nell'array, non è necessario il valore o il primo indice:

from collections import Counter

a = [ 1,  1,  1,  1,  3,  0,  5,  0,  3,  1,  1,  0,  0,  4,  6,  1,  3,  5,  5,  0,  0,  0,  5,  0]
counts = Counter(a)

t = [(counts[v], i) for i, v in enumerate(a)]
t.sort()
print([v[1] for v in t])
t.sort(key = lambda x:(-x[0],x[1]))
print([v[1] for v in t])

Questo produce lo stesso output del codice precedente per i dati di esempio, per l'array di stringhe:

a = ['g',  'g',  'c',  'f',  'd',  'd',  'g',  'a',  'a',  'a',  'f',  'f',  'f',
     'g',  'f',  'c',  'f',  'a',  'e',  'b',  'g',  'd',  'c',  'b',  'f' ]

Questo produce l'output:

[18, 19, 23, 2, 4, 5, 15, 21, 22, 7, 8, 9, 17, 0, 1, 6, 13, 20, 3, 10, 11, 12, 14, 16, 24]
[3, 10, 11, 12, 14, 16, 24, 0, 1, 6, 13, 20, 7, 8, 9, 17, 2, 4, 5, 15, 21, 22, 19, 23, 18]

1 Arty Oct 07 2020 at 07:34

Mi sono appena immaginato una soluzione probabilmente molto veloce per qualsiasi dtype usando solo funzioni numpy senza loop Python, funziona nel O(N log N)tempo. Usata funzioni NumPy: np.unique, np.argsorte matrice indicizzazione.

Sebbene non sia stato chiesto nella domanda originale, ho implementato un flag aggiuntivo equal_order_by_valse è False, quindi gli elementi dell'array con le stesse frequenze vengono ordinati come intervallo stabile uguale, il che significa che potrebbe esserci un c d d c d coutput come nei dump degli output di seguito, perché questo è l'ordine in cui gli elementi vanno nella matrice originale per la stessa frequenza. Quando flag è True, tali elementi vengono inoltre ordinati in base al valore dell'array originale, risultando in c c c d d d. In altre parole, in caso di False ordiniamo stabilmente solo per chiave freq, e quando è True (freq, value)ordiniamo per ordine crescente e (-freq, value)per ordine decrescente.