配列要素のコピーを繰り返します:MATLABでのランレングスデコード
-
21-09-2019 - |
質問
「値」配列と「カウンター」配列を使用して、複数の値を配列に挿入しようとしています。たとえば、場合:
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
.
解決
問題文
私たちは一連の値を持っています、 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
したがって、この新しいアプローチで顕著なスピードアップ!
他のヒント
ベンチマーク
R2015Bの更新: repelem
すべてのデータサイズで最速になりました。
テストされた関数:
- Matlabの組み込み
repelem
R2015aで追加された関数 - Gnovice's
cumsum
解決 (rld_cumsum
) - ディバカール
cumsum
+diff
解決 (rld_cumsum_diff
) - Knedlsepp's
accumarray
解決 (knedlsepp5cumsumaccumarray
) から この郵便受け - 素朴なループベースの実装(
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
上記の解決策
私が知っている組み込み関数はありませんが、ここに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{:}];
最終的に(その後 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
Matlabの組み込みのパフォーマンスの問題 repelem
R2015Bの時点で修正されています。私は実行しました test_rld.m
R2015BのChappJCの投稿からのプログラム repelem
これで、他のアルゴリズムよりも速い係数2によって高速になりました。