6

私は、ユークリッドのアルゴリズムを使用して 2 つの数値の GCD を計算する何かをいじっていました。いつものように標準のワンライナーを実装しましたが、うまくいきました。シリーズを計算し、要素が大きくなるにつれてgcd()要素ごとに数回呼び出すアルゴリズムで使用されます。nメモ化することでもっとうまくできるかどうかを確認することにしたので、試したのは次のとおりです。

size_t const gcd(size_t const a, size_t const b) {
  return b == 0 ? a : gcd(b, a % b);
}

struct memoized_gcd : private std::unordered_map<unsigned long long, size_t> {
  size_t const operator()(size_t const a, size_t const b) {
    unsigned long long const key = (static_cast<unsigned long long>(a) << 32) | b;
    if (find(key) == end()) (*this)[key] = b == 0 ? a : (*this)(b, a % b);
    return (*this)[key];
  }
};

//std::function<size_t (size_t, size_t)> gcd_impl = gcd<size_t,size_t>;
std::function<size_t (size_t, size_t)> gcd_impl = memoized_gcd();

std::function後でインスタンスを介して、選択した関数を呼び出します。興味深いことに、たとえば n = 10,000 の場合、このコンピューターでは計算が 8 秒で実行され、メモ化されたバージョンでは 1 分近くかかり、他のすべては同じです。

明らかな何かを見逃しましたか？ハッシュマップkeyに特化する必要がないように、手段として使用しています。std::hash私が考えることができる唯一のことは、メモ化されたバージョンがTCOを取得せず、取得するgcd()か、ファンクターの呼び出しstd::functionが遅いか（両方で使用しているにもかかわらず）、またはおそらく私が遅れていることです。教祖よ、道を示してください。

ノート

g++ 4.7.0 を使用した win32 と win64、および g++ 4.6.1 と 4.7.1 を使用した Linux x86 でこれを試しました。

std::map<std::pair<size_t, size_t>, size_t>また、メモ化されていないバージョンと同等のパフォーマンスを持つバージョンも試しました。

4

3 に答える 3

6

お使いのバージョンのGCDの主な問題は、使用パターンによっては、大量のメモリを消費する可能性があることです。

たとえば、すべてのペア0 <= a <10,000、0 <= b <10,000のGCD（a、b）を計算すると、メモ化テーブルは100,000,000エントリになります。x86では各エントリが12バイトであるため、ハッシュテーブルは少なくとも1.2GBのメモリを使用します。その量のメモリでの作業は遅くなります。

そしてもちろん、値が10,000を超えるGCDを評価する場合は、テーブルを任意に大きくすることができます...少なくともアドレス空間またはコミット制限がなくなるまで。

概要：一般に、GCDをメモ化すると、メモリ使用量が無制限になるため、メモ化することはお勧めできません。

議論できるいくつかのより細かい点があります：

  • テーブルがさまざまなサイズを超えると、テーブルはますます低速のメモリに格納されます。最初にL1キャッシュ、次にL2キャッシュ、L3キャッシュ（存在する場合）、物理メモリ、ディスクです。明らかに、テーブルが大きくなるにつれて、メモ化のコストは劇的に増加します。
  • すべての入力が狭い範囲（たとえば、0 <= x <100）にあることがわかっている場合でも、メモ化または事前計算されたテーブルを使用することが最適化になる可能性があります。確かなことは難しいです-あなたはあなたの特定のシナリオで測定しなければならないでしょう。
  • GCDを最適化する方法は他にもある可能性があります。たとえば、この例では、g++が末尾再帰を自動的に認識するかどうかはわかりません。そうでない場合は、再帰をループに書き直すことでパフォーマンスを向上させることができます。

しかし、私が言ったように、あなたが投稿したアルゴリズムがうまく機能しないことはまったく驚くべきことではありません。

于 2012-07-13T05:23:27.043 に答える
0

これはそれほど驚くべきことではありません。最近のCPUでは、特にキャッシュにない場合、メモリアクセスは非常に遅くなります。多くの場合、値をメモリに保存するよりも、値を再計算する方が高速です。

于 2012-07-13T01:22:51.170 に答える
0

頻繁なヒープ割り当て (新しいエントリの作成時)。また、std::unordered_map ルックアップのオーバーヘッドも発生します (一定時間の場合もありますが、単純な配列オフセットよりも確実に遅くなります)。キャッシュ ミスも発生します (アクセス パターンとサイズの関数)。

「純粋な」比較を行いたい場合は、スタックに割り当てられた静的なプレーン配列を使用するように変換してみてください。これは、より多くのメモリを使用するスパース ルックアップ テーブルである可能性がありますが、メモ化された配列全体を CPU キャッシュに収めることができれば、メモ化をより代表するものになります。

于 2012-07-13T02:07:12.837 に答える