寻找固定长度排列的块算法

Question

要查找长度为2的所有排列，可以使用下面的简单程序:

  #include <iostream>
  using namespace std;
  int main(int argc, const char *argv[])
  {
      int l[] = {0, 1, 2, 3, 4, 5};
      const int length = sizeof(l)/sizeof(l[0]);
      for(int i = 0; i + 1 < length; i++)
          for(int j = i + 1; j < length; j++)
              cout << "(" << l[i] << ", " << l[j] << ")" << endl;
      return 0;
  }

但是在我需要它的应用程序中，单个项是BIG的，并且需要在使用集合之前构造。因此，我试图找到算法，它做同样的，但阻塞。阻塞应该允许我有一个可以用于缓存的银行。

下面举例说明了一个(手动)创建序列的银行，它可以容纳4个项目:

SETS, Cache miss, bank
(0,1) * *         0, 1
(0,2) *           0, 1, 2
(0,3) *           0, 1, 2, 3
(1,2)             0, 1, 2, 3
(1,3)             0, 1, 2, 3
(2,3)             0, 1, 2, 3
(0,4) *           0, 1, 2, 4
(1,4)             0, 1, 2, 4
(2,4)             0, 1, 2, 4
(0,5) *           0, 1, 4, 5
(1,5)             0, 1, 4, 5
(4,5)             0, 1, 4, 5
(2,5)             0, 2, 4, 5
(3,4) *           3, 2, 4, 5
(3,5)             3, 2, 4, 5

你们有人知道这个问题的解决办法吗?或者你能指出正确的方向吗?

——艾伦

Answer 1

使用方法get(int ID)创建类cache，该方法返回具有相应ID的项目:

(1)如果对应的项已经被缓存，返回缓存的副本(或指向它的指针)
(2)如果不是:创建它，从缓存中删除一个条目，将新条目添加到缓存中，然后继续执行(1)

困难的部分是决定从(2)中的缓存中删除哪个项。最优选择是删除最长时间不需要的项。如果这是不实际的(例如，因为您对访问模式了解不够)，有许多替代方案。

最常见的是:

• LRU:删除最近最少使用的项
• MRU:删除最近使用的项
• LFU:删除最不常用的项

参见维基百科关于缓存算法的文章获取更多示例