2

想象一下，你有一个相当大的 double 数组和一个avg(double*,size_t)计算平均值的简单函数（只是一个简单的例子：数组和函数都可以是任何数据结构和算法）。我希望如果第二次调用该函数并且同时未更改数组，则返回值直接来自前一个，而无需经过未更改的数据。

保持之前的值看起来很简单，我只需要在函数内部添加一个静态变量，对吧？但是检测数组的变化呢？我是否需要编写一个接口来访问设置函数要读取的标志的数组？可以做一些更智能、更便携的事情吗？

4

2 回答 2

1

正如Kerrek SB 所说，这就是所谓的“记忆化”。我将在最后介绍我个人最喜欢的方法（使用double* array和更简单的方法DoubleArray），因此如果您只想查看代码，可以跳到那里。但是，有很多方法可以解决这个问题，我想把它们都介绍一遍，包括其他人建议的方法。如果您只想查看代码，请跳至水平线。

第一部分是一些理论和替代方法。这个问题基本上有四个部分：

  • 证明函数是幂等的（调用一次函数与调用任意次数相同）
  • 缓存键入输入的结果
  • 在给定一组新输入的情况下搜索缓存结果
  • 使不再准确/当前的缓存结果无效

第一步对您来说很容易：平均值是幂等的。它没有副作用。

缓存结果是一个有趣的步骤。您显然将为输入创建一些“键”，您可以将其与缓存的“键”进行比较。在 Kerrek SB 的 memoization示例中，key 是所有参数的元组，与其他带有==. 在您的系统中，等效的解决方案是将密钥作为整个数组的内容。这意味着每个键比较都是 O(n)，这是昂贵的。如果函数的计算成本高于平均函数，那么这个价格可能是可以接受的。然而，在平均的情况下，这个密钥非常昂贵。

这导致了对好密钥的开放式搜索。Dieter Lücking 的答案是键入数组指针。这是 O(1)，而且启动速度很快。但是，它还假设一旦计算了数组的平均值，该数组的值就永远不会改变，并且该内存地址永远不会重新用于另一个数组。这个问题的解决方案稍后会在任务的失效部分出现。

另一个流行的键是评论中的 HotLick (1)。您使用数组的唯一标识符（指针，或者更好的是，永远不会再次使用的唯一整数 idx）作为键。然后，每个数组都有一个“脏位avg”，只要值发生更改，它们就会被设置为 true。缓存首先查找脏位。如果为真，则忽略缓存值，计算新值，缓存新值，然后清除表示缓存值现在有效的脏位。（这确实是无效的，但它很适合这部分答案）

该技术假设调用的次数avg多于数据的更新次数。如果数组一直是脏的，那么 avg 仍然需要不断地重新计算，但我们仍然要为每次写入时设置脏位付出代价（减慢它的速度）。

该技术还假设只有一个函数avg需要缓存结果。如果您有许多功能，那么让所有脏位保持最新会变得很昂贵。解决方案是一个“纪元”计数器。你有一个整数，而不是一个脏位，它从 0 开始。每次写入都会增加它。当你缓存一个结果时，你不仅缓存了数组的标识，还缓存了它的纪元。当您检查是否有缓存值时，您还要检查时期是否发生了变化。如果它确实发生了变化，您就无法证明您的旧结果是最新的，并且必须将它们丢弃。

存储结果是一项有趣的任务。编写一个存储算法非常容易，它通过记住数十万个旧结果来消耗大量内存avg。一般来说，需要有一种方法让缓存代码知道一个数组已被破坏，或者一种方法可以慢慢移除旧的未使用缓存结果。在前一种情况下，双数组的释放器需要让缓存代码知道该数组正在被释放。在后一种情况下，通常将缓存限制为 10 或 100 个条目，并驱逐旧的缓存结果。

最后一部分是缓存失效。我之前谈到了肮脏的部分。对此的一般模式是，如果缓存中的值没有更改，则必须将缓存中的值标记为无效，但数组中的值确实更改了。如果键是数组的副本，这显然永远不会发生，但是当键是标识整数或指针时，它可能会发生。

一般来说，失效是向调用者添加要求的一种方式：如果您想使用avg缓存，这里是您需要做的额外工作来帮助缓存代码。

最近我用这种缓存失效方案实现了一个系统。它非常简单，源于一种理念：调用的代码avg比它本身更能确定数组是否发生了变化avg。

  • 有两个版本的avg:double avg(double* array, int n)和double avg(double* array, int n, CacheValidityObject& validity).
  • 调用avgnever cached 的 2 参数版本，因为它不能保证数组没有更改。
  • 调用avg激活缓存的 3 参数版本。调用者保证，如果它传递相同的 CacheValidityObjectavg而不将其标记为脏，则数组必须相同。

