Trova tutte le possibili distanze da due array

Dati due array ordinati A e B lunghezza N. Ogni elemento può contenere un numero naturale inferiore a M. Determina tutte le possibili distanze per tutti gli elementi di combinazione A e B. In questo caso, se A[i] - B[j] < 0, la distanza è M + (A[i] - B[j]).Trova tutte le possibili distanze da due array

Esempio:

A = {0,2,3} 
B = {1,2} 
M = 5 

Distances = {0,1,2,3,4}

Nota: Lo so O(N^2) soluzione, ma ho bisogno di una soluzione più veloce di O(N^2) e O(N x M).

Modifica: matrice A, B e Distances contengono elementi distinti.

fonte

2015-12-15 Karsten Ari Agathon

Le distanze potrebbero non contenere duplicati. –

Non penso che troverai migliore di 0 (MxN) ma mi aspetto che qualcuno pubblichi qualcosa, sarebbe interessante :) – Netwave

Considerando che l'output può essere "N * M", non penso che possiamo scrivere un algoritmo più veloce di O (N * M). –

È possibile ottenere una soluzione di complessità O (MlogM) nel modo seguente.

Preparare una Ax array di lunghezza M con Ax [i] = 1 se i appartiene ad A (e 0 altrimenti)
Preparare una serie Bx di lunghezza M con Bx [M-1-i] = 1 se appartiene a B (e 0 altrimenti)
Utilizza la fast Fourier Transform a convolvere questi 2 sequenze insieme
Controllare la matrice di output, valori diversi da zero corrispondono a possibili distanze

noti che il FFT è normalmente fatto con numeri in virgola mobile, quindi in ste p 4 probabilmente vuoi verificare se l'uscita è maggiore di 0,5 per evitare potenziali problemi di arrotondamento.

fonte

2015-12-15 09:59:06

Qual è la dimensione dei risultati nel passaggio 3? –

Grazie per la risposta, signor Peter. Accetterò questa risposta quando riuscirò a confermarlo. Al momento, non sono ancora perfettamente a conoscenza della FFT. Sarò molto felice se fornirai un riferimento sull'algoritmo FFT correlato. –

Questo è banale se usi Python con la libreria scipy perché c'è una funzione [fftconvolve] (http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.signal.fftconvolve.html) che fa il passaggio 3 per te in una riga :) –

Possibile fatto con N * N ottimizzato.

Se convertito A 0 e 1 campo dove 1 su posizioni che presenti in A (nella gamma [0..M]. Dopo convertire questo array in bitmasks, dimensione di un array viene diminuito in 64 volte.

Ciò consentirà risultati inserto di blocchi di dimensione 64. Complessità ancora verrà N*N ma il tempo di lavoro sarà notevolmente diminuita. Come accennato limitazione dall'autore 50000 a e B formati e M. operazioni attesi valore sarà N * N/64 ~ = 4 * 10^7. È passato in 1 secondo

fonte

2015-12-15 10:49:17

È possibile utilizzare bitve medici per realizzare questo. Le operazioni di bitvector su bitmap di grandi dimensioni sono lineari nella dimensione del bitvector, ma sono veloci, facili da implementare e potrebbero funzionare bene dato il limite di 50k.

Inizializza due bitvector di lunghezza M. Chiama questi vectA e vectAnswer. Imposta i bit di vectA che corrispondono agli elementi in A. Lascia vectAnswer con tutti gli zeri.

Definire un metodo per ruotare un bitvector di k elementi (ruotare verso il basso). Chiamerò questo ruotare (vect, k).

Quindi, per ogni elemento b di B, vectAnswer = vectAnswer | rotate (VECTA, b).

fonte

2015-12-15 11:06:48 Dave

Trova tutte le possibili distanze da due array

risposta

Problemi correlati