Мы ищем самую простую вычислительную функцию, которая позволит индексировать поиск функции, определяемой высокочастотным входным потоком широко распределенных целых чисел и диапазоны целых чисел.Эффективная функция для преобразования целых чисел и целых чисел в индексы
Это нормально, если сам выбор функции хеша/карты зависит от конкретных требований к целому и диапазону, а производительность, связанная с частью кода, который выбирает этот алгоритм, не является критическим. Число целых чисел/диапазонов, представляющих интерес в большинстве случаев, будет небольшим (от нуля до нескольких тысяч). Критическая часть производительности - это обработка входящего потока и выбор соответствующей функции.
В качестве простого примера, пожалуйста, рассмотрите следующий псевдокод:
switch (highFrequencyIntegerStream)
case(2) : func1();
case(3) : func2();
case(8) : func3();
case(33-122) : func4();
...
case(10,000) : func40();
В типичном примере, было бы лишь несколько тысяч из «случаев», показанных выше, которые могут включать в себя полный спектр 32-битных целых значений и диапазонов. (В псевдокоде выше 33-122 представлены все целые числа от 33 до 122.) Будет большое количество объектов, содержащих эти «операторы switch».
(Обратите внимание, что фактическая реализация не будет включать в себя операторы switch. Вместо этого это будет таблица перехода (которая представляет собой массив указателей функций) или, может быть, комбинацию шаблонов Command и Observer и т. Д. Детали реализации являются тангенциальными на запрос, но предоставленный для оказания помощи при визуализации.)
Многие из объектов будут содержать «операторы switch» всего несколькими записями. Значения, представляющие интерес, подлежат изменению в реальном времени, но производительность, связанная с управлением этими изменениями, не является критичной. Алгоритмы Hash/map могут быть сгенерированы медленно с каждым обновлением на основе конкретных целых чисел и диапазонов, представляющих интерес (для данного объекта в данный момент времени).
Мы искали в Интернете, глядя на фильтры Блума, различные функции хеширования, перечисленные на странице «хэш-функции» Википедии, и в другом месте, довольно много вопросов о переполнении стека, абстрактная алгебра (в основном теория Галуа, которая привлекательна для ее вычислительно простых операнды), различные шифры и т. д., но не нашли решения, которые, как представляется, нацелены на эту проблему. (Мы даже не смогли найти функцию хеша или карты, которая рассматривала бы эти типы диапазонов как входы, а тем более высокоэффективные. Возможно, мы не ищем правильные места или используем правильный народный язык.)
Текущий план заключается в создании пользовательского алгоритма, который препроцессирует список интересных целых чисел и диапазонов (для данного объекта в данный момент времени), который ищет сдвиги и маски, которые могут быть применены к входному потоку, чтобы помочь определить диапазоны. Обратите внимание, что большинство входящих целых чисел будут неинтересными, и крайне важно принять очень быстрое решение для как можно большего процента этой части потока (поэтому фильтры Bloom выглядели интересными сначала (прежде чем мы начнем что их реализация требует большей вычислительной сложности, чем другие решения)).
Поскольку первое решение так важно, мы также рассматриваем возможность иметь несколько таблиц, первая из которых будет обратными масками (маски для выбора неинтересных чисел) для простого поиска больших диапазонов данных, не включенных в данный " switch statement ", за которым последуют последующие таблицы, которые будут расширять меньшие диапазоны. Мы думаем, что для большинства случаев входных потоков это приведет к чему-то значительно быстрее, чем к бинарному поиску на границах диапазонов.
Обратите внимание, что входной поток можно считать случайным образом распределенным.
Обмануть gperf в мышление, что наши данные являются строкой, представляет интересную идею. Мы также рассматриваем CMPH, как вы предложили. Мы искали IEEE и ACM, но не нашли ничего, что касалось диапазонов. Беглый взгляд на gperf и CMPH также, по-видимому, указывает на то, что они не обрабатывают диапазоны. Например, если бы кто-то использовал границы диапазона в строке gperf, хеш-функция не знала бы, чтобы выбрать что-то внутри этого диапазона и сопоставить его с правильным индексом. Например, в нашем псевдокоде, как, например, знал бы gperf, чтобы сопоставить ввод 100 с индексом, связанным с func4? – Mark
Извините, я неправильно понял. Из потока байтов извлекались диапазоны мыслей. Теперь я понимаю, что вы имеете в виду. Дай мне подумать об этом. – Gene
Мы провели некоторое время вчера вечером, работая с gperf, как и предполагалось. Обратите внимание, что если бы мы использовали его для второй таблицы в нашем предложенном выше решении (после того, как большие диапазоны (и обратные диапазоны) были замаскированы, а малые диапазоны были расширены), мы должны были бы включить gperf и и компилятор как часть наш выпуск. По этой причине CMPH может быть лучшим выбором. Тем не менее, мы все еще надеемся на хороший способ включения диапазонов в качестве неотъемлемой части алгоритма. – Mark