「値」配列と「カウンター」配列を使用して、配列に複数の値を挿入しようとしています。たとえば、次の場合:
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) 回繰り返され、a(2) は b(2) 回繰り返されます...
これを行う MATLAB の組み込み関数はありますか? できれば for ループの使用は避けたいと思います。「repmat()」と「kron()」のバリエーションを試しましたが、役に立ちませんでした。
これは基本的にRun-length encodingです。
値の配列valsとランレングスがあり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) ゼロ配列の初期化: 長さは? 時間を繰り返しているため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よく考えてみると、withのdifferentiatedバージョンが必要になるでしょう。これらの微分された値は、距離で区切られた場所でゼロ配列に配置されるため、使用後、最終出力として各要素が何度も繰り返されます。valuesdiffcumsumvaluesrunlenscumsumvalsrunlens
ソリューション コード
上記のすべての手順をつなぎ合わせた実装は次のとおりです-
% 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)
事前割り当てハック
上にリストされたコードは、ゼロによる事前割り当てを使用していることがわかります。現在、高速な事前割り当てに関するこのUNDOCUMENTED 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提案されたアプローチは、約3 倍のアプローチよりも顕著なスピードアップを私たちに与えているようです!
この新しいcumsum+diffベースのアプローチが以前のアプローチよりも優れているのはなぜcumsum-onlyですか?
その理由の本質は、cumsum-only「累積された」値を にマッピングする必要があるアプローチの最終ステップにありますvals。新しいcumsum+diffベースのアプローチでは、アプローチの要素数のマッピングと比較して、MATLAB が要素 (n は runLengths の数)diff(vals)のみを処理する代わりに、この数は何倍も多くなければならないため、この新しいアプローチによる顕著なスピードアップ！nsum(runLengths)cumsum-onlyn
ベンチマーク
R2015b 用に更新:repelemすべてのデータ サイズで最速になりました。
テスト済みの機能:
repelemR2015aで追加されたMATLABの組み込み関数cumsumソリューション ( rld_cumsum)cumsum+diffソリューション ( rld_cumsum_diff)accumarrayソリューション ( knedlsepp5cumsumaccumarray) from this postnaive_jit_test.mジャストインタイム コンパイラをテストするための単純なループベースの実装 ( )test_rld.mR2015 bの結果:
R2015 a hereを使用した古いタイミング プロット。
所見：
repelem常に約 2 倍速くなります。rld_cumsum_diffより一貫して高速ですrld_cumsum。repelem小さなデータ サイズ (約 300 ～ 500 要素未満) の場合は最速です。rld_cumsum_diffrepelem約 5000 要素よりも大幅に高速化repelemrld_cumsum30 000 から 300 000 要素の間のどこかよりも遅くなりますrld_cumsum～とほぼ同じ性能を持つknedlsepp5cumsumaccumarraynaive_jit_test.mrld_cumsum速度はほぼ一定で、サイズが小さい場合と同等で、knedlsepp5cumsumaccumarrayサイズが大きい場合は少し速くなります
R2015 a hereを使用した古いレート プロット。
結論
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)、 vectorVおよび vectorを使用して、要素が何度も繰り返されるNベクトルを作成します。WV(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