c++ - 缓存重复输入数据的表达式评估

Question

我有几个简单的“表达式”类派生自

namespace Expression {
class Virtual {
  public:
  Virtual();
  ~Virtual();

  virtual
  double eval(double x, double y, double z) const = 0; 
}
}

例如

class MyFun: public Virtual {
  public:
  MyFun();
  ~MyFun();

  virtual
  double eval(double x, double y, double z) const
  {
      return sin(x*x) + exp(z)*y + 3.0; // some expensive expression
  } 
}

这些表达式在许多但非常具体的 xyz 中被求值，即网格的节点

class MyMesh {
  MyMesh();
  ~MyMesh();

  virtual
  std::vector<std::vector<double> > getNodes() const
  {
      return allMyNodes_;
  } 
}

被调用者将实例化一个网格，实例化一个Expression，然后继续执行一些数值过程，其中可能多次在网格节点中评估Expression。

MyMesh myMesh();
MyFun myExpr();

Result result = numericalProcedure(myMesh, myExpr);
// [...]

因为 eval 很昂贵，所以我考虑了如何加快速度。想到的是缓存。

一个想法是将所有 eval 结果存储在一个带有一些索引的 vector 中的所有网格节点中，我想知道如何最好地实现这一点。我不想在 Expression 中粘贴任何网格数据(以将缓存保留在那里)，也不想让被调用者的界面变得更复杂。

是否有适合此用例的缓存设计模式？将缓存逻辑与其余代码隔离的方法有哪些？

Answer 1

您可以在仿函数中存储从参数数组到结果的映射:

class MyFun {
public:
    virtual
    double eval(double x, double y, double z) const
    {
        std::array<double,3> arr {x,y,z};

        //is the answer cached?
        if (cache_.count(arr))
        {
            return cache_[arr];
        }

        double ret = sin(x*x) + exp(z)*y + 3.0;
        //cache the result
        cache_[arr] = ret;
        return ret;
    } 

private:
    //need mutable so it can be modified by a const function
    mutable std::map<std::array<double,3>, double> cache_;
};

您甚至可以在基类中进行缓存，然后将求值转发给虚函数:

class BaseFun {
public:
    double eval(double x, double y, double z) const
    {
        std::array<double,3> arr {x,y,z};
        if (cache_.count(arr))
        {
            return cache_[arr];
        }

        double ret = doEval(x,y,z);
        cache_[arr] = ret;
        return ret;
    }   

protected:
    virtual double doEval (double x, double y, double z) const = 0;
private:
    mutable std::map<std::array<double,3>, double> cache_;
};

class MyFun : public BaseFun {
private:
    virtual double doEval (double x, double y, double z) const override
    {
        return sin(x*x) + exp(z)*y + 3.0;
    }
};