Выбор между std :: vector и std :: unordered_map Для поиска в нескольких случаях?

Question

Есть несколько элементов для повторения и поиска по ключу. И я уже составляю std::vector для итерации. Мне нужно сформировать struct для поиска, например std::unordered_map?

Я знаю, что поиск в std::vector привел к O(N) и выполнен в std::unordered_map приведено в O(1). Но элементы внутри около 10. Никакая вставка или обновление не произошло после инициализации. Я могу искать много раз. Может быть, 1 миллион, 1 миллиард или даже больше, я не могу этого сделать.

Я обеспокоен тем, что хеширование может быть дороже, чем итерация.

Вот пример:

class Item 
{ 
public: 
    int key; 
    const char* value; 
}; 

class Items 
{ 
public: 
    Items(const std::vector<const Item> items) 
    : _vector(items) 
    , _map(generateMap()){ 
    } 

    const char* getValueByKey(int key) const { 
     //which one to choose 
     //map 
//  const auto& iter = _map.find(key); 
//  if (iter!=_map.end()) { 
//   return iter->second; 
//  } 
//  return nullptr; 
     //vector 
     for (const auto& iter : _vector) { 
      if (iter.key==key) { 
       return iter.value; 
      } 
     } 
     return nullptr; 
    } 

protected: 
    const std::unordered_map<int, const char*> generateMap() const{ 
     std::unordered_map<int, const char*> map; 
     for (const auto& item : _vector) { 
      map.insert({item.key, item.value});//I can make sure that no same key will exists 
     } 
     return map; 
    } 

    const std::vector<const Item> _vector; 
    const std::unordered_map<int, const char*> _map;//Is it necessary? 
}; 

int main() 
{ 
    const std::vector<const Item> items ={ 
     {1, "value_1"}, 
     {20, "value_2"}, 
     {10, "value_3"}, 
     {55, "value_4"}, 
    }; 
    Items theItems = items; 
    srand(time(nullptr)); 
    for (int i = 0; i < 1000000; i++) { 
     int key = rand(); 
     printf("%d %s exists\n", key, theItems.getValueByKey(key)==nullptr?"is not":"is"); 
    } 
    return 0; 
} 

Вот int ключевой случай, может быть, не хеширования не произошло. Но как насчет других случаев, std::string, пользовательский struct и так далее?

Итак, как я должен принять мое решение для такого рода случая теоретически?

Answer 1

Если вы не собираетесь менять данные, и вам нужно сделать много запросов, я предлагаю вам попробовать использовать std:vector и сортировать его. Затем вы можете использовать алгоритм поиска, такой как binary_search, lower_bound или upper_bound из STL, используя тот факт, что контейнер отсортирован.

Вы получаете лучшее: как местность, так и сложность O (log (N)).

Answer 2

Политически правильный ответ - «эталон!».

Но, основываясь на опыте других людей, когда используется только небольшое количество предметов относительно небольшого размера, использование std::vector обычно выполняется быстрее (особенно если оно сортируется), поскольку оно улучшает локальность памяти ваших предметов и не использует дополнительные распределения/освобождения кучи для своих предметов. Однако, если ключ является чем-то вроде std::string, а ключевые сравнения выполняются с использованием его содержимого, то это, конечно, может повредить локальность памяти, поскольку содержимое строки не всегда (всегда) содержится в самом объекте строки, но в куче ,

Answer 3

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

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

Answer 4

Я бы посмотрел boost::flat_map, который предоставляет интерфейс карты над векторной реализацией.

Независимо от сложности Big O, факт заключается в том, что ваше оборудование будет работать намного лучше с вектором, чем с картой, из-за местоположения данных и предварительной выборки данных из основной памяти.

Цитирование Chandler Каррут, «Карты упражнением в замедляя код»