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

Уникальное целое/длинное хеш-генерация ключей над строками для более быстрого сравнения

Мне любопытно, как другие решили эту проблему, и какие проблемы могут скрываться за наивным решением:

У меня есть система, которая обрабатывает данные фондового рынка. Есть десятки тысяч символов с соответствующими ценами/размерами, втекающими в систему со скоростью несколько тысяч за миллисекунду.

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

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

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

EDIT: Я напишу этот код на Java. Не уверен в качестве (collision) качества hashCode или скорости, с которой он рассчитывается.

4b9b3361

ОТВЕТЫ

Ответ 1

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

Я предлагаю создать структуру данных Trie всех интересующих вас тикеров (см. http://en.wikipedia.org/wiki/Trie). Пройдите дерево по каждому символу, и если вы дойдете до конца тикера без поиска соответствия, то это не интересный тикер.

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

Ответ 2

Общие криптографические хэш-функции, такие как SHA-1, выходят 20 байтов (160 бит). Как долго ваши символы акций? Если мы говорим о символы тикера, такие как "WMT" (Walmart), "KO" (Coca-Cola) и т.д., Тогда они кажутся чтобы быть только пару байтов в длину - таким образом, нужно быстрее сравнивать их напрямую, вместо того, чтобы иметь дело с 20-байтовым хэшем. Вы упоминаете хэш-столкновений - я бы не стал беспокоиться о них, особенно если эти входы намного меньше, чем хэш-выход.

Возможно, вы сможете передать байты в int или long в зависимости от языка программирования и платформы, а затем выполнить сравнение между этими "числами" в одной инструкции CPU. (Я не знаю, могут ли современные компиляторы одинаково быстро сравнивать кучу байтов с вызовом memcmp?)

Ответ 3

Вам следует использовать Perfect hash function, я думаю, что он соответствует вашим требованиям

Ответ 4

Если вы используете String.intern() или свой собственный пул строк, вы можете использовать ==, а не .equals() - я сделал это с аналогичным критически важным кодом, и это имеет большое значение. Строка по умолчанию уже имеет hashCode(), который работает достаточно эффективно.

Я только понял, что это не вопрос Java, но то же самое. Да, хеширование, а затем использование проверки подлинности может сэкономить время. В алгоритме хэширования java используется:

     s[0] * 31^(n-1) + s[1] * 31^(n-2) + ... + s[n-1]

Ответ 5

Если вы получаете 4-буквенные символы тикера, каждая буква должна быть представлена ​​как один байт. Упакуйте все 4 вместе в 32-битный int и voila, у вас есть свой "хэш". Теперь вы можете сравнить это с ссылкой с помощью одной машинной инструкции.

Если вы не использовали Java, то есть.

Я бы действительно не предлагал использовать Java для чего-либо критически важного для скорости, особенно не для тысяч сравнений строк за миллисекунду.

edit: Если вы хотите использовать 64-битный код, вы можете упаковать до 8 букв на длинный int, а затем сравнить в 1 инструкции.

Ответ 6

Вы можете сгенерировать хеш, обработав строку как номер базы-27 (при условии, что символы содержат только буквы). Это создаст уникальность, которую вы ищете. Например:

(без буквы) = 0, A = 1, B = 2,... Z = 26

AA = (1 x 27 1) + (1 x 27 0) = 28

AAA = (1 x 27 2) + (1 x 27 1) + (1 x 27 0) = 757

BBB = (2 x 27 2) + (2 x 27 1) + (2 x 27 0) = 1514

GOOG = (7 x 27 3) + (15 x 27 2) + (15 x 27 1) + (7 x 27 0) = 149128

Это будет работать с точностью до 6 символов в 32-битном int.

Ответ 7

Что вы хотите - это быстрая хеш-функция, которая обладает хорошей способностью к дискриминации. Для каждой строки вычислите связанную хэш-функцию и сохраните ее со строкой. Затем для сравнения код:    if (Hash (s1) == Hash (s2)         & & s1 == s2)    тогда {... } Фактическое сравнение строк не произойдет, если не совпадают хэши, что на практике только когда строки совпадают.

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

Криптографические хеши имеют большую силу дискриминации, но не разработаны Быть быстрым. Что вообще очень быстро и имеет хорошую дискриминацию власть - это функции CRC, и большинство langauges легко находили библиотеки которые вычисляют их быстро (используя технику поиска таблицы в байтах). Мы используем CRC-32, и это очень эффективно для этого (в основном 1 шанс в 2 ^ 32, что произойдет хеш-столкновение, когда строки не совпадают). Вы можете использовать CRC-64, но дополнительная сила дискриминации он не добавит реальной функциональности.

Ответ 8

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

Но не пишите свою собственную хеш-функцию, используйте ту, что есть там.

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

Ответ 9

Изменить: лучшие комментарии, чем мои собственные, были брошены (и раньше), что делает мою резервную копию в лучшем случае.

Ответ 10

Во-вторых, вышеприведенное предположение о структуре Trie как наилучшем подходе для этого случая. Вычислимо эквивалентно совершенному хешу, но концептуально намного красивее. Это предполагает, что ваши символы ограничены по длине.

Ответ 11

FWIW, в последнем проекте с высоким объемом данных, в котором я был включен, мы обнаружили, что ключевыми являются фильтрация, агрегация и предварительная классификация данных с использованием некоторого сильно настроенного кода на C. Все наши каналы вошли в этот препроцессор, и он позаботился о простой очистке данных, прежде чем передавать основную часть данных в нашу Java-систему для обработки. В основном препроцессор сделал именно то, что вы просите: идентифицировать интересующие вас записи, проверить, что они были полными, и удалить дубликаты и опорожнения. В пиковые времена препроцессор мог устранить до 20% от 8М или около того записей, которые мы получали бы в час (вероятно, не совсем того объема, который, я думаю, вы получаете из фидов фондового рынка). Наша оригинальная версия Java была удачной, чтобы получить половину этого (но это было "элегантно", по крайней мере!)

Ответ 12

За что его стоит. Я решил эту проблему, характерную для символики CMS (NYSE) и CQS (NASDAQ). Корни символов будут длиной не более 6 символов и будут иметь верхний регистр. Мои требования были следующими:

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

Например, если данные для GOOG поступают, их необходимо обработать и распределить по процессам в диапазоне символов [F-HAA]. (F <= GOOG <= HAA). Я использовал класс диапазона, который имеет низкое значение (F) и высокое значение (HAA). Моя концепция функции Hash похожа на упаковку символов в байты, но для ведения журналов, сетей и для конечных целей я выбрал unsigned long long, как мой тип хранилища. Перед вызовом этой функции символы заполняются символом "@". (IBM @@@)

unsigned long long SymbolToVal(std::string& str)
{
 size_t maxlen = 6; // Symbology constraint
 if (str.length() != maxlen) return 0;
 unsigned long long val;
 unsigned long long retval=0;
 int expon = maxlen*2; // ASCII val range (65-90)
 double factor = std::pow(10.0,expon);
 expon-=2;
 for (size_t i = 0; i < maxlen; i++)
 {
    val = (unsigned long long)factor * str[i];
    retval += val;
    factor = (unsigned long long) std::pow(10.0,expon);
    expon-=2;
  }
  return retval;
 }

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