как отобразить специализированную строку в указанное целое число
Я занимаюсь финансовой торговлей. У меня есть набор биржевых символов, но они имеют очень четкую структуру:
он состоит из двух символов AB, AC AD и текущий месяц, который является четырехзначным числом: 1503, 1504, 1505, Вот некоторые примеры:
AB1504
AB1505
AC1504
AC1505
AD1504
AD1505
....
Поскольку эти строки очень хорошо спроектированы по шаблону, я хочу отобразить (хэш) каждую строку в уникальное целое число, чтобы я мог использовать целое число в качестве индекса массива для быстрого доступа, так как у меня много обращений в моей системе и std::unordered_map или любая другая хэш-карта не достаточно быстра. У меня есть тесты, показывающие, что общая хэш-карта имеет уровень задержки в 100 наносекунд, в то время как индексирование массива всегда меньше 100 наносекунд.
мой идеальный случай был бы, например, AB1504 отображается в целое число 1, AB1505
карты для 2…., тогда я могу создать массив внутри, чтобы получить доступ к информации, связанной с этими символами гораздо быстрее.
Я пытаюсь выяснить некоторые алгоритмы хеширования или другие методы, которые могут достичь моей цели, но не могут найти.
Ребята, у вас есть предложения по этой проблеме?
Решение
Вы можете рассматривать строку как представление числа с переменной базой и конвертировать ее в целое число. Например:
AC1504:
A (range: A-Z)
C (range: A-Z)
15 (range: 0-99)
04 (range: 1-12)
Извлечь части; тогда хеш-функция может быть
int part1, part2, part3, part4;
...
part1 -= 'A';
part2 -= 'A';
part4 -= 1;
return (((part1 * 26 + part2) * 100 + part3) * 12 + part4;
Другие решения
Следующие значения должны быть представлены 32-разрядным целым числом:
XYnnnn => (26 * X + Y) * 10000 + nnnn
Вот X а также Y принимать значения в диапазоне [0, 26) и n принимает значения в диапазоне [0, 10).
Всего у вас есть 6 760 000 представимых значений, поэтому, если вы хотите связать с ним только небольшой объем данных (например, счетчик или указатель), вы можете просто создать плоский массив, где каждый символ занимает одну запись массива.
Если вы проанализируете строку как смешанное базовое число, сначала 2 цифры из 26 цифр, а затем 4 цифры из 10 цифр, вы быстро получите уникальный индекс для каждой строки. Единственная проблема заключается в том, что если вы можете получить малонаселенный массив.
Вы всегда можете изменить порядок цифр при расчете индекса, чтобы минимизировать проблему, упомянутую выше.
Поскольку числа на самом деле являются месяцами, я бы вычислил количество месяцев из первой записи и умножил бы это на двузначное число base-26 из префикса.
Надеюсь, в этом вы сможете разобраться, набрав на моем планшете в данный момент. : D
Я предполагаю, что формат «AAyymm», где A — это заглавный символ yy двухзначный год, а mm двухзначный месяц.
Следовательно, вы можете сопоставить его с 10 (AA) + Y (yy) + 4 (mm) битами. где Y = 32 — 10 — 4 = 18 бит для 32-битного представления (или 262144 года).
Имея это, вы можете представить формат как целое число, сместив символы туда-сюда и сместив пары года и месяца туда-сюда после преобразования их в целое число.
Примечание: в двоичном представлении всегда будут пробелы, здесь 5 + 5-битное представление для символов (6 + 6 значений) и в 4-битном представлении месяца (4 значения)
Чтобы избежать пропусков, измените представление на ABmmmm, где пара AB представлена числом 26 * A + B, а mmmm — это месяц относительно нулевого месяца в каком-либо году (который охватывает 2 ^ 32/1024/12 = 349525 лет — имея 32 бита).
Тем не менее, вы можете рассмотреть разделение биржевых символов и времени. Объединение двух значений в одном поле обычно проблематично (это может быть хороший формат хранения, но не хороший «формат данных программы»).