kết hợp chuỗi trong danh sách được sắp xếp theo thứ tự đại diện (theo cách MATLAB)

Question

Tôi có một chuỗi ô được sắp xếp theo thứ tự bảng chữ cái lớn (~ 495 nghìn), với nhiều bản sao (nằm cạnh nhau, vì nó là chữ cái).

Đối với một chuỗi nhìn lên nhất định, tôi cần phải tìm tất cả các chuỗi trong danh sách đó sẽ phù hợp với một trong tôi vượt qua trong.

Tôi đã sử dụng strcmp(lookUpString,list) để làm điều này, nhưng điều này là cực kỳ chậm - Tôi nghĩ rằng nó đang trải qua từng giá trị trong danh sách để so sánh, bởi vì nó không biết nó được sắp xếp theo thứ tự bảng chữ cái.

Tôi có thể viết một vòng lặp while để lặp qua danh sách để so sánh từng chuỗi bằng cách sử dụng strcmp cho đến khi tôi tìm khối chuỗi mà tôi muốn (và sau đó dừng), nhưng tôi đã tự hỏi liệu có một cách "matlab" hay không điều này (nghĩa là thực hiện các phép so sánh logic trên một mảng đã sắp xếp).

Cảm ơn sự giúp đỡ của bạn!

Answer 1

UPDATE: tôi đã không hài lòng với trước đây của tôi "Phương pháp 3" vì vậy tôi đã chỉ cần tái jigged nó một chút để có được hiệu suất tốt hơn. Nó bây giờ chạy nhanh hơn gần 10 lần so với strcmp ngây thơ.

strcmp thắng trên máy của tôi (2011b trên Linux Mint 12). Đặc biệt, nó hoạt động tốt hơn nhiều so với ismember. Tuy nhiên, bạn có thể tăng thêm chút tốc độ nếu bạn thực hiện một số việc định vị thủ công. Hãy xem xét các thử nghiệm tốc độ sau:

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 

Đầu ra là:

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

Answer 2

ismember là bạn của bạn. Thay vì tìm kiếm tuyến tính, it does binary search.

Answer 3

Hãy thử nhị phân tìm kiếm.

Nó là nhanh hơn gần 13 lần (!):

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 

Đây là mã bin-search Tôi đang sử dụng:

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 

nơi bạn có thể nhận được strlexcmp() từ chuỗi Peter John Acklam của -nhiều, tại: http://home.online.no/~pjacklam/matlab/software/util/strutil/

Và cuối cùng đây là tập lệnh thử nghiệm tôi đã sử dụng:

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

Lưu ý rằng kết quả có thể khác với các chuỗi dài hơn.