Versión más rápida de búsqueda para vectores ordenados (MATLAB)

Tengo un código del siguiente tipo en MATLAB:

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

Esto devuelve 4,5,6 – los índices de elementos en la matriz igual a 3. Ahora. mi código hace este tipo de cosas con vectores muy largos. Los vectores siempre están ordenados .

Por lo tanto, me gustaría una función que reemplace la complejidad O (n) de find con O (log n), a expensas de que la matriz deba ser ordenada.

Estoy al tanto de ismember, pero por lo que sé, no devuelve los índices de todos los ítems, solo el último (los necesito a todos).

Por razones de portabilidad, necesito que la solución sea solo de MATLAB (no hay archivos comp comstackdos, etc.)

Aquí hay una implementación rápida usando búsqueda binaria. Este archivo también está disponible en 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 

El enfoque de Daniel es inteligente y su función myFind2 es definitivamente rápida, pero hay errores / errores que ocurren cerca de las condiciones de contorno o en el caso de que los límites superior e inferior produzcan un rango fuera del conjunto pasado.

Además, como señaló en su comentario sobre su respuesta, su implementación tenía algunas ineficiencias que podrían mejorarse. Implementé una versión mejorada de su código, que se ejecuta más rápido, mientras que también maneja correctamente las condiciones de contorno. Además, este código incluye más comentarios para explicar lo que está sucediendo. ¡Espero que esto ayude a alguien de la misma manera que el código de Daniel me ayudó aquí!

 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 

Tenga en cuenta que la versión mejorada de la función Daniels searchFor es ahora simplemente:

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

ismember le dará todos los índices si mira el primer resultado:

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

inds =

  4 5 6 

Solo necesitas usar el orden correcto de las entradas.

Tenga en cuenta que hay una función auxiliar utilizada por ismember que puede llamar directamente:

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

El uso de ismembc ahorrará tiempo de cálculo ya que ismember llamadas issorted se issorted primero, pero esto omitirá el control.

Tenga en cuenta que las versiones más nuevas de matlab tienen un builtin llamado por builtin('_ismemberoneoutput',a,b) con la misma funcionalidad.


Dado que las aplicaciones anteriores de ismember , etc. son un poco hacia atrás (buscando cada elemento de x en el segundo argumento en lugar de al revés), el código es mucho más lento de lo necesario. Como señala el OP, es desafortunado que [~,loc]=ismember(3,x) solo proporcione la ubicación de la primera aparición de 3 en x , en lugar de en todas. Sin embargo, si tiene una versión reciente de MATLAB (R2012b +, creo), puede utilizar aún más funciones incorporadas no documentadas para obtener el primero y los últimos índices. Estos son ismembc2 y ismembc2 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; 

Aún más lento que el gran código de MATLAB de Daniel R., pero ahí está ( rntmX agregado al punto de referencia de randomatlabuser) solo por diversión:

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

Aquí están los trozos de documentación para estas funciones 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. 

En realidad, se hace referencia a un ISMEMBERLAST , pero parece que no existe (¿todavía?).

Esta no es una respuesta. Simplemente estoy comparando el tiempo de ejecución de las tres soluciones sugeridas por Chappjc y 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 búsqueda binaria de Daniel es muy 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 

Necesitaba una función como esta. Gracias por el mensaje @Daniel!

Trabajé un poco con eso porque necesitaba encontrar varios índices en la misma matriz. Quería evitar la sobrecarga de arrayfun (o similar) o llamar a la función varias veces. Entonces puede pasar un grupo de valores dentro del range y obtendrá los índices en la 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 

Supongo que puedes usar un parfor o arrayfun en arrayfun lugar. Sin embargo, no me he probado a mí mismo en qué tamaño de range vale la pena.

Otra posible mejora sería usar los índices encontrados previamente (si el range está ordenado) para disminuir el espacio de búsqueda. Soy escéptico de su potencial para ahorrar CPU debido al tiempo de ejecución O(log n) .


La función final terminó ejecutándose un poco más rápido. Usé el framework de @randomatlabuser para eso:

 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 

No es una gran mejora, pero ayuda porque necesito ejecutar varios miles de búsquedas.

 % 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 esto pueda ayudar a alguien.


EDITAR

Si hay una posibilidad significativa de tener coincidencias exactas, vale la pena utilizar el ismember incorporado muy rápido antes de llamar a la función:

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