Альтернатива stdext :: hash_map по соображениям производительности

Question

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

Ключ на карте ниже - это std :: string, но он может измениться на массив символов, если это необходимо. C или C ++ в качестве решения в порядке.

  typedef stdext::hash_map<std:string, int> symbols_t;

Кто-нибудь знает какие-либо другие решения, которые устранят поиск или будут быстрее?

Заранее спасибо за помощь.

Дополнительная информация от правок:
1. В настоящее время hash_map содержит 350 000 элементов.
2. Каждое значение ключа обычно имеет длину от 4 до 10 символов.
3. Информация поступает по обратному вызову от стороннего API. Обратному вызову присваивается символ, который используется в качестве значения ключа при поиске карты. Остальная часть программного обеспечения извлекается из int, возвращаемого из поиска карты.

СПАСИБО: Спасибо всем за ваш вклад. Вы дали мне несколько возможностей для изучения. Я обязательно попробую это. Я ценю помощь.

Answer 1

Хеш-таблица обычно достаточно быстрая O (1), и мы не можем сказать вам, можете ли вы избавиться от хеш-таблицы, не зная всей структуры вашего приложения.Это может быть невозможно.

Я не знаю, как реализовано stdext::hash_map<std::string,T>, но дерево префиксов , возможно, лучше решение.Это эквивалентно хеш-таблице с идеальной хеш-функцией.

      s
      |
      t
    /   \
   o     a
   |     |
(p,42)   r
         |
       (t,69)

Она даст вам значение, соответствующее вашей строке, за O (1) максимум 10 итераций (максимальная длина строки) и сведет к минимумустоимость места хранения ключей.

Answer 2

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

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

Answer 3

Вот статья о производительности hash_map, где представлена ​​замена вставки, которая должна работать намного лучше:

http://www.codeproject.com/KB/cross-platform/BenchmarkCppVsDotNet.aspx

Вот список других тестов производительности:

http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/ http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/
http://tinodidriksen.com/2009/10/04/cpp-map-speeds-msvc-edition/

Опытный, что std_ext :: hash_map работал плохо, когда более 25.000 элементов, где поиск замедлялся с увеличением количества элементов Изменение в boost :: unordered_map решило проблему.

Answer 4

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

Что касается производительности, то использовать или нет hash_map зависит от некоторых сложностей. Hashmaps имеют (если у вас есть хорошая реализация, реально) O (1) поиск, вставка. Но постоянные накладные расходы могут быть довольно высокими. Если у вас мало записей, вы можете пострадать здесь и получить пользу от std :: map. Вы также можете страдать от проблем когерентности кэша, если часто обращаетесь ко многим различным элементам карты и вместо этого можете рассмотреть какой-то отсортированный массив.

Answer 5

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

struct CustomStringHash: std::unary_function<std::string, size_t>
{
    size_t operator()(const std::string & s) const
    {
         switch (s.size())
         {
              case 0:
                   return 0;
              case 1:
                   return s[0] + 1;
              case 2:
                   return (s[0] << 8) + s[1];
              default: //3 or more chars long, plus a terminating null
                   return *reinterpret_cast<const uint32_t *>(s.c_str());
         }
    }

Если ваши строки в среднем имеют 8-12 символов и в основном уникальны для первых четырех символов, то настройка хеш-функции может значительно ускорить поиск.

Answer 6

Код вручную хэш-карты, которая больше соответствует вашим данным.

1. достаточно простая хеш-функция
2. используйте разреженный массив C, достаточно большой, чтобы не было коллизий для ваших данных
3. убедитесь, что все звонки встроены
4. Убедитесь, что вы никогда не копируете и не конвертируете строки

5. Написать код для генерации C-источника для этого массива C. Это будет выглядеть (используя 0 для отсутствия записи):

   int symbols[] = { 0,0,0,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,0,2 /* etc */ };
   

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

Индекс массива simple_hash(string& s)

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

РЕДАКТИРОВАТЬ: на основе ответа @ Blaze - код в # 5 написан для вас и называется gperf

Answer 7

Я бы сказал, что у нас здесь недостаточно информации, чтобы надежно сказать вам, что делать.

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

Если вы загромождаете код уродливыми взломами, чтобы выиграть 1 постоянную микросекунду в функции, алгоритмическая стоимость которой равна O(n²), где она может быть O(n), вы тратите свое время на неправильную проблему.

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