将责任推给来电者使平均微不足道。CacheValidityObject 是一个非常简单的类来保存结果

class CacheValidityObject
{
    public:
        CacheValidityObject(); // creates a new dirty CacheValidityObject

        void invalidate(); // marks this object as dirty


        // this function is used only by the `avg` algorithm.  "friend" may
        // be used here, but this example makes it public
        boost::shared_ptr<void>& getData();
    private:
        boost::shared_ptr<void>  mData;
};

inline void CacheValidityObject::invalidate()
{
    mData.reset(); // blow away any cached data
}

double avg(double* array, int n); // defined as usual

double avg(double* array, int n, CacheValidityObject& validity)
{
    // this function assumes validity.mData is null or a shared_ptr to a double
    boost::shared_ptr<void>& data = validity.getData();
    if (data) {
        // The cached result, stored on the validity object, is still valid
        return *static_pointer_cast<double>(data);
    } else {
        // There was no cached result, or it was invalidated
        double result = avg(array, n);
        data = make_shared<double>(result); // cache the result
        return result;
    }
}

// usage
{
    double data[100];
    fillWithRandom(data, 100);

    CacheValidityObject dataCacheValidity;
    double a = avg(data, 100, dataCacheValidity); // caches the aveerage
    double b = avg(data, 100, dataCacheValidity); // cache hit... uses cached result

    data[0] = 0;
    dataCacheValidity.invalidate();
    double c = avg(data, 100, dataCacheValidity); // dirty.. caches new result
    double d = avg(data, 100, dataCacheValidity); // cache hit.. uses cached result

    // CacheValidityObject::~CacheValidityObject() will destroy the shared_ptr,
    // freeing the memory used to cache the result
}

优点

  • 几乎是最快的缓存（在几个操作码内）
  • 实现起来很简单
  • 不泄漏内存，仅当调用者认为它可能想要再次使用它们时才保存缓存值

缺点

  • 要求调用者处理缓存，而不是为它们隐式执行。

如果将 包装double* array在一个类中，则可以最大程度地减少缺点。为每个算法分配一个索引（可以在运行时完成）让DoubleArray类维护一个缓存值的映射。每次修改都会DoubleArray使缓存的结果无效。这是最易于使用的版本，但不适用于裸数组...您需要一个类来帮助您

class DoubleArray
{
    public:
        // all of the getters and setters and constructors.
        // Special note: all setters MUST call invalidate()

        CacheValidityObject getCache(int inIdx)
        {
            return mCaches[inIdx];
        }

        void setCache(int inIdx, const CacheValidityObject& inObj)
        {
            mCaches[inIdx] = inObj;
        }

    private:
        void invalidate()
        {
            mCaches.clear();
        }

        std::map<int, CacheValidityObject> mCaches;
        double*                            mArray;
        int                                mSize;
};

inline int getNextAlgorithmIdx()
{
    static int nextIdx = 1;
    return nextIdx++;
}


static const int avgAlgorithmIdx = getNextAlgorithmIdx();
double avg(DoubleArray& inArray)
{
    CacheValidityObject valid = inArray.getCache(avgAlgorithmIdx);
    // use the 3 argument avg in the previous example
    double result = avg(inArray.getArray(), inArray.getSize(), valid);
    inArray.setCache(avgAlgorithmIdx, valid);
    return result;
}

// usage
DoubleArray  array(100);
fillRandom(array);
double a = avg(array); // calculates, and caches
double b = avg(array); // cache hit
array.set(0, 5); // invalidates caches
double c = avg(array); // calculates, and caches
double d = avg(array); // cache hit
于 2013-09-12T00:42:25.163 回答
0 
#include <limits>
#include <map>

// Note: You have to manage cached results - release it with avg(p, 0)! 
double avg(double* p, std::size_t n) {
    typedef std::map<double*, double> map;
    static map results;
    map::iterator pos = results.find(p);
    if(n) {
        // Calculate or get a cached value
        if(pos == results.end()) {
            pos = results.insert(map::value_type(p, 0.5)).first; // calculate it
        }
        return pos->second;
    }
    // Erase a cached value
    results.erase(pos);
    return std::numeric_limits<double>::quiet_NaN();
}
于 2013-09-11T18:12:32.043 回答