Это медленнее из-за двух поисков вместо одного?

Когда я хочу убедиться, что запись, которую я хочу использовать, существует, я обычно делаю это.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

if (map.find(key) != map.end())
    map[key].member = 42;

Однако, я думаю, что он выполняет два поиска для key в хэш-карте. Это кэширует поиск.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

auto find = map.find(key);
if (find != map.end())
    find->second.member = 42;

Первый вариант кажется более выразительным. Это действительно медленнее?

Ответы

Ответ 1

Да, потому что вы дважды просматриваете ключ: map[key] найдите ключ точно так же, как map.find, из которого вы отбросили результат.

Как открыть ящик, чтобы увидеть, есть ли данный объект, скажите "ай да!". и закройте ящик, затем откройте его снова и исследуйте объект, чтобы изменить его.

Второй код открывает ящик, ищет объект и меняет его.

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

Вся проблема, в сущности, уменьшит время сравнения двух хэш-вычислений (и пройдите в конечном слоте карты в случае хеш-столкновения) и время доступа к дополнительной переменной:

2*H < H+M

Это означает H < M. Если M является регистром, а H не является тривиальным, то для H трудно быть меньше M.

Ответ 2

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

Ответ 3

Да, это может быть медленнее, но, вероятно, не заметно медленнее. Существует несколько дополнительных работ:

  • Хэш скорее всего будет вычислен дважды, если у вас нет достаточно интеллектуального компилятора, используйте расширения поставщика, такие как pure или const или использовать аналогичный метод. Обратите внимание, что если хеш тривиален, а компилятор знает, что код, большинство компиляторов, вероятно, в настоящее время достаточно умны.
  • Положение ведра необходимо найти во второй раз (если компилятор не заметит, что это тот же хэш, поэтому его не нужно перекомпоновать)
  • Необходимо выполнить обход столкновений (или аналогичный метод в зависимости от разрешения столкновения). Опять же - достаточно умный компилятор может заметить, что мы делаем это дважды, мы фактически ничего не модифицируем и т.д. У нас могут быть такие компиляторы в настоящее время, но я не уверен на 100%, если мы там. Даже если они не являются кэшированными чтениями, и они, вероятно, не будут налагать никаких значительных затрат (по сравнению, например, с использованием хэша или пропущенного чтения). Не вдаваясь в подробности архитектуры процессора L1 $read hit занимает ~ 4 такта латентности на i7 (данные из памяти могут быть неправильными), и процессор может выполнять другую работу во время ожидания.

Итак, подытожим if:

  • Ваша хэш-функция дорогая (например, она должна принимать хэш строки).
  • Компилятор недостаточно умен, чтобы вывести, что хеш-функция не изменяет объект и действительно возвращает то же значение.
  • Код в внутреннем цикле.

тогда вы можете увидеть разницу.

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

Ответ 4

Если у вас есть определенная причина для сохранения значения в существующей записи (если она уже существует), вы можете полностью пропустить первый поиск и просто установить новое значение:

#include <unordered_map>

struct type { int member; };
std::unordered_map<key_t, type> map;

map[key].member = 42;

Это изменит существующую запись (если она есть) и вставьте новую запись, если она не существует.

Ответ 5

Да, это может быть медленнее. Если вы ищете что-то более выразительное, возможно, вы должны инкапсулировать std:unordered_map (что может быть хорошей идеей) и выставить указатель. Тогда вы можете написать что-то вроде:

auto thing = getThing(key);
if (thing) 
  thing->member = 42;