Versão mais rápida de encontrar por vetores classificados (MATLAB)

Eu tenho código do seguinte tipo no MATLAB:

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

Isso retorna 4,5,6 – os índices de elementos na matriz igual a 3. Agora. meu código faz esse tipo de coisa com vetores muito longos. Os vetores são sempre classificados .

Portanto, gostaria de uma function que substitua a complexidade O (n) de find por O (log n), à custa de que a matriz tenha que ser classificada.

Estou ciente do ismember, mas pelo que sei não retorna os índices de todos os itens, apenas o último (eu preciso de todos eles).

Por razões de portabilidade, eu preciso que a solução seja somente MATLAB (sem arquivos mex compilados, etc.)

Aqui está uma implementação rápida usando a pesquisa binária. Este arquivo também está disponível no 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 

A abordagem de Daniel é inteligente e sua function myFind2 é definitivamente rápida, mas há erros / bugs que ocorrem perto das condições de contorno ou no caso em que os limites superior e inferior produzem um intervalo fora do conjunto passado.

Além disso, como ele observou em seu comentário sobre sua resposta, sua implementação teve algumas ineficiências que poderiam ser melhoradas. Eu implementei uma versão melhorada de seu código, que roda mais rápido, enquanto também manipula corretamente as condições de contorno. Além disso, esse código inclui mais comentários para explicar o que está acontecendo. Espero que isso ajude alguém do jeito que o código de Daniel me ajudou aqui!

 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 

Note que a versão melhorada da function searchFor de Daniels agora é simplesmente:

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

ismember fornecerá todos os índices se você observar a primeira saída:

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

inds

  4 5 6 

Você só precisa usar a ordem correta de inputs.

Observe que há uma function auxiliar usada pelo ismember que você pode chamar diretamente:

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

O uso do ismembc economizará o tempo de computação, pois ismember chamadas do issorted primeiro issorted , mas isso omitirá a verificação.

Note que as versões mais recentes do Matlab têm um builtin chamado por builtin('_ismemberoneoutput',a,b) com a mesma funcionalidade.


Como os aplicativos acima de ismember , etc. estão um pouco para trás (procurando por cada elemento de x no segundo argumento, e não o contrário), o código é muito mais lento do que o necessário. Como o OP aponta, é lamentável que [~,loc]=ismember(3,x) apenas forneça a localização da primeira ocorrência de 3 em x , em vez de todos. No entanto, se você tiver uma versão recente do MATLAB (R2012b +, eu acho), você pode usar ainda mais funções internas não documentadas para obter o primeiro e os últimos índices! Estes são 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; 

Ainda mais lento que o ótimo código MATLAB de Daniel R., mas é isso ( rntmX adicionado ao benchmark do randomatlabuser) apenas por diversão:

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

Aqui estão os pedaços de documentação para essas funções dentro de 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. 

Na verdade, existe uma referência a um ISMEMBERLAST embutido, mas parece não existir (ainda?).

Esta não é uma resposta – estou apenas comparando o tempo de execução das três soluções sugeridas por 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 

A busca binária de Daniel é muito rápida.

 % 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 

Eu precisava de uma function como essa. Obrigado pelo post @Daniel!

Eu trabalhei um pouco com isso porque precisava encontrar vários índices no mesmo array. Eu queria evitar a sobrecarga de arrayfun (ou algo parecido) ou chamar a function várias vezes. Então você pode passar um monte de valores no range e você obterá os índices na matriz.

 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 

Eu acho que você pode usar um parfor ou arrayfun vez disso. Eu não me testei em que tamanho de range vale a pena, no entanto.

Outra possível melhoria seria usar os índices encontrados anteriormente (se o range for classificado) para diminuir o espaço de pesquisa. Eu sou cético em relação ao seu potencial para economizar CPU por causa do tempo de execução do O(log n) .


A function final acabou funcionando um pouco mais rápido. Eu usei o framework do @randomatlabuser para isso:

 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 

Não é uma grande melhoria, mas ajuda porque preciso executar vários milhares de pesquisas.

 % 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 

Espero que isso possa ajudar alguém.


EDITAR

Se houver uma chance significativa de ter correspondências exatas, vale a pena usar o ismember muito rápido antes de chamar a function:

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