Можно ли отобразить строку в int быстрее, чем при использовании hashmap?

Question

Я понимаю, что не должен оптимизировать каждую часть моей программы, поэтому, пожалуйста, сочтите этот вопрос "академическим"

У меня есть максимум 100 строк и целое число для каждой из них, что-то вроде этого:

MSFT 1
DELL 2
HP   4
....
ABC  58

Этот набор предварительно инициализирован, что означает, что после его создания он никогда не изменяется. После того, как набор инициализирован, я использую его довольно интенсивно, поэтому приятно иметь быстрый поиск. Строки довольно короткие, максимум 30 символов. Подключенные int также ограничен и составляет от 1 до 100.

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

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

Есть ли готовые к использованию или простые в реализации решения для моей проблемы? Я использую C++ и Boost.

upd Я проверил и обнаружил, что для моего тикера лимит обмена составляет 12 символов, а не 30, как указано выше. Однако другие биржи могут допускать чуть более длинные символы, поэтому интересно иметь алгоритм, который будет продолжать работать с тикерами длиной до 20 символов.

Answer 1

Хеш-таблица ^[1] в принципе является самым быстрым способом.

Однако вы можете скомпилировать Perfect Hash Function, учитывая тот факт, что вы знаете весь домен заранее.

С идеальным хешем не должно быть столкновений, поэтому вы можете хранить хеш-таблицу в линейном массиве!

При правильной настройке вы можете тогда

• разместить все элементы хеша в ограниченном пространстве, что делает прямой адрес потенциальным вариантом
• иметь обратный поиск в O(1)

Инструментом старой школы для генерации функций Perfect Hash будет gperf (1). В википедии перечислено больше ресурсов на эту тему.

Из-за всех дебатов я запустил демонстрацию:

Загрузка символов тикера NASDAQ и получение 100 случайных выборок из этого набора с применением gperf следующим образом:

gperf -e ' \015' -L C++ -7 -C -E -k '*,1,$' -m 100 selection > perfhash.cpp

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

inline unsigned int Perfect_Hash::hash (register const char *str, register unsigned int len) {
  static const unsigned char asso_values[] = {
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156,  64,  40,   1,  62,   1,
       41,  18,  47,   0,   1,  11,  10,  57,  21,   7,
       14,  13,  24,   3,  33,  89,  11,   0,  19,   5,
       12,   0, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156, 156,
      156, 156, 156, 156, 156, 156, 156, 156, 156
    };
  register int hval = len;

  switch (hval) {
      default: hval += asso_values[(unsigned char)str[4]];   /*FALLTHROUGH*/
      case 4:  hval += asso_values[(unsigned char)str[3]];   /*FALLTHROUGH*/
      case 3:  hval += asso_values[(unsigned char)str[2]+1]; /*FALLTHROUGH*/
      case 2:  hval += asso_values[(unsigned char)str[1]];   /*FALLTHROUGH*/
      case 1:  hval += asso_values[(unsigned char)str[0]];   break;
  }
  return hval;
}

Это действительно не становится намного более эффективным. Посмотрите https://gist.github.com/sehe/5433535

Имейте в виду, это тоже идеальный хеш, поэтому столкновений не будет

---

Q. [...] это явно "DELL". Такой поиск должен быть значительно быстрее, чем "поиск по хэш-карте".

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

---

^[1] PS. Для 100 строк, отсортированный массив строк с std::search или же std::lower_bound потенциально будет так же быстро / быстрее из-за улучшенного местоположения ссылки. Посмотрите результаты своего профиля, чтобы увидеть, применимо ли это.

Answer 2

Небольшое дополнение к посту sehe:

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

Вы можете использовать поиск по префиксу, чтобы быть намного более эффективным. Проблема с обоими std::map и наивный бинарный поиск состоит в том, что они будут читать один и тот же префикс для каждого отдельного сравнения, делая общий поиск O (m log n), где m - длина строки поиска.

Это причина, по которой хеш-карта превосходит эти два метода для больших наборов. Однако существует структура данных, которая не выполняет избыточные сравнения префиксов, и фактически должна сравнивать каждый префикс ровно один раз: дерево префикса (поиска), более известное как trie, и поиск единственной строки длины m осуществимы в O (m) то же самое асимптотическое время выполнения вы получаете для хеш-таблицы с идеальным хешированием.

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

Answer 3

(Пока) Еще одно небольшое дополнение к sehe's ответ:

Помимо Perfect Hash Functions, есть эта функция Minimal Perfect Hash Function, и соответственно C Minimal Perfect Hash Function, Это почти так же, как gperf, Кроме этого:

gperf немного отличается, так как он был задуман для создания очень быстрых идеальных хеш-функций для небольших наборов ключей, а библиотека CMPH была задумана для создания минимальных идеальных хеш-функций для очень больших наборов ключей

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

источник: http://cmph.sourceforge.net/

Answer 4

Да!

Хеш должен пройти через вашу строку и построить хеш-значение. при использовании trie, как описано в ссылке [ Wiki: Trie], нужно только следовать по пути в связанной структуре без каких-либо перерасчетов. и если это сжатое три, как объяснено в конце страницы, он учитывает случай, когда инициал для одного слова (случай DELL, о котором вы говорили). предварительная обработка немного выше, но дает лучшую производительность во время выполнения.

еще несколько преимуществ:
1. если искомая строка не существует, вы знаете, что в первом символе, который отличается от существующих строк (не нужно продолжать вычисление)
2. после того, как реализовано, добавление большего количества строк в Trie является прямым.

Answer 5

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

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

Вы найдете обсуждение связанной темы "переключение на строку" на моем сайте, а также множество решений, использующих общий тестовый стенд с использованием макросов в качестве бесплатных источников C / C++, которые решают проблему во время выполнения. Я также думаю о прекомпиляторе.

Answer 6

Ну, вы можете хранить строки в двоичном дереве и искать там. Хотя это имеет O(log n) теоретически, на практике это может быть намного быстрее, если у вас есть только несколько клавиш, которые действительно длинные и уже отличаются по первым нескольким символам.

Т.е. при сравнении ключей дешевле вычисления хеш-функции.

Кроме того, существуют эффекты кэширования процессора, и такие, которые могут (или не могут) быть полезными.

Тем не менее, с довольно дешевой хэш-функцией, хеш-таблицу будет трудно превзойти.

Answer 7

Если строки известны во время компиляции, вы можете просто использовать перечисление:

enum
{
  Str1,
  Str2
};

const char *Strings = {
  "Str1",
  "Str2"
};

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

Тогда поиск может быть достигнут так же быстро, как индексация массива:

const char *string = Strings[Str1]; // set to "Str1"

Это будет иметь оптимальное время поиска и местность ссылки.