Лично я бы просто сгенерировал таблицу с gperf или для большого количества ключей с CMPH и покончил бы с этим.
Если вы должны сделать это в Python, то я нашел это сообщение в блоге с некоторым кодом Python 2, который очень эффективен для превращения ключей string в минимальный идеальный хэш с использованием посредника.Таблица.
Приспосабливая код в посте к вашим требованиям, вы получаете минимальный идеальный хэш для 50 тыс. Элементов менее чем за 0,35 секунды:
>>> import random
>>> testdata = {random.randrange(2**64): random.randrange(2**64)
... for __ in range(50000)} # 50k random 64-bit keys
>>> import timeit
>>> timeit.timeit('gen_minimal_perfect_hash(testdata)', 'from __main__ import gen_minimal_perfect_hash, testdata', number=10)
3.461486832005903
Изменения, которые я сделал:
- Я перешел на Python 3, следовал руководству по стилю Python и сделал код более Pythonic
- Я превращаю 64-разрядные целые числа без знака в 8-байтовые строки с
int.to_bytes() - Вместо хранения отрицательных чисел я использую флаг, чтобы различать прямые и хеш-значения в промежуточной таблице
Адаптированный код:
# Easy Perfect Minimal Hashing
# By Steve Hanov. Released to the public domain.
# Adapted to Python 3 best practices and 64-bit integer keys by Martijn Pieters
#
# Based on:
# Edward A. Fox, Lenwood S. Heath, Qi Fan Chen and Amjad M. Daoud,
# "Practical minimal perfect hash functions for large databases", CACM, 35(1):105-121
# also a good reference:
# Compress, Hash, and Displace algorithm by Djamal Belazzougui,
# Fabiano C. Botelho, and Martin Dietzfelbinger
from itertools import count, groupby
def fnv_hash_int(value, size, d=0x811c9dc5):
"""Calculates a distinct hash function for a given 64-bit integer.
Each value of the integer d results in a different hash value. The return
value is the modulus of the hash and size.
"""
# Use the FNV algorithm from http://isthe.com/chongo/tech/comp/fnv/
# The unsigned integer is first converted to a 8-character byte string.
for c in value.to_bytes(8, 'big'):
d = ((d * 0x01000193) ^ c) & 0xffffffff
return d % size
def gen_minimal_perfect_hash(dictionary, _hash_func=fnv_hash_int):
"""Computes a minimal perfect hash table using the given Python dictionary.
It returns a tuple (intermediate, values). intermediate and values are both
lists. intermediate contains the intermediate table of indices needed to
compute the index of the value in values; a tuple of (flag, d) is stored, where
d is either a direct index, or the input for another call to the hash function.
values contains the values of the dictionary.
"""
size = len(dictionary)
# Step 1: Place all of the keys into buckets
buckets = [[] for __ in dictionary]
intermediate = [(False, 0)] * size
values = [None] * size
for key in dictionary:
buckets[_hash_func(key, size)].append(key)
# Step 2: Sort the buckets and process the ones with the most items first.
buckets.sort(key=len, reverse=True)
# Only look at buckets of length greater than 1 first; partitioned produces
# groups of buckets of lengths > 1, then those of length 1, then the empty
# buckets (we ignore the last group).
partitioned = (g for k, g in groupby(buckets, key=lambda b: len(b) != 1))
for bucket in next(partitioned, ()):
# Try increasing values of d until we find a hash function
# that places all items in this bucket into free slots
for d in count(1):
slots = {}
for key in bucket:
slot = _hash_func(key, size, d=d)
if values[slot] is not None or slot in slots:
break
slots[slot] = dictionary[key]
else:
# all slots filled, update the values table; False indicates
# these values are inputs into the hash function
intermediate[_hash_func(bucket[0], size)] = (False, d)
for slot, value in slots.items():
values[slot] = value
break
# The next group is buckets with only 1 item. Process them more quickly by
# directly placing them into a free slot.
freelist = (i for i, value in enumerate(values) if value is None)
for bucket, slot in zip(next(partitioned, ()), freelist):
# These are 'direct' slot references
intermediate[_hash_func(bucket[0], size)] = (True, slot)
values[slot] = dictionary[bucket[0]]
return (intermediate, values)
def perfect_hash_lookup(key, intermediate, values, _hash_func=fnv_hash_int):
"Look up a value in the hash table defined by intermediate and values"
direct, d = intermediate[_hash_func(key, len(intermediate))]
return values[d if direct else _hash_func(key, len(values), d=d)]
выше создает два списка с 50k записей в каждом;значения в первой таблице - это (boolean, integer) кортежи с целыми числами в диапазоне [0, tablesize) (теоретически значения могут варьироваться до 2 ^ 16, но я был бы очень удивлен, если бы когда-либо потребовалось 65k + попыток найти расположение слотовдля ваших данных).Размер вашей таблицы <50 КБ, поэтому приведенная выше схема позволяет сохранять записи в этом списке в 4 байта (<code>bool и short составляют 3, но правила выравнивания добавляют заполнение одним байтом), когдавыражая это как массив C.
Быстрый тест для проверки правильности хеш-таблиц и получения правильного результата снова:
>>> tables = gen_minimal_perfect_hash(testdata)
>>> for key, value in testdata.items():
... assert perfect_hash_lookup(key, *tables) == value
...
Вам нужно только реализовать функцию поиска в C:
- Операция
fnv_hash_int может взять указатель на ваше 64-разрядное целое число, затем просто привести этот указатель к массиву 8-разрядных значений и увеличить индекс 8 раз, чтобы получить доступ к каждому отдельному байту.;используйте подходящую функцию , чтобы обеспечить порядок порядка байтов (по сети) . - Вам не нужно маскировать с
0xffffffff в C, поскольку переполнение целочисленного значения C автоматически отбрасываетсяв любом случае. len(intermediate) == len(values) == len(dictionary) и может быть записан в константе. - Предполагая C99, сохраните промежуточную таблицу как массив типа структуры с
flag, являющимся bool, d как без знака short;это всего 3 байта плюс 1 дополнительный байт для выравнивания по 4-байтовой границе.Тип данных в массиве values зависит от значений в вашем входном словаре.
Если вы простите мои навыки C, вот пример реализации:
mph_table.h
#include "mph_generated_table.h"
#include <arpa/inet.h>
#include <stdint.h>
#ifndef htonll
// see https://stackoverflow.com/q/3022552
#define htonll(x) ((1==htonl(1)) ? (x) : ((uint64_t)htonl((x) & 0xFFFFFFFF) << 32) | htonl((x) >> 32))
#endif
uint64_t mph_lookup(uint64_t key);
mph_table.c
#include "mph_table.h"
#include <stdbool.h>
#include <stdint.h>
#define FNV_OFFSET 0x811c9dc5
#define FNV_PRIME 0x01000193
uint32_t fnv_hash_modulo_table(uint32_t d, uint64_t key) {
d = (d == 0) ? FNV_OFFSET : d;
uint8_t* keybytes = (uint8_t*)&key;
for (int i = 0; i < 8; ++i) {
d = (d * FNV_PRIME) ^ keybytes[i];
}
return d % TABLE_SIZE;
}
uint64_t mph_lookup(uint64_t key) {
_intermediate_entry entry =
mph_tables.intermediate[fnv_hash_modulo_table(0, htonll(key))];
return mph_tables.values[
entry.flag ?
entry.d :
fnv_hash_modulo_table((uint32_t)entry.d, htonll(key))];
}
, который будет опираться на сгенерированный файл заголовка, полученный из:
from textwrap import indent
template = """\
#include <stdbool.h>
#include <stdint.h>
#define TABLE_SIZE %(size)s
typedef struct _intermediate_entry {
bool flag;
uint16_t d;
} _intermediate_entry;
typedef struct mph_tables_t {
_intermediate_entry intermediate[TABLE_SIZE];
uint64_t values[TABLE_SIZE];
} mph_tables_t;
static const mph_tables_t mph_tables = {
{ // intermediate
%(intermediate)s
},
{ // values
%(values)s
}
};
"""
tables = gen_minimal_perfect_hash(dictionary)
size = len(dictionary)
cbool = ['false, ', 'true, ']
perline = lambda i: zip(*([i] * 10))
entries = (f'{{{cbool[e[0]]}{e[1]:#06x}}}' for e in tables[0])
intermediate = indent(',\n'.join([', '.join(group) for group in perline(entries)]), ' ' * 8)
entries = (format(v, '#018x') for v in tables[1])
values = indent(',\n'.join([', '.join(group) for group in perline(entries)]), ' ' * 8)
with open('mph_generated_table.h', 'w') as generated:
generated.write(template % locals())
, где dictionary - ваша таблица ввода.
Скомпилированный с gcc -O3 хеш-функция встроена (цикл развернут), и вся функция mph_lookup синхронизируется с 300 командами процессора.Быстрый тестовый цикл по всем 50-тысячным случайным ключам, которые я сгенерировал, показывает, что мой ноутбук Intel Core i7 с частотой 2,9 ГГц может просматривать 50 миллионов значений для этих ключей в секунду (0,02 микросекунды на ключ).