5

我有一个按字母顺序排列的大型字符串单元数组（约 49.5 万），有很多重复项（它们彼此相邻，因为它是按字母顺序排列的）。

对于给定的查找字符串，我需要在列表中找到与我传入的字符串匹配的所有字符串。

我一直在strcmp(lookUpString,list)这样做，但这非常慢 - 我认为它正在通过列表中的每个值进行比较，因为它不知道它是按字母顺序排序的。

我可以编写一个while循环来遍历列表以比较每个字符串，strcmp直到我找到我想要的字符串块（然后停止），但我想知道是否有一种“matlab”方式来执行此操作（即执行逻辑排序数组上的比较操作）。

谢谢你的帮助！

4

3 回答 3

4

更新：我对我之前的“方法 3”不满意，所以我只是重新调整了一下以获得更好的性能。它现在的运行速度几乎是 naive 的 10 倍strcmp。

strcmp在我的机器上获胜（Linux Mint 12 上的 2011b）。特别是，它比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.
于 2012-10-03T01:09:14.663 回答
1

ismember是你的朋友。它不是线性搜索，而是二进制搜索。

于 2012-10-03T00:32:03.780 回答
0

尝试二进制搜索。

它几乎快 13（！）倍：

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

这是我正在使用的 bin 搜索代码：

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

您可以strlexcmp()从 Peter John Acklam 的 string-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

请注意，对于更长的字符串，结果可能会有所不同。

于 2013-08-27T09:31:31.370 回答