優化通過內存搜索

我有4096個項目的多個實例。我需要在reocurring的基礎上搜索並找到一個項目，我想優化它。因爲並不是所有的4096項都可以使用，所以我認爲，一種加快速度的方法是使用鏈表而不是數組。無論何時我必須搜索一個項目，一旦找到它，我都會將它放在列表的頭部，以便下次出現時，我只需要進行最小限度的搜索（循環）工作。這聽起來正確嗎？優化通過內存搜索

EDIT1 我不認爲二叉搜索樹的想法是真的是我可以用，因爲我有排序的數據，像一個陣列，即每個節點繼前一個更大，這違背了目的，不它？

我試圖解決我的問題與緩存和像這樣的東西來到了：

pending edit

但輸出我得到的，表明這是行不通的，好像我也想：

有關如何改善此問題的任何建議？

來源

2014-09-25 cerr

如果您的數組或4096列表是按順序排列的（按字母順序排列或其他）二進制搜索真的很快。 http://en.wikipedia.org/wiki/Binary_search_algorithm – BrettFromLA 2014-09-25 22:32:04

最糟糕的情況是，除非您按照Brett的建議對數組或列表進行排序，否則您的搜索仍然是O（N）。因此，使用排序列表可以增加插入的複雜性（插入順序），但搜索速度會更快。你所建議的幾乎就像一個「緩存」。對於我們來說，在沒有任何關於近期內找到的物品再次被搜索的頻率的多麼有用的情況下很難說。顯然，緩存是有好處的，這就是爲什麼我們在內存中擁有整個L1，L2，L3架構。但是否它會爲你工作，這是不確定的。

來源

2014-09-25 22:38:34 gnychis

請參閱上面的** EDIT1 ** – cerr 2014-09-26 22:32:06

回覆編輯1：我想如果你的數據元素不是很大，比如說只有幾個字節甚至幾十個字節，那麼可以將4096個元素裝入內存。在這種情況下，你需要的是一個哈希表。在C++中，您使用unordered_map。例如，如果您的密鑰類型爲int，則可以定義unorderedmap<int, ptr_to_your_node_type>並獲取O(1)中的元素。

如果你能很好地設計你的散列並且最壞的情況可能是O(n)，最快的搜索可能是O(1)。如果這些項目很大並且無法裝入內存，則可以使用所謂的最近最少使用的緩存algorithm來節省內存。

用於LRU高速緩存的示例代碼

template <typename K> 
class Key_Age{ 
list<K> key_list; 
unordered_map<K, typename list<K> :: iterator> key_pos; 
public: 
void access(K key){ 
    key_list.erase(key_pos[key]); 
    insert_new(key); 
} 

void insert_new(K key){ 
    key_list.push_back(key); 
    key_pos[key] = --key_list.end(); 
} 

K pop_oldest(){ 
    K t = key_list.front(); 
    key_list.pop_front(); 
    return t; 
} 
}; 

class LRU_Cache{ 
int capacity; 
Key_Age<int> key_age; 
unordered_map<int, int> lru_cache; 

public: 
LRU_Cache(int capacity): capacity(capacity) { 
} 

int get(int key) { 
    if (lru_cache.find(key) != lru_cache.end()) { 
     key_age.access(key); 
     return lru_cache[key]; 
    } 
    return -1; 
} 

void set(int key, int value) { 
    if (lru_cache.count(key) < 1) { 
     if (lru_cache.size() == capacity) { 
      int oldest_key = key_age.pop_oldest(); 
      lru_cache.erase(oldest_key); 
     } 
     key_age.insert_new(key); 
     lru_cache[key] = value; 
     return; 
    } 

    key_age.access(key); 
    lru_cache[key] = value; 
}

};

來源

2014-09-25 22:48:13

請參閱** EDIT1 **上面的 – cerr 2014-09-26 22:33:19

說到性能，只有一個重要的規則：衡量它！

在你的情況下，你可以例如有兩個不同的考慮因素，一個理論運行時分析和一個機器上真的發生了什麼。兩者都嚴重依賴於您的4096項目的特點。如果你的數據是排序的，你可以有一個O（log n）搜索，如果它是未排序的，最壞的情況是O（n）等。

關於你對鏈表的想法，你可能會有更多的硬件緩存未命中，即使您的理論考慮是正確的，數據也不會再一起存儲（空間局部性），從而導致實施較慢。

如果你有興趣，一般在這樣的問題，我建議這個涼爽的談話從GoingNative 2013 http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly

來源

2014-09-25 22:48:15 lwi

如果您的數據可以放在一個二叉搜索樹：http://en.wikipedia.org/wiki/Binary_search_tree

然後你可以使用一個數據稱爲Splay樹的結構：「splay tree是一個自我調整的二叉搜索樹，具有最近訪問的元素快速訪問的附加屬性」http://en.wikipedia.org/wiki/Splay_tree

來源

2014-09-25 22:51:07 Centril

請參閱上面的** EDIT1 ** – cerr 2014-09-26 22:31:37

優化通過內存搜索

回答

相關問題