Самый быстрый поиск строкового ключа для известного набора ключей

Рассмотрим функцию поиска со следующей подписью, которая должна возвращать целое число для данного строкового ключа:

int GetValue(string key) { ... }

Кроме того, учтите, что сопоставления значений ключей с нумерацией N известны заранее, когда пишется исходный код функции, например:

// N=3
{ "foo", 1 },
{ "bar", 42 },
{ "bazz", 314159 }

Таким образом, допустимой (но не идеальной!) Реализацией функции для ввода выше будет :

int GetValue(string key)
{
    switch (key)
    {
         case "foo": return 1;
         case "bar": return 42;
         case "bazz": return 314159;
    }

    // Doesn't matter what we do here, control will never come to this point
    throw new Exception();
}

Также заранее известно, сколько раз (C> = 1) функция будет вызываться во время выполнения для каждой заданной клавиши. Например:

C["foo"] = 1;
C["bar"] = 1;
C["bazz"] = 2;

Порядок таких вызовов , однако неизвестен. Например. Вышеупомянутое может описывать следующую последовательность вызовов во время выполнения:

GetValue("foo");
GetValue("bazz");
GetValue("bar");
GetValue("bazz");

или любую другую последовательность, при условии совпадения счетчиков вызовов.

Существует также ограничение M, указанное в наиболее удобных единицах измерения, определяющее верхнюю память граница любых таблиц поиска и других вспомогательных структур, которые могут использоваться GetValue (структуры инициализируются заранее; эта инициализация не учитывается в сложности функции). Например, M = 100 символов или M = 256 sizeof (ссылка на объект).

Вопрос в том, как записать тело GetValue так, чтобы оно было как можно быстрее - другими словами , совокупное время всех вызовов GetValue (обратите внимание, что мы знаем общее количество по всем вышеперечисленным) минимально для данных N, C и M?

Алгоритм может потребовать разумное минимальное значение для M, например M> = char.MaxValue . Также может потребоваться, чтобы M было выровнено по какой-то разумной границе - например, что это может быть только степень двойки. Также может потребоваться, чтобы M была функцией N определенного вида (например, это может допускать допустимое значение M = N, или M = 2N, ...; или допустимое значение M = N, или M = N ^ 2, ...; и т.д.)

Алгоритм может быть выражен на любом подходящем языке или в другой форме. Что касается ограничений производительности во время выполнения для сгенерированного кода,Предположим, что сгенерированный код для GetValue будет на C #, VB или Java (на самом деле подойдет любой язык, если строки рассматриваются как неизменяемые массивы символов, то есть длина O (1) и O ( 1) индексация, и никакие другие данные для них не рассчитываются заранее). Кроме того, чтобы немного упростить это, ответы, которые предполагают, что C = 1 для всех ключей, считаются действительными, хотя предпочтительны те ответы, которые относятся к более общему случаю.

Некоторые размышления о возможных подходах

Очевидный первый ответ на выше используется идеальный хеш, но общие подходы к его поиску кажутся несовершенными. Например, можно легко сгенерировать таблицу для минимального идеального хэша, используя хеширование Пирсона для приведенных выше примеров данных, но тогда входной ключ должен быть хеширован для каждого вызова GetValue , а хэш Пирсона обязательно сканирует вся входная строка. Но все образцы ключей на самом деле отличаются своим третьим символом, поэтому только он может использоваться в качестве входных данных для хеша вместо всей строки. Кроме того, если требуется, чтобы M было не менее char.MaxValue , тогда третий символ сам становится идеальным хешем.

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

Также может быть, что традиционное хеширование - не такая уж хорошая идея для начала, и легче структурировать тело GetValue в виде серии условных выражений, организованных таким образом, что первый проверяет "наиболее изменчивый" символ (тот, который различается для большинства ключей), с последующими вложенными проверками по мере необходимости для определения правильного ответа. Обратите внимание, что на «дисперсию» здесь может влиять количество раз, которое будет просматриваться каждый ключ (C). Кроме того, не всегда очевидно, какой должна быть лучшая структура ветвей - например, может быть, что символ «наиболее изменчивый» позволяет различать только 10 ключей из 100, а для остальных 90 - одну дополнительную проверку. нет необходимости различать их, и в среднем (с учетом C) на каждый ключ приходится больше проверок, чем в другом решении, которое не начинается с "наиболее изменчивого" символа. Затем цель состоит в том, чтобы определить идеальную последовательность проверок.