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

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, и хэш Пирсона обязательно сканирует всю входную строку. Но все примеры ключей на самом деле различаются по своему третьему символу, так что только они могут использоваться в качестве ввода для хеша вместо всей строки. Кроме того, если М требуется по крайней мереchar.MaxValueтогда третий персонаж сам становится идеальным хешем.

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

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