algorithm - 提出加权算法的因素？

Question

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

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

• T:自上次访问以来的时间。 (最好更换一段时间未访问的内容。)
• N:访问次数。 (最好更换未多次访问的内容。)
• R:需要移除的元素数量，以便为新元素腾出空间。 (最好替换最少数量的元素。理想情况下，这还应考虑被替换的每个元素的 T 和 N 属性。)

我有两个问题:

1. 计算出每个属性的权重。
2. 弄清楚如何计算元素的权重。

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

Element A: N = 5, T = 2 hours ago.
Element B: N = 4, T = 10 minutes ago.

在这个例子中，我可能希望 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) 密切相关，这就是为什么我希望有更好的方法来提出这种算法。

Answer 1

您所描述的是选择 cache replacement policy 的经典问题.哪种政策最适合您取决于您​​的数据，但以下通常很有效:

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

流行的鱿鱼缓存 implements以下缓存替换算法:

• 最近最少使用 (LRU):
  • replacementKey = -T
• 最不常用于动态老化 (LFUDA) 的:
  • replacementKey = N + C
• Greedy-Dual-Size-Frequency (GDSF):
  • replacementKey = (N/R) + C

C 在这里指的是一个缓存年龄因素。 C 基本上是最后被逐出(或零)的项目的 replacementKey。

注意:replacementKey 是在插入或访问对象时计算的，并与对象一起存储。具有最小 replacementKey 的对象被逐出。

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

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

如果这些都不能满足您的需求，您可以计算出T、N 和R 的最佳值(并比较不同的公式以进行组合他们)通过最小化后悔，你的公式和optimal之间的性能差异算法，例如使用 Linear regression .