阻塞算法找到固定長度排列

要找到兩個一長度所有的排列可以使用遵循簡單的程序：阻塞算法找到固定長度排列

#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

任何你是否知道解決這個問題呢？或者你可以指出正確的方向。

- 艾倫

來源

2011-05-01 Allan

我認爲它不會改變阻塞應該如何表現，但是您想要排列還是組合？ – svick 2011-05-01 22:19:28

與方法get(int ID)，其與相應的ID返回該項創建類cache：

（1）如果相應的項已被高速緩存，則返回高速緩存的副本（或一個指針）

（2）如果不是：創建它，從緩存中刪除一個項目，（2）中的哪個項目從緩存中移除。最佳選擇是移除最長時間不需要的物品。如果這是不實際的（例如，因爲您對訪問模式不夠了解），則有很多選擇。

，最常見的有：

LRU：除去最近最少使用的項目
MRU：刪除最近使用的項目
LFU：刪除不常用的項目

查看Wikipedia article about cache algorithms瞭解更多示例。

來源

2011-05-01 23:43:18 Philip

我認爲問題主要是找出最佳訪問模式：他可以按照他想要的任何順序生成排列，最好的排列是什麼？ – svick 2011-05-02 05:54:54

這個問題不是關於一般的阻塞或緩存，而是如何改變實際的算法以按照最小化緩存未命中數量的順序產生該組。 – Allan 2011-05-02 05:55:07

@Allan：啊，我明白了。高速緩存未命中的數量取決於訪問模式*和*高速緩存算法以及'1'的大小和請求的排列大小。我們可以假設'sizeof（l）== 6'，並且你正在尋找所有長度爲2的組合，就像你的OP一樣？此外，你是在尋找長度爲2的所有子集或所有可能的2元組？ – Philip 2011-05-02 11:15:12

阻塞算法找到固定長度排列

回答

相關問題