copies répétées des éléments du tableau: décodage de longueur de MATLAB

Question

Je suis en train d'insérer plusieurs valeurs dans un tableau en utilisant un tableau « valeurs » et un tableau « contre ». Par exemple, si:

a=[1,3,2,5]
b=[2,2,1,3]

Je veux la sortie d'une fonction

c=somefunction(a,b)

être

c=[1,1,3,3,2,5,5,5]

Si un (1) recurs b (1) nombre de fois, un (2) se reproduit b (2) fois, etc ...

Y at-il une fonction intégrée dans MATLAB qui fait cela? Je voudrais éviter d'utiliser une boucle si possible. J'ai essayé des variations de 'repmat ()' et 'kron () sans résultat.

Ceci est essentiellement Run-length encoding .

Answer 1

Déclaration de problème

Nous avons un tableau de valeurs, vals et longueurs de plage, runlens:

vals     = [1,3,2,5]
runlens  = [2,2,1,3]

Nous avions besoin de répéter chaque élément vals fois chaque élément correspondant dans runlens. Ainsi, le résultat final serait:

output = [1,1,3,3,2,5,5,5]

Approche prospective

L'un des outils les plus rapides avec Matlab est cumsum et est très utile pour traiter les problèmes de vectorisation qui travaillent sur des motifs irréguliers. Dans le problème posé, l'irrégularité est livré avec les différents éléments runlens.

Maintenant, pour exploiter cumsum, nous devons faire deux choses: Initialiser un tableau de zeros et placer les valeurs « appropriées » à des positions « clés » sur le tableau de zéros, de sorte qu'après « cumsum » est appliqué, nous finirions avec un tableau final de vals répétées des temps de runlens.

Étapes: numéro Let mentionné ci-dessus des mesures pour donner à l'approche prospective d'une perspective plus facile:

1) Initialiser tableau zéros: Quelle doit être la longueur? Puisque nous réitérons les temps de runlens, la longueur du tableau de zéros doit être la somme de tous runlens.

2) Trouver des positions clés / indices: Maintenant, ces positions clés sont des endroits le long du réseau de zéros où chaque élément de vals commencent à se répéter. Ainsi, pour runlens = [2,2,1,3], les positions clés mises en correspondance avec le tableau de zéros serait:

[X 0 X 0 X X 0 0] % where X's are those key positions.

3) Trouvez des valeurs appropriées: Le dernier clou à marteler avant d'utiliser cumsum serait de mettre les valeurs « appropriées » dans ces postes clés. Maintenant, puisque nous rendrions cumsum peu après, si vous pensez bien, vous auriez besoin d'une version differentiated de values avec diff , de sorte que ceux cumsum serait ramener notre values . Étant donné que ces valeurs différenciées seraient placées sur un tableau de zéros à des endroits séparés par des distances de runlens, après avoir utilisé cumsum nous aurions chaque élément vals temps de runlens répétées que la sortie finale.

Code de solution

Voici la mise en œuvre recoudre toutes les étapes mentionnées ci-dessus -

% Calculate cumsumed values of runLengths. 
% We would need this to initialize zeros array and find key positions later on.
clens = cumsum(runlens)

% Initalize zeros array
array = zeros(1,(clens(end)))

% Find key positions/indices
key_pos = [1 clens(1:end-1)+1]

% Find appropriate values
app_vals = diff([0 vals])

% Map app_values at key_pos on array
array(pos) = app_vals

% cumsum array for final output
output = cumsum(array)

préaffectation Hack

Comme on peut voir que le code de la liste ci-dessus utilise préaffectation avec des zéros. Maintenant, selon cette Blog SANS PAPIERS sur MATLAB® pré-allocation plus rapide , on peut obtenir beaucoup plus rapide avant -allocation avec -

array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))

Emballage jusqu'à: Code Fonction

Pour conclure tout, nous aurions un code de fonction compact pour réaliser ce décodage RLL comme si -

function out = rle_cumsum_diff(vals,runlens)
clens = cumsum(runlens);
idx(clens(end))=0;
idx([1 clens(1:end-1)+1]) = diff([0 vals]);
out = cumsum(idx);
return;

Analyse comparative

Code de Benchmarking

Listed suivant est le code d'étalonnage pour comparer les runtimes et speedups pour l'approche cumsum+diff indiqué dans ce poste sur l'approche fondée sur Autre cumsum-only sur MATLAB 2014B -

