coincidencia de cadenas en una lista alpbetically ordenada (la forma de MATLAB)

Question

Tengo una gran matriz ordenada alfabéticamente de cadenas (~ 495 mil), con muchos duplicados (que están uno al lado del otro, porque es alfabético).

Para una cadena de consulta dado, tengo que encontrar todas las cadenas de la lista que coincida con la que me pase en.

He estado usando strcmp(lookUpString,list) para hacer esto, pero esto es extremadamente lento - Creo que está pasando por cada valor en la lista para comparar, porque no sabe que está ordenado alfabéticamente.

Podría escribir un ciclo while para recorrer la lista y comparar cada cadena usando strcmp hasta encontrar el bloque de cadenas que quiero (y luego detener), pero me preguntaba si había una forma de "matlab" de hacer esto (es decir, realizar operaciones de comparación lógica en una matriz ordenada).

Gracias por su ayuda!

Answer 1

ACTUALIZACIÓN: que no estaba satisfecho con mi anterior "Método 3", por lo que acabo de volver a Jigged un poco para obtener un mejor rendimiento. Ahora corre casi 10 veces más rápido que un ingenuo strcmp.

strcmp gana en mi máquina (2011b en Linux Mint 12). En particular, funciona mucho mejor que ismember. Sin embargo, puede ganar un poco de velocidad extra si realiza una presecado manual usted mismo. Considere la siguiente prueba de velocidad:

NumIter = 100; 
N = 495000; 
K = N/20; 
List = cell(N, 1); 
for i = 1:20 
    List(i*K - K + 1:i*K) = cellstr(char(i+96)); 
end 

StrToFind = cell(NumIter, 1); 
for j = 1:NumIter 
    StrToFind{j} = char(round(rand * 20) + 96); 
end 

%# METHOD 1 (ismember) 
tic 
for j = 1:NumIter 
    Index1 = ismember(List, StrToFind{j}); 
    Soln1 = List(Index1); 
end 
toc 

%#METHOD 2 (strcmp) 
tic 
for j = 1:NumIter 
    Index2 = strcmp(StrToFind{j}, List); 
    Soln2 = List(Index2); 
end 
toc 

%#METHOD 3 (strmp WITH MANUAL PRE-SORTING)  
tic 
for j = 1:NumIter 
    CurStrToFind = StrToFind{j}; 
    K = 100; 
    I1 = zeros(K, 2); I1(1, :) = ones(1, 2); 
    I2 = zeros(K, 2); I2(end, 1) = 1; I2(end, 2) = N; 
    KDiv = floor(N/K); 
    for k = 2:K-1 
     CurSearchNum = k * KDiv; 
     CurListItem = List{CurSearchNum}; 
     if CurListItem < CurStrToFind; I1(k, 1) = 1; end; 
     if CurListItem > CurStrToFind; I2(k, 1) = 1; end; 
     I1(k, 2) = CurSearchNum; I2(k, 2) = CurSearchNum; 
    end 
    a = find(I1(:, 1), 1, 'last'); 
    b = find(I2(:, 1), 1, 'first'); 
    ShortList = List(I1(a, 2):I2(b, 2)); 
    Index3 = strcmp(CurStrToFind, ShortList); 
    Soln3 = ShortList(Index3); 
end 
toc 

La salida es:

Elapsed time is 6.411537 seconds. 
Elapsed time is 1.396239 seconds. 
Elapsed time is 0.150143 seconds. 

Answer 2

ismember es tu amigo. En lugar de búsqueda lineal, it does binary search.

Answer 3

Trate de búsqueda binaria.

Es casi 13 veces más rápido (!):

Elapsed time is 7.828260 seconds. % ismember 
Elapsed time is 0.775260 seconds. % strcmp 
Elapsed time is 0.113533 seconds. % strmp WITH MANUAL PRE-SORTING 
Elapsed time is 0.008243 seconds. % binsearch 

Este es el código bin-búsqueda que estoy usando:

function ind = binSearch(key, cellstr) 
    % BINSEARCH that find index i such that cellstr(i)<= key <= cellstr(i+1) 
    % 
    % * Synopsis: ind = binSearch(key, cellstr) 
    % * Input : key = what to search for 
    %   : cellstr = sorted cell-array of string (others might work, check strlexcmp()) 
    % * Output : ind = index in x cellstr such that cellstr(i)<= key <= cellstr(i+1) 
    % * Depends : strlexcmp() from Peter John Acklam’s string-utilities, 
    %    at: http://home.online.no/~pjacklam/matlab/software/util/strutil/ 
    % 
    % Transcoded from a Java version at: http://googleresearch.blogspot.it/2006/06/extra-extra-read-all-about-it-nearly.html 
    % ankostis, Aug 2013 

    low = 1; 
    high = numel(cellstr); 

    while (low <= high) 
     ind = fix((low + high)/2); 
     val = cellstr{ind}; 

     d = strlexcmp(val, key); 
     if (d < 0) 
      low = ind + 1; 
     elseif (d > 0) 
      high = ind - 1; 
     else 
      return;  %% Key found. 
     end 
    end 
    ind = -(low);  %% Not found! 
end 

donde se puede obtener strlexcmp() de cadena de Peter John Acklam -utilities, en: http://home.online.no/~pjacklam/matlab/software/util/strutil/

Y finalmente este es el script de prueba he usado:

%#METHOD 4 (WITH BIN-SEARCH)  
tic 
for j = 1:NumIter 
    Index1 = binsearch(StrToFind{j}, List); 
    Soln4 = List(Index1); 
end 

Tenga en cuenta que los resultados pueden ser diferentes con cadenas más largas.