Подтвердить что ты не робот

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

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

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

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

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Вы могли компилировать Perfect Hash Function, учитывая тот факт, что вы знаете полный домен раньше времени.

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

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

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

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

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

Загрузка символов NASAQ ticker и получение 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;
}

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

Помните, что это идеальный хэш, так что будет без столкновений

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

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

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

Ответ 2

Небольшое дополнение к сообщению:

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

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

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

Является ли таблица хешей trie или (direct lookup) с идеальным хешированием более эффективной для вашей цели, является вопрос профилирования.

Ответ 3

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

т.е. при сравнении клавиш дешевле, чем вычисление хэш-функции.

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

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

Ответ 4

Да!

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

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

Ответ 5

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

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

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

Ответ 6

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

enum
{
  Str1,
  Str2
};

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

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

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

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

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