datasizes = [reshape(linspace(10,70,4).'*10.^(0:4),1,[]) 10^6 2*10^6]; %
fcns = {'rld_cumsum','rld_cumsum_diff'}; % approaches to be benchmarked

for k1 = 1:numel(datasizes)
    n = datasizes(k1); % Create random inputs
    vals = randi(200,1,n);
    runs = [5000 randi(200,1,n-1)]; % 5000 acts as an aberration
    for k2 = 1:numel(fcns) % Time approaches  
        tsec(k2,k1) = timeit(@() feval(fcns{k2}, vals,runs), 1);
    end
end

figure,      % Plot runtimes
loglog(datasizes,tsec(1,:),'-bo'), hold on
loglog(datasizes,tsec(2,:),'-k+')
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize ->'), ylabel('Runtimes (s)')
legend(upper(strrep(fcns,'_',' '))),title('Runtime Plot')

figure,      % Plot speedups
semilogx(datasizes,tsec(1,:)./tsec(2,:),'-rx')        
set(gca,'ygrid','on'), xlabel('Datasize ->')
legend('Speedup(x) with cumsum+diff over cumsum-only'),title('Speedup Plot')

code de fonction associée pour rld_cumsum.m:

function out = rld_cumsum(vals,runlens)
index = zeros(1,sum(runlens));
index([1 cumsum(runlens(1:end-1))+1]) = 1;
out = vals(cumsum(index));
return;

Runtime et SpeedUp Parcelles

Conclusions

L'approche proposée semble nous donner une accélération notable sur l'approche cumsum-only, qui est sur le 3x

Pourquoi cette nouvelle approche basée cumsum+diff mieux que l'approche cumsum-only précédente?

Eh bien, l'essence de la raison est à l'étape finale de l'approche cumsum-only qui doit cartographier les valeurs « cumsumed » dans vals. Dans la nouvelle approche basée sur les cumsum+diff, nous faisons diff(vals) au lieu pour lequel Matlab traite uniquement des éléments de n (où n est le nombre de longueurs de plage) par rapport à la cartographie du nombre de sum(runLengths) d'éléments pour l'approche cumsum-only et ce nombre doit être plusieurs fois plus de n et donc l'accélération notable avec cette nouvelle approche!

Answer 2

Repères

Mise à jour pour R2015b :. repelem maintenant le plus rapide pour toutes les tailles de données

---

Fonctions testées:

1. Matlab intégré dans repelem fonction qui a été ajoutée dans R2015a
2. solution cumsum de gnovice ( rld_cumsum )
3. cumsum de Divakar + solution diff ( rld_cumsum_diff )
4. solution accumarray de la knedlsepp ( knedlsepp5cumsumaccumarray ) ce poste
5. la mise en œuvre à base de boucles Naive ( naive_jit_test.m ) pour tester la juste à temps compilateur

Résultats de test_rld.m sur R2015 b :

Ancien terrain calendrier utilisant R2015 .

Résultats :

• repelem est toujours le plus rapide d'environ un facteur 2.
• rld_cumsum_diff est toujours plus rapide que rld_cumsum.
• repelem est le plus rapide pour les petites tailles de données (moins d'environ 300-500 éléments)
• rld_cumsum_diff devient nettement plus rapide que repelem environ 5 000 éléments
• repelem devient plus lente que rld_cumsum quelque part entre 30 000 et 300 000 éléments
• rld_cumsum a à peu près les mêmes performances que knedlsepp5cumsumaccumarray
• naive_jit_test.m a presque vitesse constante et à égalité avec rld_cumsum et knedlsepp5cumsumaccumarray pour les petites tailles, un peu plus rapide pour les grandes tailles

parcelle Ancien taux en utilisant R2015 .

Conclusion

Utilisez repelem en dessous d'environ 5 000 éléments et la solution de cumsum + diff ci-dessus .

Answer 3

Il n'y a pas fonction intégrée que je connaisse, mais voici une solution:

index = zeros(1,sum(b));
index([1 cumsum(b(1:end-1))+1]) = 1;
c = a(cumsum(index));

Explication:

Un vecteur de zéros est créé de la même longueur que le réseau de sortie (à savoir la somme de toutes les réplications en b). Les sont ensuite placés dans le premier élément et chaque élément ultérieurs correspondant lorsque le début d'une nouvelle séquence de valeurs sera dans la sortie. La somme cumulative du vecteur index peut ensuite être utilisé pour indexer dans a, reproduisant chaque valeur du nombre de fois souhaité.

Par souci de clarté, c'est ce que les différents vecteurs ressemblent pour les valeurs de a et b dans la question:

        index = [1 0 1 0 1 1 0 0]
cumsum(index) = [1 1 2 2 3 4 4 4]
            c = [1 1 3 3 2 5 5 5]

---

EDIT: Par souci d'exhaustivité, il est une autre alternative en utilisant

Il est enfin (à partir de R2015a ) une fonction intégrée et documenté pour ce faire, repelem . La syntaxe suivante, où le second argument est un vecteur, est pertinent en l'espèce:

  

W = repelem(V,N), avec le vecteur et le vecteur V N, crée un vecteur W où V(i) élément est répété de fois N(i).

Ou en d'autres termes, « Chaque élément de N indique le nombre de fois pour répéter l'élément correspondant de V. »

Exemple:

>> a=[1,3,2,5]
a =
     1     3     2     5
>> b=[2,2,1,3]
b =
     2     2     1     3
>> repelem(a,b)
ans =
     1     1     3     3     2     5     5     5

Les problèmes de performance dans le repelem intégré de Matlab ont été fixés au R2015b. J'ai couru le programme test_rld.m du poste de chappjc dans R2015b et repelem est maintenant plus rapide que d'autres algorithmes d'un facteur 2:

Answer 4

Answer 5

Answer 6

Answer 7

Answer 8

Il est enfin (à partir de R2015a ) une fonction intégrée et documenté pour ce faire,

Answer 9

Les problèmes de performance dans le repelem intégré de Matlab ont été fixés au R2015b. J'ai couru le programme test_rld.m du poste de chappjc dans R2015b et repelem est maintenant plus rapide que d'autres algorithmes d'un facteur 2: