配列要素のコピーを繰り返します：MATLABでのランレングスデコード

Question

「値」配列と「カウンター」配列を使用して、複数の値を配列に挿入しようとしています。たとえば、場合：

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

何らかの機能の出力が欲しいです

c=somefunction(a,b)

することが

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

A（1）がb（1）回数b（1）回数、a（2）がb（2）回数など...

Matlabにこれを行う組み込み関数はありますか？可能であれば、forループを使用しないようにしたいと思います。 「repmat（）」と「kron（）」のバリエーションを試してみました。

これは基本的にです Run-length encoding.

Answer 1

問題文

私たちは一連の値を持っています、 vals とrunlengths、 runlens:

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

各要素を繰り返す必要があります vals それぞれに対応する要素を runlens. 。したがって、最終出力は次のとおりです。

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

前向きアプローチ

Matlabで最も速いツールの1つはです cumsum 不規則なパターンで機能するベクトル化の問題に対処する場合に非常に便利です。記載されている問題では、不規則性にはさまざまな要素が付属しています runlens.

今、悪用する cumsum, 、ここで2つのことをする必要があります：の配列を初期化 zeros Zerosアレイの上に「キー」位置に「適切な」値を配置し、その後」cumsum「適用されます、私たちは繰り返される最終的な配列になります vals の runlens 時代。

ステップ： 上記の手順を番号にして、将来のアプローチに簡単な視点を与えましょう。

1）Zerosアレイの初期化：長さは何でなければなりませんか？繰り返しているので runlens 時代、ゼロアレイの長さはすべての合計でなければなりません runlens.

2）キー位置/インデックスを見つける：これで、これらのキー位置は、各要素がゼロアレイに沿っている場所になりました。 vals 繰り返し始めます。したがって、 runlens = [2,2,1,3], 、Zerosアレイにマッピングされた重要な位置は次のとおりです。

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

3）適切な値を見つける：使用する前にハンマーされる最後の爪 cumsum これらの重要な位置に「適切な」値を配置することです。今、私たちはやっているので cumsum その後すぐに、あなたがよく考えれば、あなたは differentiated のバージョン values と diff, 、 となることによって cumsum それらについて 私たちを持ち帰ります values. 。これらの区別された値は、 runlens 使用後の距離 cumsum それぞれがあります vals 要素が繰り返されます runlens 最終出力としての時間。

ソリューションコード

上記のすべての手順をステッチする実装は次のとおりです -

% 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)

前配置ハック

上記のコードがゼロとの事前配列を使用していることがわかるように。今、これによると より速い事前配列に関する文書化されていないMATLABブログ, 、 -

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

ラップアップ：関数コード

すべてを締めくくるために、このような段階的なデコードを実現するためのコンパクトな関数コードがあります -

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;

ベンチマーク

ベンチマークコード

次にリストされているのは、記載されているランタイムとスピードアップを比較するベンチマークコードです cumsum+diff この投稿でアプローチします 他の cumsum-only ベースのアプローチ の上 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')

の関連する関数コード 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;

ランタイムとスピードアッププロット

結論

提案されたアプローチは、私たちに顕著なスピードアップを与えているようです cumsum-only アプローチ、それはそのことです 3x!

なぜこれが新しいのか cumsum+diff 以前よりも優れたベースのアプローチ cumsum-only アプローチ？

まあ、理由の本質は、 cumsum-only 「累積」値をにマッピングする必要があるアプローチ vals. 。新しいで cumsum+diff ベースのアプローチ、私たちはやっています diff(vals) 代わりに、MATLABが処理のみです n のマッピングと比較して、要素（nはrunlengthsの数） sum(runLengths) の要素の数 cumsum-only アプローチとこの数値は何度もでなければなりません n したがって、この新しいアプローチで顕著なスピードアップ！

Answer 2

ベンチマーク

R2015Bの更新: repelem すべてのデータサイズで最速になりました。

---

テストされた関数：

1. Matlabの組み込み repelem R2015aで追加された関数
2. Gnovice's cumsum 解決 （rld_cumsum)
3. ディバカール cumsum+diff 解決 （rld_cumsum_diff)
4. Knedlsepp's accumarray 解決 （knedlsepp5cumsumaccumarray） から この郵便受け
5. 素朴なループベースの実装（naive_jit_test.m）ジャストインタイムコンパイラをテストします

の結果 test_rld.m R2015でb:

R2015を使用した古いタイミングプロットa ここ.

調査結果:

• repelem 常に最速で最速2倍です。
• rld_cumsum_diff 常により速いです rld_cumsum.
• repelem 小さなデータサイズで最速です（約300〜500の要素未満）
• rld_cumsum_diff よりも大幅に速くなります repelem 約5 000の要素
• repelem より遅くなる rld_cumsum 30 000〜300 000の要素のどこか
• rld_cumsum ほぼ同じパフォーマンスを持っています knedlsepp5cumsumaccumarray
• naive_jit_test.m ほぼ一定の速度があり、同等です rld_cumsum と knedlsepp5cumsumaccumarray サイズが小さい場合は、大きいサイズが少し速くなります

R2015を使用した古いレートプロットa ここ.

結論

使用する repelem 以下で約5 000要素と cumsum+diff 上記の解決策.

Answer 3

私が知っている組み込み関数はありませんが、ここに1つの解決策があります。

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

説明：

ゼロのベクトルは、最初に出力配列と同じ長さの作成されます（つまり、すべての複製の合計 b）。次に、1つが最初の要素に配置され、各値のシーケンスの開始が出力内にある場所を表す各後続要素が配置されます。ベクトルの累積合計 index その後、インデックスに使用できます a, 、各値を望ましい回数で複製します。

明確にするために、これはさまざまなベクトルがの値に対してどのように見えるかです a と b 質問で与えられます：

        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]

---

編集： 完全性のために、そこに は 別の代替手段を使用します arrayfun, 、しかし、これは最大10,000の要素を持つベクトルを備えた上記のソリューションよりも20〜100倍長く実行されるようです。

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];

Answer 4

最終的に（その後 R2015A）これを行うための組み込みおよび文書化された機能、 repelem. 。 2番目の引数がベクトルである場合、次の構文はここで関連しています。

W = repelem(V,N), 、ベクトル付き V およびベクトル N, 、ベクトルを作成します W ここで、要素 V(i) 繰り返されます N(i) 時代。

または、別の言い方をすれば、「の各要素 N 対応する要素を繰り返す回数を指定します V."

例：

>> 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

Answer 5

Matlabの組み込みのパフォーマンスの問題 repelem R2015Bの時点で修正されています。私は実行しました test_rld.m R2015BのChappJCの投稿からのプログラム repelem これで、他のアルゴリズムよりも速い係数2によって高速になりました。