matlab - 長さのベクトルに基づく MATLAB 繰り返し数

Question

次のことを行うベクトル化された方法はありますか? (例で示します):

input_lengths = [ 1 1 1 4       3     2   1 ]
result =        [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

結果がどのように得られるかを理解しやすいように、input_lengths を間隔を空けて配置しました。

結果のベクトルの長さはsum(lengths). result現在、次のループを使用して計算しています。

result = ones(1, sum(input_lengths ));
counter = 1;
for i = 1:length(input_lengths)
    start_index = counter;
    end_index = counter + input_lengths (i) - 1;

    result(start_index:end_index) = i;
    counter = end_index + 1;
end

編集：

arrayfun を使用してこれを行うこともできます (ただし、これは正確にはベクトル化された関数ではありません)。

cell_result = arrayfun(@(x) repmat(x, 1, input_lengths(x)), 1:length(input_lengths), 'UniformOutput', false);
cell_result : {[1], [2], [3], [4 4 4 4], [5 5 5], [6 6], [7]}

result = [cell_result{:}];
result : [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

Answer 1

完全にベクトル化されたバージョン:

selector=bsxfun(@le,[1:max(input_lengths)]',input_lengths);
V=repmat([1:size(selector,2)],size(selector,1),1);
result=V(selector);

欠点は、メモリ使用量が O(numel(input_lengths)*max(input_lengths)) であることです

Answer 2

すべてのソリューションのベンチマーク

前のベンチマークに従って、ここで提供されるすべてのソリューションをスクリプトにグループ化し、ベンチマークのために数時間実行します。私がこれを行ったのは、入力の長さをパラメーターとして使用して提案された各ソリューションのパフォーマンスを確認するのは良いことだと思うためです。私の意図は、前のソリューションの品質を下げることではありません。 JIT。さらに、すべての参加者がそれに同意しているようで、すべての回答で非常に優れた作業が行われたため、この素晴らしい投稿は結論の投稿に値します.

スクリプトのコードはここには掲載しません。これは非常に長く、非常に面白くありません。ベンチマークの手順は、一連の異なる長さの入力ベクトルに対して各ソリューションを実行することです: 10、20、50、100、200、500、1000、2000、5000、10000、20000、50000、100000、200000、500000、 1000000. 入力の長さごとに、ポアソンの法則に基づいてパラメーター 0.8 を使用してランダムな入力ベクトルを生成しました (大きな値を避けるため)。

input_lengths = round(-log(1-rand(1,ILen(i)))/poisson_alpha)+1;

最後に、入力長ごとに 100 回の実行で計算時間を平均します。

Matlab R2013b を使用してラップトップ コンピューター (コア I7) でスクリプトを実行しました。JIT が有効化されます。

そして、ここにプロットされた結果 (申し訳ありませんが、色付きの線) が両対数スケール (x 軸: 入力の長さ、y 軸: 秒単位の計算時間) で示されています。

つまり、Luis Mendo が明確な勝者です。おめでとう!

数値結果が必要な場合、および/またはそれらを再プロットしたい場合は、次のとおりです (表を 2 つの部分に切り取り、3 桁に近似して、より適切に表示します)。

N                   10          20          50          100         200         500         1e+03       2e+03
-------------------------------------------------------------------------------------------------------------
OP's for-loop       8.02e-05    0.000133    0.00029     0.00036     0.000581    0.00137     0.00248     0.00542 
OP's arrayfun       0.00072     0.00117     0.00255     0.00326     0.00514     0.0124      0.0222      0.047
Daniel              0.000132    0.000132    0.000148    0.000118    0.000126    0.000325    0.000397    0.000651
Divakar             0.00012     0.000114    0.000132    0.000106    0.000115    0.000292    0.000367    0.000641
David's for-loop    9.15e-05    0.000149    0.000322    0.00041     0.000654    0.00157     0.00275     0.00622
David's arrayfun    0.00052     0.000761    0.00152     0.00188     0.0029      0.00689     0.0122      0.0272
Luis Mendo          4.15e-05    4.37e-05    4.66e-05    3.49e-05    3.36e-05    4.37e-05    5.87e-05    0.000108
Bentoy13's cumsum   0.000104    0.000107    0.000111    7.9e-05     7.19e-05    8.69e-05    0.000102    0.000165
Bentoy13's sparse   8.9e-05     8.82e-05    9.23e-05    6.78e-05    6.44e-05    8.61e-05    0.000114    0.0002
Luis Mendo's optim. 3.99e-05    3.96e-05    4.08e-05    4.3e-05     4.61e-05    5.86e-05    7.66e-05    0.000111

N                   5e+03       1e+04       2e+04       5e+04       1e+05       2e+05       5e+05       1e+06
-------------------------------------------------------------------------------------------------------------
OP's for-loop       0.0138      0.0278      0.0588      0.16        0.264       0.525       1.35        2.73
OP's arrayfun       0.118       0.239       0.533       1.46        2.42        4.83        12.2        24.8
Daniel              0.00105     0.0021      0.00461     0.0138      0.0242      0.0504      0.126       0.264
Divakar             0.00127     0.00284     0.00655     0.0203      0.0335      0.0684      0.185       0.396
David's for-loop    0.015       0.0286      0.065       0.175       0.3         0.605       1.56        3.16
David's arrayfun    0.0668      0.129       0.299       0.803       1.33        2.64        6.76        13.6
Luis Mendo          0.000236    0.000446    0.000863    0.00221     0.0049      0.0118      0.0299      0.0637
Bentoy13's cumsum   0.000318    0.000638    0.00107     0.00261     0.00498     0.0114      0.0283      0.0526
Bentoy13's sparse   0.000414    0.000774    0.00148     0.00451     0.00814     0.0191      0.0441      0.0877
Luis Mendo's optim. 0.000224    0.000413    0.000754    0.00207     0.00353     0.00832     0.0216      0.0441

わかりました、別のソリューションをリストに追加しました ... Luis Mendo のこれまでで最高のソリューションを最適化することをやめることはできませんでした。これは Luis Mendo のバリエーションにすぎません。後で説明します。

明らかに、使用するソリューションarrayfunは非常に時間がかかります。明示的な for ループを使用するソリューションは高速ですが、他のソリューションと比較するとまだ遅いです。そうです、ベクトル化は依然として Matlab スクリプトを最適化するための主要なオプションです。

特に入力長が 100 ～ 10000 の場合、最速のソリューションの計算時間に大きなばらつきがあることがわかったので、より正確にベンチマークすることにしました。そのため、最も遅いものを分けて (申し訳ありません)、はるかに高速に実行される他の 6 つのソリューションのベンチマークをやり直しました。この縮小された解のリストに対する 2 番目のベンチマークは、平均して 1000 回以上実行したことを除いて同じです。

(ここに表はありません。本当に必要でない限り、以前とまったく同じ数字です)

bsxfun指摘されたように、 @times を使用すると を使用するよりも遅いように見えるため、Daniel による解決策は Divakar による解決策よりも少し高速ですrepmat。それでも、それらは for ループ ソリューションよりも 10 倍高速です。明らかに、Matlab でのベクトル化は良いことです。

Bentoy13 と Luis Mendo のソリューションは非常に近いものです。最初のものはより多くの命令を使用しますが、2 番目のものは 1 を に連結するときに追加の割り当てを使用しcumsum(input_lengths(1:end-1))ます。そのため、余分な割り当てがないため、Bentoy13 のソリューションは大きな入力長 (5.10^5 を超える) で少し高速になる傾向があることがわかります。この考慮事項から、余分な割り当てがない最適化されたソリューションを作成しました。これがコードです（Luis Mendoは、必要に応じてこれを回答に入れることができます:)）：

result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);

改善のためのコメントは大歓迎です。

Answer 3

何よりもコメントですが、いくつかのテストを行いました。forループと を試しました。ループとバージョンarrayfunをテストしました。あなたのループは最速でした。これは、単純であり、JIT コンパイルが最大限の最適化を行うことができるためだと思います。私はMatlabを使用していますが、オクターブは異なる場合があります。forarrayfunfor

そしてタイミング：

Solution:     With JIT   Without JIT  
Sam for       0.74       1.22    
Sam arrayfun  2.85       2.85    
My for        0.62       2.57    
My arrayfun   1.27       3.81    
Divakar       0.26       0.28    
Bentoy        0.07       0.06    
Daniel        0.15       0.16
Luis Mendo    0.07       0.06

したがって、Bentoy のコードは非常に高速で、Luis Mendo のコードもほぼ同じ速度です。そして、私はJITに頼りすぎています！

---

そして私の試みのコード

clc,clear
input_lengths = randi(20,[1 10000]);

% My for loop
tic()
C=cumsum(input_lengths);
D=diff(C);
results=zeros(1,C(end));
results(1,1:C(1))=1;
for i=2:length(input_lengths)
    results(1,C(i-1)+1:C(i))=i*ones(1,D(i-1));
end
toc()

tic()
A=arrayfun(@(i) i*ones(1,input_lengths(i)),1:length(input_lengths),'UniformOutput',false);
R=[A{:}];
toc()

Answer 4

これは、@Daniel's answerのわずかな変形です。このソリューションの核心は、そのソリューションに基づいています。これは を回避repmatするので、おそらくもう少し「ベクトル化」されています。ここにコードがあります -

selector=bsxfun(@le,[1:max(input_lengths)]',input_lengths); %//'
V = bsxfun(@times,selector,1:numel(input_lengths)); 
result = V(V~=0)

すべての絶望的なワンライナー検索の人々のために-

result = nonzeros(bsxfun(@times,bsxfun(@le,[1:max(input_lengths)]',input_lengths),1:numel(input_lengths)))

Answer 5

私はエレガントな解決策を探していますが、 David の解決策は良いスタートだと思います。私が念頭に置いているのは、前の要素から追加する場所にインデックスを生成できるということです。

そのためcumsumに、入力ベクトルの を計算すると、次のようになります。

cumsum(input_lengths)
ans = 1     2     3     7    10    12    13

これは、同じ数のシーケンスの末尾のインデックスです。これは私たちが望んでいるものではないので、ベクトルを 2 回反転して開始点を取得します。

fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)))
ans = 1     2     3     4     8    11    13

これがトリックです。ベクトルを反転し、それを合計して反転したベクトルの両端を取得してから、元に戻します。ただし、反転したベクトルに cumsum が適用されるため、出力ベクトルの全長からベクトルを差し引く必要があります (インデックスは 1 から始まるため +1)。

これが完了したら、それは非常に簡単です。計算されたインデックスに 1 を置き、それ以外の場所に 0 を置き、それを合計するだけです。

idx_begs = fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)));
result = zeros(1,sum(input_lengths));
result(idx_begs) = 1;
result = cumsum(result);

