algorithm - 查找固定长度排列的分块算法

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;
  }

但在我需要这个的应用程序中，单个项目很大，需要先构建才能使用集合。因此，我试图找到算法，它的功能相同但有阻塞。阻塞应该允许我有一个可用于缓存的银行。

下图说明了一个(手动)创建的带有银行的序列，它可以容纳 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:删除最不常用的项

参见 Wikipedia article about cache algorithms更多示例。