dopasowywanie ciągów w liście uporządkowanej według algorytmu geograficznego (metoda MATLABA)

Question

Mam dużą alfabetycznie tablicę komórek ciągów (~ 495 tysięcy), z dużą liczbą duplikatów (które są obok siebie, ponieważ są alfabetyczne).

Dla danego łańcucha look-up, muszę znaleźć wszystkie ciągi w wykazie, który będzie pasował do jednego mijam w.

Używam strcmp(lookUpString,list) to zrobić, ale jest to bardzo powolny - Myślę, że przechodzi przez każdą wartość na liście do porównania, ponieważ nie wie, że jest posortowana alfabetycznie.

Mogę napisać pętlę while do iteracji na liście, aby porównać każdy ciąg znaków za pomocą strcmp, aż znajdę blok ciągów znaków, które chcę (a następnie zatrzymać), ale zastanawiałem się, czy istnieje sposób "matlab" to (tj. wykonywanie logicznych operacji porównania na posortowanej tablicy).

Dzięki za pomoc!

Answer 1

UPDATE: I nie był zadowolony z moich wcześniejszych „Metoda 3” Właśnie tak zmodyfikowaliśmy go trochę, aby uzyskać lepszą wydajność. Teraz działa prawie 10 razy szybciej niż naiwny strcmp.

strcmp wygrywa na moim komputerze (2011b w systemie Linux Mint 12). W szczególności działa znacznie lepiej niż ismember. Możesz jednak odrobinę przyspieszyć, jeśli wykonasz ręczne sprężanie. Rozważmy następujący test prędkości:

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 

Wyjście jest:

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

Answer 2

ismember jest twoim przyjacielem. Zamiast przeszukiwanie liniowe, it does binary search.

Answer 3

Spróbuj binarny-search.

To prawie 13 razy szybciej (!)

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 

Jest to kod bin-search używam:

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 

gdzie można dostać strlexcmp() z ciągiem Petera Johna Acklam za -możliwość, pod adresem: http://home.online.no/~pjacklam/matlab/software/util/strutil/

Na koniec jest to skrypt testowy, którego użyłem:

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

Uwaga: wyniki mogą być inne w przypadku dłuższych łańcuchów.