Оптимизация поиска по памяти

Question

У меня есть несколько экземпляров из 4096 элементов. Мне нужно найти и найти элемент на основе повторного ввода, и я бы хотел его оптимизировать. Поскольку не все 4096 элементов могут быть использованы, я думал, подход к ускорению работы будет заключаться в использовании связанного списка вместо массива. И всякий раз, когда мне приходится искать элемент, как только я его найду, я поместил его в начало списка, чтобы в следующий раз, когда он появился, мне пришлось бы выполнить минимальное усилие поиска (цикла). Правильно ли это звучит?

EDIT1 Я не думаю, что бинарное дерево поиска идея действительно то, что я могу использовать, как я упорядочивания данных, как массив, т.е. каждый узел следующий предыдущий один больше, который поражения цели, не Это?

Я пытался решить мою проблему с кэшированием и придумал что-то вроде этого:

pending edit 

Но выход я получаю, говорит о том, что он не работает, как я хотел бы, чтобы это:

любые предложения о том, как я могу это улучшить?

Answer 1

Худший случай, ваш поиск по-прежнему O (N), если вы не отсортируете массив или список, как предложил Бретт. Поэтому с отсортированным списком вы увеличиваете сложность вставки (чтобы вставить упорядоченное), но ваш поиск будет намного быстрее. То, что вы предлагаете, похоже на «кеш». Нам сложно сказать, насколько полезной будет то, что будет без какой-либо идеи о том, как часто поиск найденного предмета снова выполняется в ближайшей перспективе. Очевидно, что есть преимущества для кеширования, поэтому мы имеем всю архитектуру L1, L2, L3 в памяти. Но будет ли это работать для вас, это неуверенно.

Answer 2

Ответ на Edit1: Я думаю, что если ваш элемент данных невелик, скажем, всего несколько байтов или даже десятки байтов, из них может быть установлено 4096 из них. В этом случае вам нужна хеш-таблица. В C++ вы используете unordered_map. Например, вы можете определить unorderedmap<int, ptr_to_your_node_type> и получить элемент в O(1), если ваш тип ключа int.

Самый быстрый поиск может быть 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; 
} 

};

Answer 3

Когда дело доходит до исполнения, существует только одно важное правило: измерьте его!

В вашем случае вы можете, например, иметь два разных соображения, теоретический анализ времени выполнения и то, что действительно происходит на машине. Оба они в значительной степени зависят от характеристик ваших 4096 предметов. Если ваши данные отсортированы, вы можете иметь поиск O (log n), если он несортирован, это худший случай O (n) и т. Д.

Что касается вашей идеи связанного списка, возможно, у вас больше недостатков в аппаратном кэше, поскольку данные больше не сохраняются вместе (пространственная локальность), что приводит к более медленной реализации, даже если ваше теоретическое рассмотрение является правильным.

Если вы заинтересованы вообще в таких проблемах, я рекомендую этот прохладный разговор с GoingNative 2013 http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly

Answer 4

Если ваши данные могут быть помещены в бинарном дереве поиска: http://en.wikipedia.org/wiki/Binary_search_tree

Затем вы можете использовать данные структура, называемая деревом Splay: «Дерево расщепления - это самонастраивающееся двоичное дерево поиска с дополнительным свойством, к которому недавно доступные элементы быстро получают доступ». http://en.wikipedia.org/wiki/Splay_tree