非常に大きな行列を含むMatlabアルゴリズムの最適化/ベクトル化

Question

Matlabで最適化問題があります。私は、入力として、以下の3つのベクトルを取得すると仮定：サイズ(1 x N)（信号振幅の時系列）サイズ(1 x N)の

F（信号の瞬時周波数の時系列）サイズの

fxの

• A今

を(M x 1)（私は上で上記を一致させたい周波数軸）、Fの要素かもしれません（時間の99％、彼らはしません）必ずfxの項目と正確に一致します。そのため、最も近い頻度に一致させる必要があります。

ここにキャッチがあります。私たちは大きなデータについて話しています。 Nは、簡単に200万人に達することができ、これは数百人の被験者に対して100回実行されなければならない。私の2つの懸念：

1. 時間（主要な関心事）
2. メモリ（生産は+ 16ギガバイトのメモリを搭載したマシン上で実行されますが、開発はメモリの唯一の8ギガバイトでマシン上にある）

Iこれらの2つのワーキングソリューションがあります。以下のために、N=2604000とM=201：（forループ）

方法1

forループ単純

。メモリはまったく問題ありませんが、時間がかかります。最も簡単な実装。

tic; 
I = zeros(M,N); 
for i = 1:N 
    [~,f] = min(abs(fx-F(i))); 
    I(f,i) = A(i).^2; 
end 
toc; 

再生時間：18.082秒。

方法2（ベクトル）

アイデアは、IDを取得するために、各瞬時周波数と周波数軸と一致することです。

   F 
     [ 0.9 0.2 2.3 1.4 ] N 
    [ 0 ][ 0 1 0 0 ] 
fx [ 1 ][ 1 0 0 1 ] 
    [ 2 ][ 0 0 1 0 ] 
    M 

そして、各列にその時の振幅を掛けます。

tic; 
m_Ff = repmat(F,M,1); 
m_fF = repmat(fx,1,N); 
[~,idx] = min(abs(m_Ff - m_fF)); clearvars m_Ff m_fF; 
m_if = repmat(idx,M,1);   clearvars idx; 
m_fi = repmat((1:M)',1,N); 
I = double(m_if==m_fi);   clearvars m_if m_fi; 
I = bsxfun(@times,I,A); 
toc; 

再生時間：64.223秒。これは私には驚くべきことですが、おそらく膨大な可変サイズと制限されたメモリが変数をファイルとして保存するためです。私はSSDを持っています。

私が利用していない唯一のことは、マトリックスが多くのゼロ要素を持つことです。私は疎な行列を調べてみる。

振幅と周波数の両方で少なくともsingleの精度が必要ですが、実際には、doubleからsingleに変換するには多くの時間がかかります。

改善の方法についてのご意見はありますか？

UPDATE提案のよう

、私は今ダウン組み合わせ2.53秒の時間にしています。これは、fxが単調に増加し、偶数間隔（常に0から始まる）であるという事実を利用しています。ここでは、コードは次のとおり

tic; df = mode(diff(fx)); toc;  % Find fx step size 
tic; idx = round(F./df+1); doc;  % Convert to bin ids 
tic; I = zeros(M,N); toc;   % Pre-allocate output 
tic; lin_idx = idx + (0:N-1)*M; toc; % Find indices to insert at 
tic; I(lin_idx) = A.^2; toc;   % Insert 

タイミング出力は以下の通りである：

Elapsed time is 0.000935 seconds. 
Elapsed time is 0.021878 seconds. 
Elapsed time is 0.175729 seconds. 
Elapsed time is 0.018815 seconds. 
Elapsed time is 2.294869 seconds. 

したがって最も時間のかかるステップは現在、非常に最終的なものです。これに関するアドバイスは大歓迎です。 @Peterと@Divakarに感謝します。

UPDATE 2（溶液）

Wuhuu。 sparse(i,j,k)を使用すると、実際に結果が改善されます。

タイミングに

tic; df = fx(2)-fx(1); toc; 
tic; idx = round(F./df+1); toc; 
tic; I = sparse(idx,1:N,A.^2); toc; 

：ここ

Elapsed time is 0.000006 seconds. 
Elapsed time is 0.016213 seconds. 
Elapsed time is 0.114768 seconds. 

Answer 1

はbsxfunに基づいて一つのアプローチだ -

abs_diff = abs(bsxfun(@minus,fx,F)); 
[~,idx] = min(abs_diff,[],1); 

IOut = zeros(M,N); 
lin_idx = idx + [0:N-1]*M; 
IOut(lin_idx) = A.^2; 

Answer 2

は、私は完全にFとFXの関係を以下ではないんだけど、それはfxかもしれないように聞こえます周波数のビンのセットであり、各入力Fに適切なビンを見つける必要があります。

これを最適化するかどうかは、fxの特性によって決まります。

fxが単調で均等に配置されている場合は、まったく検索する必要はありません。スケールを整列させるためにFをスケーリングしてオフセットするだけで、ビン番号を得るために丸めます。

fxが単調（ソート済み）で、均等に配置されていない場合は、histcが必要です。これにより、fxのエッジを効率的に検索し、正しいビンを見つけることができます。おそらく、最初にfを変換して、中心ではなくビンの端を含むようにする必要があります。

もしどちらでもなければ、ソート順を保存し、正しい「ビン」を見つけたら元の注文を復元するために、少なくともソートする必要があります。