2

単項関数の値の配列を事前に計算したいと思いますf。

f(x)wherexは の形式の値のみが必要であることはわかっています。ここで、とはa*b両方ともrange 内の整数です。ab0..N

明らかな時間最適化の選択は、サイズの配列を作成し、N*N後で読み取る要素だけを事前に計算することです。についてf(a*b)は、チェックして設定するだけtab[a*b]です。これは可能な限り最速の方法ですが、この配列には ( で始まるN+1) 決して触れない多数のインデックスがあるため、これは多くのスペースを必要とします。

もう 1 つの解決策は、単純なツリー マップを作成することです。しかし、これは多くの分岐を導入することで、ルックアップ自体を非常に遅くします。いいえ。

私は疑問に思います-そのような配列をスパースでなく小さくする解決策はありますか?

編集

ハッシュマップについて多くのコメントを聞くことができます...どのように動作するかのベンチマークに進みます(分岐により、通常のルックアップよりも大幅なパフォーマンス低下が予想されます;ツリーよりも少ないですが、それでも...そうです！） .

強調したいのは、「製品のような」インデックスのみが取得されるという事実を利用するために、何らかの巧妙な方法 (?) を使用する分析ソリューションを最も高く評価することです。この事実を悪用して、平均的な一般的なハッシュ マップ関数よりも優れた結果が得られる可能性があると思いますが、私自身はアイデアがありません。

編集

std::unordered_mapあなたのアドバイスに従って、 gcc 4.5から試しました。これは、単純な配列ルックアップよりも少し遅くなりましたが、実際にはツリーベースよりもはるかに高速std::mapでした.最終的には、このソリューションで問題ありません. 当初意図していたことができない理由がわかりました。説明をありがとう！

ハッシュマップが実際にメモリを節約するかどうかはわかりません! :) @Keith Randall が説明したように、メモリ フットプリントを よりも低くすることはできず、N*N/4@Sjoerd によって説明された三角行列アプローチではN*N/2. N*N/2要素のサイズが小さい場合 (コンテナーのオーバーヘッドによって異なります) 、ハッシュ マップがスペース以上のものを使用する可能性は十分にあると思います。それを確認してみます。

2つの答えを受け入れることができればいいのに...

4

4 に答える 4

5

それを 2 次元配列として見ることから始めますtab[a][b]。これにはまだ N*N サイズが必要です。

各エントリが使用されますが、重複があります: f(a,b) = f(b,a). そのため、三角行列のみが必要です (a>b と a<b の場合、分岐が 1 つ必要になります)。

if (a < b) return tab[b*(b+1) + a]; // assuming 0 <= a < b < N
else return tab[a*(a+1) + b];       // assuming 0 <= b <= a < N

または

if (a < b) return tab[b*(b-1) + a]; // assuming 1 <= a < b <= N
else return tab[a*(a-1) + b];       // assuming 1 <= b <= a <= N

編集: 三角行列で使用されるメモリは (N+1)*N/2 で、正方行列の約半分のサイズです。ただし、まだ2次です:(

EDIT2: er はマトリックス内でまだ重複していることに注意してくださいf(3, 2) = f(6, 1)。多くの分岐とループを導入しないとこれを排除できないと思いますが、それは単なる直感です。

于 2011-01-15T01:47:45.887 に答える
2

ここで利用できる構造はあまりないようです。起こり得ないエントリのストレージを回避できるようにテーブルを配置する方法があるかどうかを尋ねている場合 (それらの素因数が N より大きいため)、あまり節約できません。N^2 付近の N 平滑数の密度は ~2^-2 であるという平滑数の理論があります。したがって、絶対的な最良のケースとして、(最大) ストレージ要件を最大で 4 分の 1 に減らすことができます。

ほとんどの引数が発生しないと予想される場合は、対称性を利用してからハッシュ テーブルを使用する方がよいと思います。

于 2011-01-15T06:44:10.383 に答える
0

A と B の組み合わせを単純にハッシュして、結果をマップに入れてみませんか? そして、欲しいものだけを手に入れるために怠惰にしますか？

public Result f(Type1 a, Type2 b) {
    TypePair key = new TypePair(a, b);
    Result res = map.get(key);
    if (res == null) {
        res = reallyCalculate(a, b);
        map.put(key, res);
    }
    return res;
}

基本的なメモ化。

于 2011-01-15T01:44:56.157 に答える
0

ハッシュ テーブルは、検索速度とメモリ オーバーヘッドのバランスを適切にとります。C++ 標準ライブラリはハッシュ テーブルを提供しませんが、非標準の拡張機能として利用できる場合があります。たとえば、 SGI hash_mapを参照してください。

Poco C++ ライブラリには、HashTable および HashMap クラスもあります。ドキュメントを参照してください。

于 2011-01-15T01:45:28.763 に答える