Блог

Главная - Вопросы по программированию - Более быстрый способ вставки в неупорядоченную карту

Более быстрый способ вставки в неупорядоченную карту

#c

#c

Вопрос:

У меня есть неупорядоченная карта, точно такая же, как:

 std::unordered_map < std::string, std::vector<std::string> > m_unordered_map;

При вставке в нее значений, что из следующего будет быстрее и почему?

Подход 1 (скелет):

 std:string key = "key";
for (int i = 0; i < n;   i) {
  std::string value = std::to_string(i); // Value would be acually an big string.
  m_unordered_map[key].push_back(value1);
}

Подход 2 (скелет)

 std:string key = "key";
std::vector<std::string> vec;
for (int i = 0; i < n;   i) {
  std::string value = std::to_string(i); // Value would be acually an big string.
  vec.insert(value);
}
m_unordered_map.insert({key, vec});

Или есть лучший подход для этого?

Комментарии:

1. почему бы вам не рассчитать время для вашего конкретного варианта использования и посмотреть, что быстрее?

2. @SamerTufail, я нашел подход 2 как более быстрый в моей среде. Сказав это, для тестирования среды выполнения у меня нет выделенной машины, которая могла бы подтвердить мне правильные номера времени выполнения. Кроме того, намерение состоит в том, чтобы ознакомиться и с другими подходами. Имеет смысл?

3. @SamerTufail По-видимому, потому, что синхронизировать такие вещи надежно и таким образом, чтобы это соответствовало реальным данным, на самом деле довольно сложно.

Ответ №1:

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

Вы можете дополнительно улучшить его, переместив вместо копирования строку и векторы. например

 std::string key = "key";
std::vector<std::string> vec;
for (int i = 0; i < 10;   i) {
    vec.emplace_back(std::to_string(i));
}
m_unordered_map.emplace(key, std::move(vec));

В общем:

  • Доступ к an unordered_map по-прежнему довольно медленный, особенно с такими ключами, как std::string . Для «попадания» это будет стоить вам O (n) хэша длины ключей и O (n) сравнения строк. Не только O(1) для самой хэш-таблицы. Если вы можете получить к нему доступ только один раз, возможно, сохраните итератор / ссылку, которая будет быстрее (проверьте правила недействительности итератора. insert может привести к аннулированию других итераторов в an unordered_map , поэтому будьте осторожны, но это не приведет к аннулированию ссылок на значения). Если вы можете полностью заменить строку, скажем, целочисленным идентификатором, это также обычно будет быстрее.
  • Избегайте копирования объектов, таких как карты, строки и векторы. По возможности переместите их. Помимо стоимости копирования данных, копирование контейнеров может привести к большому количеству сравнительно дорогих выделений памяти.

Ответ №2:

Улучшение ваших 2 подходов:

Подход 1 (скелет):

 std:string key = "key";
autoamp; vec = m_unordered_map[key];
vec.reserve(n);
for (int i = 0; i != n;   i) {
    vec.push_back(std::to_string(i));
}

Подход 2 (скелет)

 std:string key = "key";
std::vector<std::string> vec;
vec.reserve(n);
for (int i = 0; i != n;   i) {
    vec.push_back(std::to_string(i));
}
m_unordered_map[key] = std::move(vec));

Итак

  • выполните только один поиск
  • Используйте перемещение вместо копирования.

Со своей стороны, я бы создал метод для построения вектора, что-то вроде:

 std::vector<std::string> create_iota_strings(std::size_t n)
{
    std::vector<std::string> vec;
    vec.reserve(n);
    for (std::size_t i = 0; i != n;   i) {
        vec.push_back(std::to_string(i));
    }
    return vec;
}

а затем просто

 m_unordered_map[key] = create_iota_strings(n);

insert / emplace может быть более подходящим, чем operator[] если вы знаете, что key еще не существует.
Если ключ может существовать try_emplace , было бы решением избежать построения пустого вектора (когда ключ не существует).