7
votes

Indexer un vecteur dans un plus grand dans MATLAB

J'essaie de trouver la position d'index du plus petit vecteur dans un plus grand.

J'ai déjà résolu ce problème en utilisant strfind et bind2dec , mais je ne veux pas utiliser strfind , je ne veux pas du tout convertir en chaîne ou en déciamls.

Étant donné le vecteur plus long

result=[15,16,17,18,19,20];

Je veux trouver l'index du plus petit vecteur b dans un

b=[1,1,1,0,0,0];

Je m'attendrais à trouver comme résultat

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];

Merci

matlab

1 commentaires

Quelle est votre solution avec strfind ? Savez-vous que vous pouvez simplement utiliser strfind (a, b) sans convertir en chaînes (mais ce n'est pas documenté)?

4 Réponses :

3
votes

Doit-il être efficace en termes de calcul?

Une solution pas très efficace mais courte serait la suivante:

a = round(rand(1e6,1));
b = round(rand(10,1));

tic;where1 = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));toc;
tic;where2 = find_sequence(a,b);toc;


>> test_find_sequence
Elapsed time is 4.419223 seconds.
Elapsed time is 0.042969 seconds.

... vous donne 15. Votre résultat serait le vecteur where:where+length(b)-1.

edit : je l'ai essayé et je me tiens corrigée. Voici une version avec des boucles:

function where = find_sequence(a,b)

na = 0;
where = [];
while na < length(a)-length(b)
    c = false;
    for nb = 1:length(b)
        if a(na+nb)~=b(nb)
            na = na + 1;  % + nb
            c = true;                        
            break
        end

    end
    if ~c
        where = [where,na+1];
        na = na + 1;
    end   
end

Malgré ses boucles et leur mauvaise réputation dans Matlab, c'est beaucoup plus rapide:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];;
b=[1,1,1,0,0,0];
where = find(arrayfun(@(n) all(a(n+1:n+length(b))==b),0:length(a)-length(b)));

3 commentaires

Oui, l'efficacité est importante. Aussi je demande parce que strfind et bin2dec nécessitent beaucoup de mémoire pour fonctionner

Essayez celui-ci et voyez comment il se comporte pour vous.Il est inefficace pour les vecteurs plus longs b car il comparera toujours le vecteur entier alors que l'on pourrait s'arrêter dès qu'il y a une discordance. Pour résoudre ce problème, il faudrait utiliser des boucles qui ne sont pas non plus les plus efficaces de Matlab. Mon instinct est que tant que b est très court par rapport à a , cela devrait fonctionner.

D'accord, après les tests, j'ai trouvé que l'utilisation des boucles est considérablement plus rapide. Je viens de voir après avoir posté ma mise à jour que barbsan a déjà suggéré une version très similaire avant moi.

4
votes

Solution avec pour boucles:

a=[1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];
b=[1,1,1,0,0,0];
c = [];
b_len = length(b)
maxind0 = length(a) - b_len + 1 %no need to search higher indexes 

for i=1:maxind0
  found = 0;
  for j=1:b_len
    if a(i+j-1) == b(j)
      found = found + 1;
    else
      break;
    end
  end

  if found == b_len  % if sequence is found fill c with indexes
    for j=1:b_len
      c(j)= i+j-1;
    end

    break
  end
end

c %display c

2 commentaires

et si new_a = a '? (je transpose a). Aussi b est transposable

si c'est toujours un vecteur, vous pouvez remplacer size (v, 2) par length (v)

7
votes

Voici une solution utilisant la convolution 1D. Il peut trouver plusieurs correspondances donc start contient les indices de début des sous-vecteurs:

f = flip(b);

idx = conv(a,f,'same')==sum(b) & conv(~a,~f,'same')==sum(~b);

start = find(idx)-ceil(length(b)/2)+1;

result = start(1):start(1)+length(b)-1;

0 commentaires

2
votes

Une méthode plus soignée utilisant pour ressemblerait à ceci, il n'y a pas besoin d'une boucle de vérification interne car nous pouvons vectoriser cela avec all ...

idx = [15,16,17,18,19,20]

Output:

a = [1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,1,1];
b = [1,1,1,0,0,0];

idx = NaN( size(b) ); % Output NaNs if not found
nb = numel( b );      % Store this for re-use

for ii = 1:numel(a)-nb+1
    if all( a(ii:ii+nb-1) == b )
        % If matched, update the index and exit the loop
        idx = ii:ii+nb-1;
        break
    end
end

Remarque, je trouve cela un peu plus facile à lire que certaines des solutions imbriquées, mais ce n'est pas forcément plus rapide, depuis la comparaison est fait sur tous les éléments de b à chaque fois.

0 commentaires