通过内存优化搜索

Question

我有4096个条目的多个实例。我需要搜索和找到一个项目的重新锁定的基础上，我想优化它。由于不是所有的4096项都可以使用，我想，加快速度的方法是使用链接列表而不是数组。每当我必须搜索一个项目时，一旦我找到了它，我就会把它放在列表的首位，这样下次它出现时，我只需要做最小的搜索(循环)工作。这听起来对吗？

EDIT1 --我不认为二叉树搜索树的想法是我可以使用的，因为我已经对数据进行了排序，就像一个数组，即前一个节点后面的每个节点都更大，这违背了我的目的，不是吗？

我试图解决缓存问题，并想出了如下所示：

pending edit

但是我得到的输出表明，它不像我希望的那样工作：

对我如何改进这个问题有什么建议吗？

Answer 1

当谈到性能时，只有一个重要的规则:度量它！

例如，在您的示例中，您可以考虑两个不同的问题，一个是理论运行时分析，另一个是机器上的实际情况。两者在很大程度上取决于您4096项的特性。如果对数据进行排序，则可以进行O(log n)搜索，如果数据未排序，则是最坏的情况O(n)等等。

关于链接列表的想法，您可能有更多的硬件缓存失败，因为数据不再存储在一起(空间位置)，即使您的理论考虑是正确的，最终也会有一个较慢的实现。

如果你对这样的问题感兴趣，我推荐GoingNative 2013 http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly的这个很酷的演讲。

Answer 2

最糟糕的情况是，除非像Brett建议的那样对数组或列表进行排序，否则搜索仍然是O(N)。因此，使用排序列表，可以增加插入的复杂性(插入顺序)，但搜索速度会快得多。你所建议的几乎就像一个“缓存”。对于我们来说，如果不知道在短期内再次搜索一件发现的物品的频率，我们很难说它有多有用。显然，缓存是有好处的，这就是为什么我们在内存中拥有整个L1、L2、L3体系结构。但它是否会对你来说是不确定的。

Answer 3

响应Edit1:我认为如果数据元素不是很大，比如说，只有几个字节，甚至几十个字节，那么其中的4096个可以安装到内存中。在这种情况下，您需要的是一个哈希表。在C++中，您使用unordered_map。例如，如果您的键类型是unorderedmap<int, ptr_to_your_node_type>，则可以定义int并在O(1)中获取元素。

如果您能够很好地设计哈希，最快的搜索可能是O(1)，最坏的情况可能是O(n)。如果这些项很大，不能安装到内存中，则可以使用所谓的最近使用最少的缓存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;
}

}；