Versione più veloce di ricerca per vettori ordinati (MATLAB)

Ho il codice del seguente tipo in MATLAB:

indices = find([1 2 2 3 3 3 4 5 6 7 7] == 3) 

Questo restituisce 4,5,6 – gli indici degli elementi nella matrice pari a 3. Ora. il mio codice fa questo genere di cose con vettori molto lunghi. I vettori sono sempre ordinati .

Pertanto, vorrei una funzione che sostituisce la complessità O (n) di trovare con O (log n), a spese che l’array deve essere ordinato.

Sono a conoscenza di ismember, ma per quello che so non restituisce gli indici di tutti gli articoli, solo l’ultimo (ho bisogno di tutti loro).

Per motivi di portabilità, ho bisogno che la soluzione sia solo MATLAB (nessun file mex compilato, ecc.)

Ecco un’implementazione veloce utilizzando la ricerca binaria. Questo file è anche disponibile su github

 function [b,c]=findInSorted(x,range) %findInSorted fast binary search replacement for ismember(A,B) for the %special case where the first input argument is sorted. % % [a,b] = findInSorted(x,s) returns the range which is equal to s. % r=a:b and r=find(x == s) produce the same result % % [a,b] = findInSorted(x,[from,to]) returns the range which is between from and to % r=a:b and r=find(x >= from & x < = to) return the same result % % For any sorted list x you can replace % [lia] = ismember(x,from:to) % with % [a,b] = findInSorted(x,[from,to]) % lia=a:b % % Examples: % % x = 1:99 % s = 42 % r1 = find(x == s) % [a,b] = myFind(x,s) % r2 = a:b % %r1 and r2 are equal % % See also FIND, ISMEMBER. % % Author Daniel Roeske  A=range(1); B=range(end); a=1; b=numel(x); c=1; d=numel(x); if A< =x(1) b=a; end if B>=x(end) c=d; end while (a+1 

L’approccio di Daniel è intelligente e la sua funzione myFind2 è decisamente veloce, ma ci sono errori / bug che si verificano vicino alle condizioni al contorno o nel caso in cui i limiti superiore e inferiore producano un intervallo al di fuori del set passato.

Inoltre, come ha notato nel suo commento sulla sua risposta, la sua implementazione ha avuto alcune inefficienze che potrebbero essere migliorate. Ho implementato una versione migliorata del suo codice, che gira più velocemente, mentre gestisce correttamente anche le condizioni al contorno. Inoltre, questo codice include più commenti per spiegare cosa sta succedendo. Spero che questo aiuti qualcuno come il codice di Daniele mi ha aiutato qui!

 function [lower_index,upper_index] = myFindDrGar(x,LowerBound,UpperBound) % fast O(log2(N)) computation of the range of indices of x that satify the % upper and lower bound values using the fact that the x vector is sorted % from low to high values. Computation is done via a binary search. % % Input: % % x- A vector of sorted values from low to high. % % LowerBound- Lower boundary on the values of x in the search % % UpperBound- Upper boundary on the values of x in the search % % Output: % % lower_index- The smallest index such that % LowerBound< =x(index)<=UpperBound % % upper_index- The largest index such that % LowerBound<=x(index)<=UpperBound if LowerBound>x(end) || UpperBound= LowerBound lower_index_b=lw; % decrease lower_index_b (whose x value remains \geq to lower bound) else lower_index_a=lw; % increase lower_index_a (whose x value remains less than lower bound) if (lw>upper_index_a) && (lwlower_index_a) lower_index_b=up;%decrease lower_index_b (whose x value remains greater than upper bound and thus lower bound) end end end if x(lower_index_a)>=LowerBound lower_index = lower_index_b; else lower_index = lower_index_a; end if x(upper_index_b)< =UpperBound upper_index = upper_index_a; else upper_index = upper_index_b; end 

Si noti che la versione migliorata della funzione searchfor di Daniels ora è semplicemente:

 function [lower_index,upper_index] = mySearchForDrGar(x,value) [lower_index,upper_index] = myFindDrGar(x,value,value); 

ismember ti darà tutti gli indici se guardi al primo output:

 >> x = [1 2 2 3 3 3 4 5 6 7 7]; >> [tf,loc]=ismember(x,3); >> inds = find(tf) 

inds =

  4 5 6 

Hai solo bisogno di usare l’ordine giusto di input.

Si noti che esiste una funzione di supporto utilizzata da ismember che è ansible chiamare direttamente:

 % ISMEMBC - S must be sorted - Returns logical vector indicating which % elements of A occur in S tf = ismembc(x,3); inds = find(tf); 

L’utilizzo di ismembc consente di risparmiare tempo di calcolo dal momento che ismember chiama prima l’ issorted , ma questo non tralascia il controllo.

Si noti che le versioni più recenti di MATLAB hanno un builtin chiamato da builtin('_ismemberoneoutput',a,b) con la stessa funzionalità.


Poiché le suddette applicazioni di ismember , ecc. Sono in qualche modo arretrate (cercando ogni elemento di x nel secondo argomento piuttosto che nel contrario), il codice è molto più lento del necessario. Come sottolinea l’OP, è spiacevole che [~,loc]=ismember(3,x) fornisca solo la posizione della prima occorrenza di 3 in x , piuttosto che di tutti. Tuttavia, se si dispone di una versione recente di MATLAB (R2012b +, penso), è ansible utilizzare ancora più funzioni incorporate non documentate per ottenere il primo un ultimo indice! Questi sono ismembc2 e builtin('_ismemberfirst',searchfor,x) :

 firstInd = builtin('_ismemberfirst',searchfor,x); % find first occurrence lastInd = ismembc2(searchfor,x); % find last occurrence % lastInd = ismembc2(searchfor,x(firstInd:end))+firstInd-1; % slower inds = firstInd:lastInd; 

Ancora più lento del grande codice MATLAB di Daniel R., ma rntmX ( rntmX aggiunto al benchmark di randomatlabuser) solo per divertimento:

 mean([rntm1 rntm2 rntm3 rntmX]) ans = 0.559204323050486 0.263756852283128 0.000017989974213 0.000153682125682 

Ecco i bit di documentazione per queste funzioni all’interno di ismember.m :

 % ISMEMBC2 - S must be sorted - Returns a vector of the locations of % the elements of A occurring in S. If multiple instances occur, % the last occurrence is returned % ISMEMBERFIRST(A,B) - B must be sorted - Returns a vector of the % locations of the elements of A occurring in B. If multiple % instances occur, the first occurence is returned. 

C’è effettivamente un riferimento a un builtin ISMEMBERLAST , ma non sembra esistere (ancora?).

Questa non è una risposta – sto solo confrontando il tempo di esecuzione delle tre soluzioni suggerite da chappjc e Daniel R.

 N = 5e7; % length of vector p = 0.99; % probability KK = 100; % number of instances rntm1 = zeros(KK, 1); % runtime with ismember rntm2 = zeros(KK, 1); % runtime with ismembc rntm3 = zeros(KK, 1); % runtime with Daniel's function for kk = 1:KK x = cumsum(rand(N, 1) > p); searchfor = x(ceil(4*N/5)); tic [tf,loc]=ismember(x, searchfor); inds1 = find(tf); rntm1(kk) = toc; tic tf = ismembc(x, searchfor); inds2 = find(tf); rntm2(kk) = toc; tic a=1; b=numel(x); c=1; d=numel(x); while (a+1 

La ricerca binaria di Daniel è molto veloce.

 % Mean of running time mean([rntm1 rntm2 rntm3]) % 0.631132275892504 0.295233981447746 0.000400786666188 % Percentiles of running time prctile([rntm1 rntm2 rntm3], [0 25 50 75 100]) % 0.410663611685559 0.175298784336465 0.000012828868032 % 0.429120717937665 0.185935198821797 0.000014539383770 % 0.582281366154709 0.268931132925888 0.000019243302048 % 0.775917520641649 0.385297304740352 0.000026940622867 % 1.063753914942895 0.592429428396956 0.037773746662356 

Avevo bisogno di una funzione come questa. Grazie per il post @Daniel!

Ho lavorato un po ‘con esso perché avevo bisogno di trovare diversi indici nello stesso array. Volevo evitare l’overhead di arrayfun (o simili) o chiamare la funzione più volte. Quindi puoi passare un gruppo di valori range e otterrai gli indici nell’array.

 function idx = findInSorted(x,range) % Author Dídac Rodríguez Arbonès (May 2018) % Based on Daniel Roeske's solution: % Daniel Roeske  % https://github.com/danielroeske/danielsmatlabtools/blob/master/matlab/data/findinsorted.m range = sort(range); idx = nan(size(range)); for i=1:numel(range) idx(i) = aux(x, range(i)); end end function b = aux(x, lim) a=1; b=numel(x); if lim< =x(1) b=a; end if lim>=x(end) a=b; end while (a+1 

Suppongo che tu possa usare un parfor o arrayfun invece. Non mi sono ancora messo alla prova su quale sia la portata della range che paga.

Un altro ansible miglioramento sarebbe utilizzare gli indici trovati precedentemente (se l' range è ordinato) per ridurre lo spazio di ricerca. Sono scettico sul suo potenziale di risparmiare CPU a causa del runtime O(log n) .


La funzione finale ha finito per funzionare leggermente più veloce. Ho usato il framework di @randomatlabuser per questo:

 N = 5e6; % length of vector p = 0.99; % probability KK = 100; % number of instances rntm1 = zeros(KK, 1); % runtime with ismember rntm2 = zeros(KK, 1); % runtime with ismembc rntm3 = zeros(KK, 1); % runtime with Daniel's function for kk = 1:KK x = cumsum(rand(N, 1) > p); searchfor = x(ceil(4*N/5)); tic range = sort(searchfor); idx = nan(size(range)); for i=1:numel(range) idx(i) = aux(x, range(i)); end rntm1(kk) = toc; tic a=1; b=numel(x); c=1; d=numel(x); while (a+1=x(end) a=b; end while (a+1 

Non è un grande miglioramento, ma aiuta perché ho bisogno di eseguire diverse migliaia di ricerche.

 % Mean of running time mean([rntm1 rntm2]) % 9.9624e-05 5.6303e-05 % Percentiles of running time prctile([rntm1 rntm2], [0 25 50 75 100]) % 3.0435e-05 1.0524e-05 % 3.4133e-05 1.2231e-05 % 3.7262e-05 1.3369e-05 % 3.9111e-05 1.4507e-05 % 0.0027426 0.0020301 

Spero che questo possa aiutare qualcuno.


MODIFICARE

Se c'è una possibilità significativa di avere corrispondenze esatte, vale la pena utilizzare l' ismember incorporata molto veloce prima di chiamare la funzione:

 [found, idx] = ismember(range, x); idx(~found) = arrayfun(@(r) aux(x, r), range(~found));