स्ट्रिंग मिलान (MATLAB रास्ता)

Question

मैं (है, जो एक दूसरे के बगल में हैं, क्योंकि यह वर्णमाला है) डुप्लिकेट के बहुत सारे के साथ, तार का एक बड़ा वर्णानुक्रम सेल सरणी (~ 495 हजार) की है।

किसी दिए गए लुक-अप स्ट्रिंग के लिए, मैं सूची में सभी श्रृंखलाएं जिनमें एक मैं में पारित की पूर्ति करेंगे खोजने की जरूरत है।

मैं strcmp(lookUpString,list) उपयोग कर रहे हैं यह करने के लिए, लेकिन यह बेहद धीमी गति से है - मुझे लगता है कि यह तुलना में सूची में प्रत्येक मान के माध्यम से जा रहा है, क्योंकि यह नहीं जानता कि यह वर्णानुक्रम में क्रमबद्ध है।

मैं strcmp का उपयोग करके प्रत्येक स्ट्रिंग की तुलना करने के लिए सूची के माध्यम से फिर से लिखने के लिए थोड़ी देर लूप लिख सकता हूं जब तक कि मुझे स्ट्रिंग्स (और फिर रुकें) के ब्लॉक को न मिल जाए, लेकिन मैं सोच रहा था कि क्या "matlab" तरीका करने का तरीका है यह (यानी एक क्रमबद्ध सरणी पर तार्किक तुलना संचालन प्रदर्शन)।

आपकी मदद के लिए धन्यवाद!

Answer 1

अद्यतन: मैं अपने पहले "विधि 3" से संतुष्ट नहीं था तो मैं बस यह एक छोटे फिर से jigged गए बेहतर प्रदर्शन प्राप्त करने के लिए। यह अब एक बेवकूफ strcmp से लगभग 10 गुना तेजी से चलता है।

strcmp मेरी मशीन पर जीतता है (लिनक्स मिंट 12 पर 2011 बी)। विशेष रूप से, यह ismember से काफी बेहतर काम करता है। हालांकि, अगर आप कुछ मैनुअल खुद को पूर्व निर्धारित करते हैं तो आप थोड़ा अतिरिक्त गति प्राप्त कर सकते हैं। निम्नलिखित गति परीक्षण पर विचार करें:

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 

उत्पादन होता है:

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

Answer 2

ismember आपका मित्र है। इसके बजाय रैखिक खोज की, it does binary search.

Answer 3

बाइनरी-खोज का प्रयास करें। (!)

यह लगभग 13 गुना तेजी से होता है: जहां पीटर जॉन Acklam की स्ट्रिंग से strlexcmp() प्राप्त कर सकते हैं

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 

:

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 

यह मैं उपयोग कर रहा हूँ बिन-खोज कोड है -utilities, पर: http://home.online.no/~pjacklam/matlab/software/util/strutil/

और अंत में इस परीक्षण स्क्रिप्ट मैं प्रयोग किया जाता है:

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

ध्यान दें कि परिणाम लंबी तार के साथ अलग अलग हो सकता है।