1

私のアプリケーションは、密行列に対して多数の行列演算 (加算/乗算など) を実行します。計算の重複を避けるために、一意の結果をキャッシュしたいと考えています。

密行列:

typdef struct denseMatrix{
 int m;
 int n;
 double **d;            // actual matrix
 multiplyTable **entry; // key & result
} dns;

テーブル エントリ:

typedef struct multiplyTable{
 dns *rightOperand; // key
 dns *result;       // value
} multiplyTable;   // or something like that

dns *A, *B, *C, *D...; // allocated internally

C = mult(A,B); //may be called many many times.

この場合、mult はエントリ (オペランド、結果) のペアをテーブルに追加します。

add(A->entry, B, C); //B is the right operand and C is the result

後で D = mult(A, B) が再度呼び出される場合、search(A->entry,B) は C を取得します。一方、特定のオペランドがリストにない場合は、次のように追加されます。結果行列へのポインタ。

私はこれまでにこのようなことをしたことがなく、これが問題にアプローチする方法であるかどうかさえわかりません. 私の限られた理解では、ハッシュテーブルを使用してこのようなものを実装できます。

私が持っている実際的な質問には次のようなものがあります: (a) ハッシュテーブルはそもそも問題に対する適切な解決策ですか? ポインターアドレスをキーと値として許可しますか??

(b) 「ハッシュテーブル」を構造体の「フィールド」として保持することは理にかなっていますか? そうすれば、すでに左側のオペランドがあり、乗算テーブルで右側のオペランドを検索するだけで済みます。それとも、左オペランドと右オペランドの両方をキーとして持つ独立したテーブルが必要ですか?

(c) 足し算や掛け算などのために別のテーブルを作成しますか?それとも、オペランドと演算子を含む単一のテーブルを作成する必要がありますか?

(d) 作成されたすべてのオブジェクトを追跡して適切に解放できるようにする最善の方法は何ですか??

（e）このようなものを実装するのに適した公開ライブラリ（c）はどれですか？

私は、(a) 問題にアプローチできる別の方法、および (b) そのような別の方法の長所/短所に関する意見/提案を求めています。

最後に、このフォーラムは非常に役に立ちました。感謝の意を表したいと思います。++ありがとうございます。

4

3 に答える 3

1

ハッシュには細心の注意を払う必要があります。衝突 (異なる元の値に対して同じハッシュ値) がある場合、間違った結果になる可能性があります。マトリックスのハッシュを計算することは、実際の操作を実行するよりもはるかに効率的であると確信していますか (すべて明らかにこれらの操作の数/複雑さに依存します)

2 番目の懸念 - キャッシュの削除ポリシーについて何も言っていません。削除せずにハッシュ テーブルに追加するだけですか? 異なる行列の数によっては、メモリ不足になる可能性があります...

于 2009-08-17T03:00:02.637 に答える
0

この機能はメモ化と呼ばれます - 詳細については、ウィキペディアの記事を参照してください。

この記事では、役立ついくつかのライブラリについても説明します。

于 2009-08-17T06:29:20.957 に答える
0

最初に簡単な部分に答える: 行列演算の C++ ライブラリについては、広範な機能が組み込まれているnewmatを見てください。パフォーマンスに関してはかなり効率的です。

ハッシュを構築して計算を高速化するという特定のケースでは、非常に限られた一連の行列で操作を実行する場合を除き、キャッシュは価値があります。マトリックスの一意のハッシュを作成するには、すべてのエントリにアクセスし、各エントリの場所と値に基づいてハッシュを計算する必要があります。さらに悪いことに、行列は常に可換であるとは限りません。たとえば、特別な場合を除いてA B != B A です。

これは、特定の計算ごとに 1 つのエントリをキャッシュに格納する必要があることを意味します。そのため、非常に狭い範囲の入力行列を扱っていない限り、すべての結果を保持するためのメモリ コストが膨大になります。

  1. 非常に小さな行列または列/行ベクトルの場合、完全な計算とハッシュの計算のわずかなオーバーヘッドはごくわずかです...そのため、数ミリ秒の時間差が発生するほど多くの計算を行っていない限り、キャッシングによる追加の利点はほとんどありません。違いを生み出すのに十分な量を蓄積します。
  2. 非常に大きな行列の場合、可能な入力行列が非常に限られている場合、キャッシュの利点が見られる可能性があります。それらが何であれ、可能性のある利点は、キャッシュで繰り返しストライクを取得することのまれ性、およびキャッシュを管理するためのメモリコストと複雑さによって補われます.

キャッシュは結果を高速化しますが、非常に限られた状況でのみです。

ライブラリについてもアドバイスを求めていることを考えると、これは時期尚早の最適化のケースのように聞こえます。キャッシュせずにプログラムを実装し、パフォーマンスをプロファイルします。配列演算でパフォーマンスのボトルネックが見つかった場合は、数値処理を最適化する方法を検討してください。

編集: ハッシュの計算について: n 行 m 列の行列Xがある場合、その 1 つの行列のハッシュの計算は、R が行ベクトル [1,.., n] であり、C は列ベクトル [1,..,m] です。私は最適なペイオフを計算していませんが、2x2、3x3 のオーダーの非常に小さな行列の場合、生の計算を行う方がハッシュを計算するよりも安くなります。

于 2009-08-17T03:41:04.597 に答える