Неупорядоченная карта для уникальных ключей и хеширования

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

  • Имена являются постоянными и инициализируются строковыми литералами. Они известны во время компиляции.
  • Два имени, которые были инициализированы разными строками, должны сравниваться по-разному, независимо от их внутреннего представления.
  • Имена могут быть произвольной длины. Моя библиотека не устанавливает никаких ограничений.
  • Практически не должно быть ограничений на возможные имена. Ограничения реализации не должны влиять на интерфейс, поэтому, опять же, никаких ограничений с моей стороны.

Учитывая, что частый поиск будет происходить, я подумал об использовании неупорядоченной карты.

Неупорядоченные ассоциативные контейнеры хранят свои элементы, независимо от их типа, по номерам (обычно типа std::size_t), которые получаются с помощью хэш-функции. Это означает, что:

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

Я думал о двух решениях.

Хеширование по значению

Использование самих данных для вычисления значения хеша. Соображения:

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

Хеширование по заказу

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

  1. Когда имя создается (из строкового литерала), таблица просматривается (выполняется точное сравнение).
    • Если он не найден, он регистрируется в конце контейнера.
  2. Смещение его записи в таблице становится его хеш-значением.

Соображения:

  • Очень медленно. Для каждого созданного имени необходимо выполнить столько строковых сравнений, сколько зарегистрированных имен. Это не намного лучше, чем традиционный std::map, это?
  • Тема небезопасна. Стол должен быть защищен.
  • Принудительно сделано во время выполнения.

Вопросы

  1. Правильно ли использовать неупорядоченную карту в этих условиях? Было бы лучше использовать std::map вместо?
  2. Если 1 - "да", какой подход лучше и почему? Тот, который используется в Boost.Log, кажется действительно неэффективным, почему он используется вместо другого, который я объяснил, даже если строки не обязательно известны во время компиляции?

Примечание: я не добавил c++14 тег, хотя у меня есть доступ к экспериментальной поддержке, предлагаемой gcc и clang. Пожалуйста, не стесняйтесь использовать функции, включенные в следующую спецификацию.

Источник

2 ответа

Решение

Правильно ли использовать неупорядоченную карту в этих условиях? Было бы лучше использовать std::map вместо?

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

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

Если 1 - "да", какой подход лучше и почему? Тот, который используется в Boost.Log, кажется действительно неэффективным, почему он используется вместо другого, который я объяснил, даже если строки не обязательно известны во время компиляции?

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

Возможная реализация:

// You stated that names were constant and constructed from string literals.
// Borrowed from the example at http://en.cppreference.com/w/cpp/language/constexpr
class
    name final
{
    private:
        const char * const
            s; // string
        const std::size_t
            l; // length

    public:
        template<std::size_t N> constexpr
            name
            ( const char (& s)[N] )
            noexcept
            : s( s ) , l( N-1 )
            { }

        // Interface that enables hashing algorithms to operate on your class.
        // If hashing is to happen at compile-time, the methods must be
        // declared `constexpr`.
};

struct
    hasher final
{
    constexpr std::size_t
        operator()
        ( const name & n )
        const noexcept
        {
            return 0; // read below
        }
};

Вам нужно будет реализовать интерфейс для алгоритмов хеширования для доступа к данным, лежащим в основе вашего name учебный класс. Кроме того, как указано в примере, методы должны быть constexpr-declared; в противном случае они не могут быть вызваны из вашего constexprВключенная функция хеширования. Что касается алгоритмов хеширования, их существует множество, каждый из которых соответствует некоторым обстоятельствам. На этой странице подробно рассматривается тема и представлена ​​реализация X65599, которая, однако, не использует constexpr, Вы можете попробовать это сначала и проверить, как он ведет себя в вашей ситуации.

Источник

Правильно ли использовать неупорядоченную карту в этих условиях? Было бы лучше использовать вместо него std::map?

Если вам не нужно заказывать записи, обычно более эффективно использовать unordered_map чем map, Поскольку оба имеют почти идентичный интерфейс, это, конечно, очень легко измерить (что вам следует сделать).

Если 1 - "да", какой подход лучше и почему? Тот, что используется в Boost.Log, кажется действительно неэффективным, почему он используется вместо другого, который я объяснил, даже если строки не обязательно известны во время компиляции?

Вы должны прочитать документацию Boost немного лучше. Я ничего не читал о поисках линейной сложности. Описание attribute_set предлагает использовать ассоциативный контейнер (я ожидаю, что std::unordered_map, но вы можете проверить исходный код самостоятельно). Причина использования идентификатора, а не строки, также четко указана в документации:

"Работа с идентификаторами намного эффективнее, чем со строками. Например, копирование не требует динамического выделения памяти, а операторы сравнения очень легкие".

Будет ли это полезно в вашем случае, зависит от того, как вы используете эти структуры данных. Поскольку вы указываете, что строковые идентификаторы могут быть представлены в виде строковых литералов (но учтите, нужно ли вам переводить эти строки), вам нужно всего лишь передать указатель, чтобы скопировать строковый идентификатор. Тем не менее, сравнение будет по-прежнему медленнее, чем с boost::attribute_names.

Источник
Другие вопросы по тегам