3

f(a,b)2 つの入力を受け入れる関数 があります。aとのどの値が使用されるかは前もってわかりませんb。私はメモリを少し無駄にしても大丈夫です (私は速度を気にします)。f(a,b)の出力が既に配信されているかどうかを確認できるようにしたいのですが、そうであれば、f(a,b)プロセスを再実行せずにその出力を再度配信します。

デコレータを使って Python で行うのは簡単ですが、C++ は私の頭をはるかに超えています。

4

5 に答える 5

7

キーがstd::pairであるstd::map (または) を使用するか、おそらくマップのマップを使用します。std::unordered_map

その場合、C++11 の改善がおそらく役に立ちます。または多分ブーストのもの。

于 2012-04-11T19:37:34.567 に答える
3

ポスターは次のように尋ねます。

f(a,b) の出力が既に配信されているかどうかを確認できるようにしたいのですが、そうであれば、f(a,b) プロセスを再実行せずにその出力を再度配信します。

を使用してC++で非常に簡単std::mapです。関数が正確に 2 つのパラメーターを持つという事実は、std::pairそれらを記述するために使用できることを意味します。

#include <map>
#include <iostream>

uint64_t real_f(int a, int b) {
  std::cout << "*";
  // Do something tough:
  return (uint64_t)a*b;
}

uint64_t memo_f(int a, int b) {
  typedef std::pair<int, int> key;
  typedef std::map<key, uint64_t> map;
  static map m;
  key k(a,b);
  map::iterator it = m.find(k);
  if(it == m.end()) {
    return m[k] = real_f(a, b);
  }
  return it->second;
}

int main () {
  std::cout << memo_f(1, 2) << "\n";
  std::cout << memo_f(3, 4) << "\n";
  std::cout << memo_f(1, 2) << "\n";
  std::cout << memo_f(3, 4) << "\n";
  std::cout << memo_f(5, 6) << "\n";
}

上記のプログラムの出力は次のとおりです。

*2
*12
2
12
*30

アスタリスクのない行は、キャッシュされた結果を表します。

于 2012-04-11T20:14:45.930 に答える
1

C++11 では、タスクとフューチャーを使用できます。あなたの機能をしましょうf：

int f(int a, int b)
{
    // Do hard work.
}

次に、戻り値へのハンドルを返す関数の実行をスケジュールします。このハンドルはfutureと呼ばれます:

template <typename F>
std::future<typename std::result_of<F()>::type>
schedule(F f)
{
    typedef typename std::result_of<F()>::type result_type;
    std::packaged_task<result_type> task(f);
    auto future = task.get_future();

    tasks_.push_back(std::move(task)); // Queue the task, execute later.
    return std::move(future);
}

次に、このメカニズムを次のように使用できます。

auto future = schedule(std::bind(&f, 42, 43)); // Via std::bind.
auto future = schedule([&] { f(42, 43); });    // Lambda alternative.

if (future.has_value())
{
    auto x = future.get();  // Blocks if the result of f(a,b) is not yet availble.
    g(x);
}

免責事項: 私のコンパイラはタスク/フューチャーをサポートしていないため、コードに多少の荒いエッジがある場合があります。

于 2012-04-11T19:55:29.950 に答える
0

この質問の要点は、f(a,b) の計算と、結果をキャッシュするためのある種のルックアップ テーブルの保持との間の CPU と RAM の相対的な費用です。

128 ビットのインデックス長の完全なテーブルは (まだ) 実行可能ではないため、ルックアップ スペースを管理可能なサイズに縮小する必要があります。これは、アプリ内でいくつかの考慮事項なしでは実行できません。

  • 関数入力の実際に使用されるスペースの大きさは? その中にパターンはありますか？
  • 一時的なコンポーネントはどうですか？繰り返される計算が互いに近いか、タイムラインに沿って分散すると予想しますか?
  • ディストリビューションはどうですか？関数呼び出しの大部分を消費するために、インデックス スペースのごく一部を想定していますか?

(a,b, f(a,b))タプルの固定サイズの配列と線形検索から始めるだけです。上記で尋ねたパターンによっては、

  • window-slide it (キャッシュ ミスで最も古いものを削除): これは局所化された再発に適しています
  • カウントが最小のタプルが(a,b,f(a,b),count)除外されるタプルを持つ - これは、ローカライズされていないオカレンスに適しています
  • キー関数にキャッシュ内の位置を決定させる (これは小さなインデックス スペースの使用に適しています)
  • 他にクヌースやグーグルが考えたであろうことは何でも

ルックアップ メカニズムがますます複雑になる場合は、繰り返し計算をルックアップ メカニズムに対してベンチマークすることもできstd::mapます。

于 2012-04-11T20:21:38.460 に答える
0

唯一の簡単な方法は、 を使用することstd::mapです。std::unordered_map動作しません。std::pair順序付けられていないマップのキーとして使用することはできません。次のことができます。

std::map<pair<int, int>, int> mp; 

int func(int a, int b)
{
  if (mp.find({a, b}) != mp.end()) return mp[{a, b}];
  // compute f(a, b)...
  mp[{a, b}] = // computed value;
  return mp[{a, b}];
}
于 2021-03-04T02:17:51.920 に答える