編集

まず、 Luis Mendo's solutionを見てください。これは私のものに非常に近いですが、よりシンプルで少し高速です (非常に近いものでも編集しません)。現時点では、これが最速のソリューションだと思います。

次に、他のソリューションを見ながら、最初のソリューションや他のワンライナーとは少し異なる別のワンライナーを作成しました。わかりました、これはあまり読みにくいので、息を吸ってください：

result = cumsum( full(sparse(cumsum([1,input_lengths(1:end-1)]), ...
ones(1,length(input_lengths)), 1, sum(input_lengths),1)) );

2本線で切りました。では、説明しましょう。

同様の部分は、現在の要素の値をインクリメントするインデックスの配列を構築することです。そのために、ルイス・メンドのソリューションを使用します。解ベクトルを 1 行で作成するために、ここでは、それが実際にはバイナリ ベクトルのスパース表現であるという事実を使用します。これは最後に累積します。このスパース ベクトルは、計算されたインデックス ベクトルを x 位置として、1 のベクトルを y 位置として、1 をこれらの位置に配置する値として使用して構築されます。4 番目の引数は、ベクトルの合計サイズを正確に指定するために指定されます (の最後の要素がinput_lengths1 でない場合に重要です)。次に、このスパース ベクトルの完全な表現を取得し (それ以外の場合、結果は空の要素のないスパース ベクトルになります)、cumsum を実行できます。

この問題に別の解決策を与える以外に、この解決策を使用することはできません。ベンチマークは、メモリ負荷が重いため、元のソリューションよりも遅いことを示している可能性があります。