Векторизовать этот цикл поиска

Я хочу векторизовать этот цикл:

needle = [1 2 3];

haystack  = [0 0 1 2 3 0 1 2 3;
             0 1 2 3 0 1 2 3 0;
             0 0 0 1 2 3 0 0 0];

for ii = 1:3

    indices{ii} = strfind (haystack(ii,:), needle);

end

indices{:}

Затем indices содержит начальные позиции needle в каждой строке haystack (может быть разное количество раз в строке):

3 7
2 6
4

Любая команда (команды) подойдет, не обязательно должна быть strfind, если она векторизована.


person andrelucas    schedule 08.03.2014    source источник


Ответы (4)


Если вы не хотите использовать цикл for, вы можете сделать следующее:

 result = cellfun(@(row) strfind(row, needle), num2cell(haystack, 2), 'UniformOutput', 0);
person Marcin    schedule 08.03.2014

Можно объединить всю переменную haystack, а затем найти в ней needle следующим образом:

totalWhiteSpaces=isspace(haystack); %finds white space locations
totalWhiteSpaces=sum(totalWhiteSpaces(1,:),2); %Assumes that "haystack" has equal number 
                                     %of characters (including whitespaces) in each row.

realColumns=size(haystack,2)-totalWhiteSpaces; %gets how many characters are 
                                               %there in a row excluding whitespaces
needle(needle==' ')='';
haystack1=haystack';
haystack2=(haystack1(:))';
haystack2(haystack2==' ')='';  %removes whitespace
result=strfind(haystack2,needle);  %find the pattern
rowsOfResult=uint32(result/realColumns)+1; %necessary since we had concatenated the array.
                                          %It is kind of reshaping operation.
resultValue=mod(result,realColumns);

Я думаю, вы можете сформировать свою окончательную матрицу отсюда.

Результаты по времени: Вы можете увидеть преимущество этого кода, когда ваш haystack станет больше. Согласно моим экспериментам, для размера 300000x9 ваш код занимает около 0,38 секунды. Мой код занимает около 0,23 секунды, а код с использованием cellfun занимает 2,23 секунды. Я думаю, это из-за операции num2cell. Кроме того, cellfun использует for-loop внутри, поэтому он не является действительно векторизованным.

person Autonomous    schedule 08.03.2014

Если у вас все в порядке с поиском номеров столбцов с соответствующими номерами строк в другом векторе, как предложил Луис, вы также можете использовать это -

%// Main portion
haystack_t = haystack';
num1 = strfind(num2str(haystack_t(:))',num2str(needle(:))');
col = rem(num1,size(haystack,2));
ind = floor(num1/size(haystack,2))+1;

%// We need to remove indices that get into account because of concatenation of all the numbers into one big string
rm_ind = col> (size(haystack,2) - numel(needle))+1;
col(rm_ind)=[];
ind(rm_ind)=[];

Работает с различными входами иглы -

RUN1 (Original values):
needle =
     1     2     3
haystack =
     0     0     1     2     3     0     1     2     3
     0     1     2     3     0     1     2     3     0
     0     0     0     1     2     3     0     0     0
col =
     3     7     2     6     4
ind =
     1     1     2     2     3

RUN2 :
needle =
     1     2     3     0     1
haystack =
     0     0     1     2     3     0     1     2     3
     0     1     2     3     0     1     2     3     0
     0     0     0     1     2     3     0     0     0
col =
     3     2
ind =
     1     2
person Divakar    schedule 08.03.2014

Если вы можете принять результат в другом формате (более подходящем для векторизации):

[m n] = size(haystack);
haystackLin = haystack.';
haystackLin = haystackLin(:).'; %// linearize haystack row-wise
ind = strfind(haystackLin,needle); %// find matches
[jj ii] = ind2sub([n m],ind); %// convert to row and column
valid = jj<=n-numel(needle)+1; %// remove false matches (spanning several rows)
result = [ii(valid).' jj(valid).'];

Формат результата

result =

     1     3
     1     7
     2     2
     2     6
     3     4
person Luis Mendo    schedule 08.03.2014
comment
Луис, я не думаю, что какой-либо из этих двух методов будет работать для иглы = [1 2 3 0 1];. - person Divakar; 08.03.2014
comment
Луис, дело не в том, что у "стрелки" ноль или нет. Использование любого ненулевого значения также не сработает. Настоящая проблема заключается в том, что из-за конкатенации он распространяется на следующую строку. Это обсуждается в моем коде. Хорошо, я думаю, вы внесли изменения, отлично! - person Divakar; 08.03.2014
comment
@Divakar Да, я думаю, что мы оба пришли к одному и тому же выводу :-) Наличие равных элементов в needle также было проблематичным с моим прежним подходом conv - person Luis Mendo; 08.03.2014
comment
Ага, это было.. что-то :) - person Divakar; 08.03.2014