缓存单个重写计算C++ 11

Question

我想要一种缓存由两个派生类共享的计算的方法的建议.作为一个例子,我有两种类型的归一化向量L1和L2,它们各自定义它们自己的归一化常数(注意:反对良好实践我将从std::vector这里继承作为一个快速说明 - 信不信由你,我真正的问题不是关于L1和L2向量!):

#include <vector>
#include <iostream>
#include <iterator>
#include <math.h>

struct NormalizedVector : public std::vector<double> {
  NormalizedVector(std::initializer_list<double> init_list):
    std::vector<double>(init_list) { }
  double get_value(int i) const {
    return (*this)[i] / get_normalization_constant();
  }
  virtual double get_normalization_constant() const = 0;
};

struct L1Vector : public NormalizedVector {
  L1Vector(std::initializer_list<double> init_list):
    NormalizedVector(init_list) { }
  double get_normalization_constant() const {
    double tot = 0.0;
    for (int k=0; k<size(); ++k)
      tot += (*this)[k];
    return tot;
  }
};

struct L2Vector : public NormalizedVector {
  L2Vector(std::initializer_list<double> init_list):
    NormalizedVector(init_list) { }
  double get_normalization_constant() const {
    double tot = 0.0;
    for (int k=0; k<size(); ++k) {
      double val = (*this)[k];
      tot += val * val;
    }
    return sqrt(tot);
  }
};

int main() {
  L1Vector vec{0.25, 0.5, 1.0};
  std::cout << "L1 ";
  for (int k=0; k<vec.size(); ++k)
    std::cout << vec.get_value(k) << " ";
  std::cout << std::endl;

  std::cout << "L2 ";
  L2Vector vec2{0.25, 0.5, 1.0};
  for (int k=0; k<vec2.size(); ++k)
    std::cout << vec2.get_value(k) << " ";
  std::cout << std::endl;
  return 0;
}

这个代码对于大型向量来说是不必要的慢,因为它get_normalization_constant()反复调用,即使它在构造之后没有改变(假设push_back已经适当地禁用了修饰符).

如果我只考虑一种规范化形式,我只需使用一个double值来缓存这个结果:

struct NormalizedVector : public std::vector<double> {
  NormalizedVector(std::initializer_list<double> init_list):
    std::vector<double>(init_list) {
    normalization_constant = get_normalization_constant();
  }
  double get_value(int i) const {
    return (*this)[i] / normalization_constant;
  }

  virtual double get_normalization_constant() const = 0;
  double normalization_constant;
};

但是,这可以理解为无法编译,因为NormalizedVector构造函数尝试调用纯虚函数(在基本初始化期间派生的虚拟表不可用).

选项1: 派生类必须normalization_constant = get_normalization_constant();在其构造函数中手动调用该函数.

选项2: 对象定义用于初始化常量的虚函数:

init_normalization_constant() {
  normalization_constant = get_normalization_constant();
}

然后由工厂构建对象:

struct NormalizedVector : public std::vector<double> {
  NormalizedVector(std::initializer_list<double> init_list):
    std::vector<double>(init_list) {
    //    init_normalization_constant();
  }
  double get_value(int i) const {
    return (*this)[i] / normalization_constant;
  }

  virtual double get_normalization_constant() const = 0;
  virtual void init_normalization_constant() {
    normalization_constant = get_normalization_constant();
  }

  double normalization_constant;
};

// ...
// same code for derived types here
// ...

template <typename TYPE>
struct Factory {
  template <typename ...ARGTYPES>
  static TYPE construct_and_init(ARGTYPES...args) {
    TYPE result(args...);
    result.init_normalization_constant();
    return result;
  }
};

int main() {
  L1Vector vec = Factory<L1Vector>::construct_and_init<std::initializer_list<double> >({0.25, 0.5, 1.0});
  std::cout << "L1 ";
  for (int k=0; k<vec.size(); ++k)
    std::cout << vec.get_value(k) << " ";
  std::cout << std::endl;

  return 0;
}

选项3: 使用实际缓存:get_normalization_constant定义为新类型,CacheFunctor; 第一次CacheFunctor调用时,它会保存返回值.

在Python中,这可以按原始编码的方式工作,因为虚拟表始终存在,即使在__init__基类中也是如此.在C++中,这更棘手.

我真的很感激他的帮助; 这对我来说很重要.我觉得我在C++中获得了良好的面向对象设计,但并不总是在制作非常高效的代码时(特别是在这种简单的缓存的情况下).

Answer 1

我建议使用非虚拟接口模式.当您希望方法提供通用和唯一功能时,此模式非常出色.(在这种情况下,共同缓存,唯一性计算.)

http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Non-Virtual_Interface

// UNTESTED
struct NormalizedVector : public std::vector<double> {
 ...
  double normalization_constant;
  bool cached;
  virtual double do_get_normalization_constant() = 0;
  double get_normalization_constant() {
    if(!cached) {
      cached = true;
      normalization_constant = do_get_normalization_constant();
    }
    return normalization_constant;
};

Ps你真的不应该公开来自std::vector.

PPs使缓存失效就像设置cached为false 一样简单.

完整解决方案

#include <vector>
#include <iostream>
#include <iterator>
#include <cmath>
#include <algorithm>

struct NormalizedVector : private std::vector<double> {
private:
  typedef std::vector<double> Base;
protected:
  using Base::operator[];
  using Base::begin;
  using Base::end;
public:
  using Base::size;

  NormalizedVector(std::initializer_list<double> init_list):
    std::vector<double>(init_list) { }
  double get_value(int i) const {
    return (*this)[i] / get_normalization_constant();
  }

  virtual double do_get_normalization_constant() const = 0;
  mutable bool normalization_constant_valid;
  mutable double normalization_constant;
  double get_normalization_constant() const {
    if(!normalization_constant_valid) {
      normalization_constant = do_get_normalization_constant();
      normalization_constant_valid = true;
    }
    return normalization_constant;
  }

  void push_back(const double& value) {
    normalization_constant_valid = false;
    Base::push_back(value);
  }

  virtual ~NormalizedVector() {}
};

struct L1Vector : public NormalizedVector {
  L1Vector(std::initializer_list<double> init_list):
    NormalizedVector(init_list) { get_normalization_constant(); }
  double do_get_normalization_constant() const {
    return std::accumulate(begin(), end(), 0.0);
  }
};

struct L2Vector : public NormalizedVector {
  L2Vector(std::initializer_list<double> init_list):
    NormalizedVector(init_list) { get_normalization_constant(); }
  double do_get_normalization_constant() const {
    return std::sqrt(
      std::accumulate(begin(), end(), 0.0,
        [](double a, double b) { return a + b * b; } ) );
  }
};

std::ostream&
operator<<(std::ostream& os, NormalizedVector& vec) {
  for (int k=0; k<vec.size(); ++k)
    os << vec.get_value(k) << " ";
  return os;
}

int main() {
  L1Vector vec{0.25, 0.5, 1.0};
  std::cout << "L1 " << vec << "\n";

  vec.push_back(2.0);
  std::cout << "L1 " << vec << "\n";

  L2Vector vec2{0.25, 0.5, 1.0};
  std::cout << "L2 " << vec2 << "\n";

  vec2.push_back(2.0);
  std::cout << "L2 " << vec2 << "\n";
  return 0;
}