C ++ некоторые вопросы по boost :: unordered_map & boost :: hash

Question

Я только недавно начал изучать boost и его контейнеры, и я прочитал несколько статей в Интернете и stackoverflow, что boost :: unordered_map является самым быстродействующим контейнером для больших коллекций.Итак, у меня есть этот класс State, который должен быть уникальным в контейнере (без дубликатов), и в контейнере будут миллионы, если не миллиарды состояний.Поэтому я пытался оптимизировать его для небольшого размера и как можно меньшего количества вычислений.Раньше я использовал boost :: ptr_vector, но когда я читаю на stackoverflow, вектор хорош только до тех пор, пока в нем не так много объектов.В моем случае State десорбирует сенсорно-моторную информацию от робота, поэтому может быть огромное количество состояний, и поэтому быстрый поиск имеет первостепенное значение.Следуя документации boost для unordered_map, я понимаю, что я могу сделать две вещи, чтобы ускорить процесс: использовать hash_function и использовать оператор равенства для сравнения состояний на основе их hash_function.Итак, я реализовал приватную функцию hash (), которая получает информацию о состоянии и, используя boost :: hash_combine, создает хеш-значение std :: size_t.Оператор == сравнивает в основном хэш-значения состояния.Итак:

• достаточно ли std :: size_t для покрытия миллиардов возможных комбинаций hash_function?Чтобы избежать повторяющихся состояний, я намерен использовать их hash_values.

• При создании state_map я должен использовать в качестве ключа State * или значение хеш-функции?то есть: boost::unordered_map<State*,std::size_t> state_map; Или boost::unordered_map<std::size_t,State*> state_map;

• Являются ли времена поиска с boost :: unordered_map :: iterator = state_map.find () быстрее, чем прохождение boost :: ptr_vector исравнивать значение ключа каждого итератора?

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

РЕДАКТИРОВАТЬ: я видел довольно много ответов, один из которых не для повышения, но C ++ 0X, другой не для использования unordered_set, но, если честно, я все еще хочу увидеть, как используется boost :: unordered_setс хэш-функцией.Я следил за документацией Boost и реализовал ее, но все еще не могу понять, как использовать хэш-функцию boost с упорядоченным набором.

Answer 1

Это немного запутано.

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

• Вам необходимопредоставить оператор равенства, который сравнивает объекты , а не хеш-значения.Весь смысл равенства состоит в том, чтобы различать элементы с одинаковым хешем.

• size_t - это целочисленный тип без знака, 32 бита на x86 и 64 бита на x64.Поскольку вам нужны «миллиарды элементов», что означает много гигабайт данных, я предполагаю, что у вас все равно есть надежная машина x64.

• Важно, чтобы ваша хеш-функция была хорошей, то есть имеет несколько столкновений.

• Вы хотите набор, а не карту.Поместите предметы прямо в набор: std::unordered_set<State>.Используйте карту, если вы отображаете на что-то, то есть указывает на что-то еще.О, используйте C ++ 0x, не буст, если можете.

• Использование hash_combine - это хорошо.

---

Малышпример:

struct State
{
  inline bool operator==(const State &) const;
  /* Stuff */
};

namespace std
{
  template <> struct hash<State>
  {
    inline std::size_t operator()(const State & s) const
    {
      /* your hash algorithm here */
    }
  };
}

std::size_t Foo(const State & s) { /* some code */ }

int main()
{
  std::unordered_set<State> states; // no extra data needed
  std::unordered_set<State, Foo> states; // another hash function
}

Answer 2

забудь про хеш; нет ничего (по крайней мере, из вашего вопроса), которое предполагает, что у вас есть значимый ключ;

Давайте сделаем шаг назад и перефразируем ваши фактические цели производительности:

• вы хотите быстро проверить, не существует ли дубликатов ни для одного из ваших объектов State

комментарий, если мне нужно добавить другие.

Исходя из вышеупомянутой цели и вашего комментария, я бы предложил вам использовать orders_set вместо unordered_map. Да, упорядоченный поиск использует бинарный поиск O (log (n)), в то время как неупорядоченный использует поиск O (1).

Однако, разница в том, что при таком подходе вам нужно order_set ONLY , чтобы проверить, что подобное состояние уже не существует , когда вы собираетесь создать новое , то есть в состоянии время создания .

В всех других поисках вам на самом деле не нужно заглядывать в order_set! потому что у вас уже есть ключ; Состояние *, и ключ может получить доступ к значению с помощью оператора магического разыменования: * ключ

так что при таком подходе вы используете order_set только как index для проверки состояний только на время создания. Во всех остальных случаях вы получаете доступ к вашему состоянию с помощью оператора разыменования вашего ключа-указателя.

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

Чтобы это работало, вам, очевидно, нужен предикат сравнения для проверки всех внутренних свойств вашего состояния (гироскоп, двигатели, акселерометры, протонные лучи и т. Д.)

Answer 3

unordered_map - это хеш-таблица. Вы не храните хэш; это делается внутренне как метод хранения и поиска.

Учитывая ваши требования, может быть более подходящим unordered_set, так как ваш объект - единственный элемент для хранения.

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

std :: size_t подходит для хэш-функции. Помните, что хеш не идеален; будут столкновения, и эти элементы столкновений будут сохранены в связанном списке в той позиции корзины.

Таким образом, .find () будет O (1) в оптимальном случае и очень близко к O (1) в среднем случае (и O (N) в худшем случае, но приличная хеш-функция позволит избежать этого .)

Вы не упоминаете свою платформу или архитектуру; при миллиардах записей вам все же придется беспокоиться о нехватке памяти в зависимости от них и размера вашего объекта State.