2

我正在尝试为应用程序提出加权算法。在应用程序中，不同元素的可用空间有限。一旦所有空间都被占用，算法应该选择要删除的最佳元素，以便为新元素腾出空间。

有不同的属性会影响这个决定。例如：

  • T：自上次访问以来的时间。（最好更换一段时间未访问的东西。）
  • N：访问次数。（最好更换没有多次访问的东西。）
  • R：为新元素腾出空间而需要移除的元素数量。（最好替换最少数量的元素。理想情况下，这还应该考虑到每个被替换元素的 T 和 N 属性。）

我有两个问题：

  1. 计算出给这些属性中的每一个赋予多少权重。
  2. 弄清楚如何计算元素的权重。

（1）我意识到为这样的事情提出权重是非常主观的，但我希望有一种标准方法或其他东西可以帮助我决定赋予每个属性多少权重。例如，我在想一种方法可能是提出一组两个样本元素，然后手动比较两者并决定最终应该选择哪一个。这是一个例子：

元素 A：N = 5，T = 2 小时前。
元素 B：N = 4，T = 10 分钟前。

在这个例子中，我可能希望 A 成为被选择替换的元素，因为虽然它被访问了一次，但与 B 相比，它已经很长时间没有被访问了。这种方法似乎需要很多时间，并且会涉及做出很多艰难的、主观的决定。此外，最后得出最终的权重可能并非易事。

我想出的另一种方法是任意选择不同属性的权重，然后使用该应用程序一段时间。如果我发现算法有任何明显错误，我可以进入并稍微修改权重。这基本上是一种“猜测和检查”的方法。

这两种方法似乎都不是很好，我希望有更好的解决方案。

(2) 一旦我计算出重量，我不确定哪种方法最适合计算重量。我应该添加所有内容吗？（在这些示例中，我假设具有最高元素的元素replacementWeight应该是要被替换的元素。）

replacementWeight = .4*T - .1*N - 2*R

或乘以一切？

replacementWeight = (T) * (.5*N) * (.1*R)

不使用常量作为权重怎么办？例如，确定“时间”(T) 可能很重要，但是一旦经过了特定的时间量，它就不会产生太大的影响。本质上，我会将所有内容归为“已经过去了很多时间”的垃圾箱。（例如，即使 8 小时和 7 小时两者之间有一个小时的差异，这种差异可能不如 1 分钟和 5 分钟之间的差异那么显着，因为这两个时间要近得多。）（或另一个示例：替换 (R ) 1 或 2 个元素很好，但是当我开始需要替换 5 或 6 个时，这应该被严重加权......因此它不应该是线性的。）

replacementWeight = 1/T + sqrt(N) - R*R

显然（1）和（2）是密切相关的，这就是为什么我希望有更好的方法来提出这种算法。

4

2 回答 2

2

您所描述的是选择缓存替换策略的经典问题。哪种策略最适合您，取决于您的数据，但以下通常效果很好：

首先，总是在缓存中存储一​​个新对象，驱逐R最差的对象。没有办法先验地知道一个对象是否应该被存储。如果对象没有用，它很快就会再次从缓存中掉出来。

流行的 squid 缓存实现了以下缓存替换算法：

  • 最近最少使用 (LRU)：
    • replacementKey = -T
  • 最不常用于动态老化 (LFUDA)：
    • replacementKey = N + C
  • 贪心双频（GDSF）：
    • replacementKey = (N/R) + C

C这里指的是缓存年龄因素。C基本上replacementKey是最后被驱逐的项目（或零）。

注意：replacementKey 是在插入或访问对象时计算的，并存储在对象旁边。具有最小替换键的对象被驱逐。

LRU 很简单，而且通常足够好。缓存越大，它的性能就越好。

LFUDA 和 GDSF 都是权衡取舍。LFUDA 更喜欢保留大对象，即使它们不太受欢迎，假设对大对象的一次命中构成对较小对象的大量命中。GDSF 基本上做了相反的权衡，保留许多较小的对象而不是较少的大对象。从您写的内容来看，后者可能很合适。

如果这些都不能满足您的需求，您可以计算 的最佳值T，N并且R（并比较不同的公式以组合它们）通过最小化后悔，您的公式和最佳算法之间的性能差异，例如使用线性回归。

于 2012-02-19T08:29:51.210 回答
1

这是一个完全主观的问题——正如您自己指出的那样。一个明显的可能性是，如果您的测试用例由对 (A,B) 组成，其中您更喜欢 A 到 B，那么您可能会发现您更喜欢 A 到 B 、 B 到 C 以及 C 而不是 A - 即它不是订购。

如果你不小心，你的功能可能不存在！

如果您可以使用各种系数和指数参数定义输入变量的标量函数，则可以使用回归估计所述参数，但如果您有很多参数，您将需要大量数据。

这是古典统计学家的方法，首先查看数据以识别模型，然后使用该模型来估计模型的特定实现。有很多关于这个主题的书籍。

于 2012-02-19T03:13:36.743 回答