Почему карта будет намного быстрее, чем unordered_map?

Я реализовал результаты кэширования поиска, которые состоят из ключей типа State (класс с 7 короткими ints) и значений типа Socre (класс из 3 удваивается). Использование unordered_map было как минимум в 20 раз медленнее, чем карта. Почему?

Редактировать: Darn it! Моя хэш-функция была

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

Я забыл return retval, так что все это столкнулось! Я хочу, чтобы unordered_map имел функцию hash_function_quality(), которая сообщает о среднем числе столкновений.

Ответы

Ответ 1

Скорость unordered_map прямо пропорциональна скорости вашей хеширующей функции. Это никогда не прямые отношения. Например, если вы используете простейшую функцию хеширования:

std::size_t myHash(MyObjectType _object){ return 1; }

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

Что вам нужно сделать, это посмотреть на две вещи:

  • Какую функцию хеширования вы используете? Стоит ли смешное количество времени для обработки?
  • Сколько коллизий производится? То есть, сколько уникальных элементов сопоставляется с одним и тем же значением хеша?

Либо каждый из них может и может убить производительность.

Ответ 2

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

Ответ 3

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

std::map, с другой стороны, проще, чем std::unordered_map. Время, необходимое для доступа к элементу, зависит от количества элементов, но все меньше и меньше, так как число элементов растет. А большой коэффициент c для std:: map тоже очень мал, по сравнению с std::unordered_map.

В общем, предпочитайте использовать std::map над std::unordered_map, если у вас нет конкретной причины использовать std::unordered_map. Это особенно важно, если у вас нет большого количества элементов.

Ответ 4

Для

Я хочу, чтобы unordered_map имел hash_function_quality(), которая сообщает среднее число столкновения.

Я думаю, что следующая функция может быть полезна.

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

Опустите load_factor, лучше хеш-функция.