5

matlabには、ペアごとの距離を計算するpdist関数が組み込まれていることを知っています。ただし、私のマトリックスは非常に大きいため、60000 x 300 であり、matlab のメモリが不足しています。

この質問は、 Matlab ユークリッド ペアワイズ 2 乗距離関数のフォロー アップです。

この計算の非効率性に対する回避策はありますか。ペアごとの距離計算を手動でコーディングしてみましたが、通常は実行に丸 1 日かかります (6 ～ 7 時間の場合もあります)。

どんな助けでも大歓迎です！

4

3 に答える 3

6

まあ、私は遊びに抵抗できませんでした。単精度と倍精度のペアワイズ ユークリッド距離を実装するという名前の Matlab mex C ファイルを作成しました。pdistc私のマシンでは、Matlab R2012b および R2015a を使用しており、大きな入力 (たとえば、60,000 x 300) の場合よりも 20 ～ 25% 高速ですpdist(および基礎となるヘルパー関数)。pdistmex

指摘されているように、この問題は基本的にメモリによって制限されており、多くのメモリを要求しています。私の mex C コードは、出力に必要な量を超える最小限のメモリを使用します。そのメモリ使用量を のメモリ使用量と比較するとpdist、2 つが実質的に同じであるように見えます。つまり、pdist余分なメモリを大量に使用していません。メモリの問題は、呼び出す前にメモリを使い果たしている可能性があります (大きな配列を削除するためにpdist使用できますか?)、または単に小さなハードウェアで大きな計算上の問題を解決しようとしているからです。clear

したがって、私のpdistc関数はメモリ全体を節約できない可能性がありますが、組み込みの別の機能を使用できる可能性があります。全体的なペアワイズ距離ベクトルのチャンクを計算できます。このようなもの：

m = 6e3;
n = 3e2;
X = rand(m,n);
sz = m*(m-1)/2;

for i = 1:m:sz-m
    D = pdistc(X', i, i+m); % mex C function, X is transposed relative to pdist
    ...                     % Process chunk of pairwise distances
end

これはかなり遅く (10 倍程度)、私の C コードのこの部分は最適化されていませんが、配列全体を一度に必要としないと仮定すると、メモリの使用量ははるかに少なくなります。pdist(または) を使用して、すべてではなくpdistcサブセットを直接渡したループを作成することで、同じことをはるかに効率的に実行できることに注意してください。X

64 ビットの Intel Mac を使用している場合は、.mexmaci64バイナリが含まれているのでコンパイルする必要はありませんが、それ以外の場合は、マシンのコードをコンパイルする方法を理解する必要があります。私はそれを手伝うことはできません。コンパイルできない可能性や、コードを自分で編集して解決する必要がある互換性の問題が発生する可能性があります。バグがあり、コードが Matlab をクラッシュさせる可能性もあります。pdistまた、マシン イプシロン ( ) の範囲内で 2 つの間の違いに関連して、わずかに異なる出力が得られる場合があることに注意してくださいeps。pdist大規模な入力やその他の数値の問題のオーバーフローを回避するために、派手なことをする場合としない場合がありますが、私のコードはそうではないことに注意してください。

さらに、単純な純粋な Matlab 実装を作成しました。これは mex コードよりも大幅に低速ですが、単純な実装や にあるコードよりも高速ですpdist。

すべてのファイルはここにあります。ZIP アーカイブには、すべてのファイルが含まれています。BSDライセンスです。自由に最適化してください (C コードで BLAS 呼び出しと OpenMP を試してみましたが、うまくいきませんでした。ポインター マジックまたは GPU/OpenCL でさらに高速化できる可能性があります)。あなたや他の誰かに役立つことを願っています。

于 2013-07-23T00:20:37.280 に答える
0

コンピューターは無限に大きくも、無限に高速でもありません。人々は、大量のメモリと高速な CPU を持っていると考えているため、ますます大きな問題を作成し、最終的には、なぜ問題の実行速度が遅いのか疑問に思います。実際、これは計算の非効率性ではありません。それは過負荷のCPUです。

Oli がコメントで指摘しているように、距離行列の上半分または下半分のみを計算すると仮定しても、2e9 のような値を計算する必要があります。(6e4^2/2 は約 2e9 です。) これを格納するには、配列のコピーが 1 つだけメモリに作成されると仮定すると、約 16 ギガバイトの RAM が必要になります。コードがずさんな場合、簡単に 2 倍または 3 倍になる可能性があります。仮想メモリに入るとすぐに、物事はずっと遅くなります。

大きな問題を速く実行したいだけでは十分ではありません。あなたを本当に助けるために、利用可能なRAMの量を知る必要があります. これは仮想メモリの問題ですか? 必要なすべての RAM を処理できる CPU で 64 ビット MATLAB を使用していますか?

于 2013-07-21T22:13:02.970 に答える