Cerca vettori simili, basati sulla differenza elementare

Puoi riorganizzare il tuo:

(1-2) + (4-3) + (7-5) + (2-9) 

... diventare:

(1 + 4 + 7 + 2) - (2 + 3 + 5 + 9)

... e (errori di arrotondamento modulo, overflow, ecc.) siamo certi che la risposta rimane lo stesso.

In altre parole, possiamo memorizzare la somma di elementi in ogni vettore, e quando otteniamo una query, sommare gli elementi in quel vettore, quindi cercare il valore più vicino tra quelli indicati.

Questocipermetteràdifarelamaggiorpartedeicalcoliinanticipomoltopiùragionevolmente.

Tuttavia,possiamofareancoramegliodellasemplicericercadituttiqueivettori.Adesempio,potremmocreareunstd::multimap(ostd::unordered_multimap)perdirediusareivettoriassociatiaciascunasomma.Conununordered_multimap,possiamoaspettarciunacomplessitàapprossimativamentecostanteperlaricerca.

Neicommenti,tuttavia,haiaggiuntounrequisitopertrovareiNvettoripiùsimili.Inquestocaso,probabilmentevorraiusareunstd::multimapinvecedellavarietànonordinata.Conquesto,laricercainizialesaràlogaritmicaanzichécostosa(prevista),matrovarel'elementosuccessivopiùsimilepuòesserefattoconunacomplessitàcostante,perchésonoordinati.

Asecondadellasituazione,potrebbeanchevalerelapenadiprendereinconsiderazionel'usodiunvettoreordinatodisomme.Questotendeafareunusosostanzialmentemiglioredellacache,datochememorizzaidatiinmodocontiguo.Ilcompromessoèchenonsupportal'inserimento/lacancellazionedielementicomebene.Seeseguimoltericercheeraramente(omai)modifichiquei5000vettori,alloraunvettoreordinatodisommefunzioneràprobabilmentemeglio.Se,tuttavia,sonosoggettiamoltemodifiche(adesempio,eliminicostantementeivecchivettorieneinseriscidinuovi),unstd::mappotrebbeessereunasceltamigliore.

Unaltropunto:unmultimapusaunaricercabinariapertrovarel'oggettopiùvicino.Seletuedifferenzesonoragionevolmenteequamentedistribuite,puoiinveceusareunaricercainterpolata.Periniziare,trovaladifferenzatralasommapiùpiccolaelapiùgrande.Adesempio,supponiamocheilpiùpiccolosia4eilpiùgrandesia7912038,estiamocercandolasommapiùvicinaa32750.Ladifferenzadellesommeè7912034,quindiiniziamocalcolando32750/7912034=circa0,004.Quindi(assumendoesattamente5000vettori)moltiplichiamoquelloper5000perottenerecirca20.Quindi,invecediiniziarealcentrodellamatricedisomme,possiamoiniziaredall'elemento20^thdell'array(easecondadiquantoerratotalerisultato,possiamoripeterelostessoprocessofinoaraggiungereilpuntodesiderato).

Supponendochelesommesianodistribuiteabbastanzaequamente,questocipermetteditrovarelavocepiùsimileconcircaO(loglogN)complessitàinvecedellacomplessitàO(logN)diunaricercabinaria.Naturalmente,perilmomentohousatol'interpolazionelineare-sesappiamochelesommehanno(peresempio)unadistribuzionelogaritmicaoesponenziale,possiamousareun'interpolazionelogaritmicaoesponenziale.Inaltreparole,lesommenondevonoessereuniformementedistribuiteperfarsìchefunzionicorrettamente-devonoesseredistribuiteinmodoragionevolmenteprevedibile.

loglogNèspessochiamato"pseudo-costante" - cresce con il numero di elementi esaminati, ma cresce così lentamente che per la maggior parte degli scopi pratici può essere trattato come costante - per un piccolo numero di elementi come il tuo 5000, è uno. Per un gran numero di articoli, cresce a 2. Prima che arrivi a 3, stai parlando di più dati di quanti ne puoi immagazzinare in tutta la memoria prodotta sul pianeta terra nella sua intera storia. Prima che arrivi a 4, stai parlando di un numero più grande del numero di atomi nell'universo.

Per le differenze saggiate dagli elementi, Jerry ha fornito una soluzione eccellente. Se è davvero quello che vuoi, questo è un modo perfetto per andare.

Tuttavia, voglio sottolineare che potrebbe esserci una certa confusione tra la differenza di elementi e la distanza tra i vettori. Se vuoi calcolare la distanza dei vettori (= vuoi trovare il vettore che è più vicino al vettore di query) devi ridefinire il tuo calcolo:

Considera questi 2 vettori:

• v1: [1 4]
• v2: [4 1]

Dato un vettore di query q [2 4], è ovvio che v1 è più vicino di v2, sebbene la somma delle differenze sia la stessa:

diff(v1, q) = (1-2) + (4-4) = -1+0 = -1
diff(v2, q) = (4-2) + (1-4) = 2-3 = -1

Il problema con la tua funzione di diff è che le differenze negative dovrebbero essere considerate positive se vuoi conoscere la distanza dei vettori. Quindi usando la funzione distanza (= valori assoluti delle differenze) le equazioni hanno questo aspetto:

dist(v1, q) = abs(1-2) + abs(4-4) = 1+0 = 1
dist(v2, q) = abs(4-2) + abs(1-4) = 2+3 = 5

Ora vediamo chiaramente che v1 è più vicino a q.

Ancora una volta, questa potrebbe non essere una risposta alla domanda iniziale: solo alcuni aggiungono:)

Vorrei suggerire un approccio non ortodosso per calcolare le distanze manhattan tra un vettore di query e un insieme di vettori (m) usando GPGPU.

Supponiamo che il tuo set di vettori sia definito come S (m, n)

S (m,n) = 
   [s_1,1, s_1,2, .... s_1,n

    s_2,1, s_1,2, .... s_2,n

    ....               ....

    s_m,1, s_m,2, .... s_m,n]

Prima devi trasformare i tuoi vettori dimensionali N (V1, .. Vn) in N + 1 vettori dimensionali come (V1, ... Vn, 1), che può essere fatto nel tempo O (m).

S'(m,n+1)= 
    [s_1,1, s_1,2, .... s_1,n ,1

     s_2,1, s_1,2, .... s_2,n, 1

     ....               ....

     s_m,1, s_m,2, .... s_m,n ,1]

Quindi puoi tradurre il tuo set intorno al tuo vettore di query Q '= [Q1, ..., Qn, 1] usando

TQ(n+1,n+1)= 
    [1, 0, .... 0, -Q1

     0, 1, .... 0, -Q2

     ....         ....

     0, 0, .... 1, -Qn
     0, 0, .... 0, 1]

S''(m,n+1)= S'(m,n+1) x TQ(n+1,n+1);

Le distanze Manhattan possono essere calcolate utilizzando la seguente moltiplicazione di matrice:

MD(n+1,1)= 
    [1, 

     1, 

     ...

     1, 
     0]

 S'''(m,1) = S''(m,n+1) x MD(n+1,1)

Tutta la moltiplicazione della matrice può essere eseguita in GPU come indicato nella Sezione 3.4 di Calcoli matriciali sulla GPU utilizzando CUDA per ottimizzare l'elaborazione

Ora, l'unica cosa che devi fare è trovare min (S '' ') e il suo vettore corrispondente che può essere fatto in tempo O (m).