Как сопоставить 13-битное значение с 4-битным кодом?

Question

У меня есть std :: map для некоторой программы обработки пакетов.

Я не заметил до профилирования, но, к сожалению, только этот поиск карты потребляет около 10% процессорного времени (которое вызывается слишком много времени).

Обычно во входных данных существует не более 10 клавиш.Поэтому я пытаюсь реализовать вид кэша ключей перед картой.

Значение ключа - 13-битное целое число.Я знаю, что есть только 8192 возможных ключа, и массив из 8192 элементов может обеспечить постоянный поиск по времени, но мне уже стыдно, и я не хочу использовать такой наивный подход: (

Теперь, я просто угадываю какой-то методхэширования, которые дают 4-битное кодовое значение для 13-битного целого числа очень быстро.

Любая крутая идея?

Заранее спасибо.

ОБНОВЛЕНИЕ

Помимо позора, я не имею полного контроля над исходным кодом, и почти запрещено создавать новый массив для этой цели.

Менеджер проекта сказал (кто запускал профилировщик), связанный список показывает небольшую производительностьполучить и рекомендовать использовать std :: list вместо std :: map.

UPDATE

Значения ключей являются случайными (без отношения) и не имеют хорошего распределения.

Образец:
1) 0x100, 0x101, 0x10, 0x0, 0xffe
2) 0x400, 0x401, 0x402, 0x403, 0x404, 0x405, 0xff

Answer 1

Предполагается, что ваша хеш-таблица содержит какой-то базовый тип - почти нет памяти.Даже на 64-битных системах это только 64 КБ памяти.Нет ничего постыдного в использовании подобной таблицы поиска, она обладает лучшими характеристиками, которые вы можете получить.

Answer 2

Возможно, вы захотите использовать среднее решение и метод открытой адресации : один массив размером 256. Индекс для массива - это простая хеш-функция, такая как XOR из двух байтов. Элементом массива является структура {ключ, значение}. Столкновения обрабатываются путем сохранения столкнувшегося элемента в следующем доступном индексе. Если вам нужно удалить элемент из массива, и если удаление происходит редко, просто создайте заново массив (создайте временный список из оставшихся элементов, а затем создайте массив из этого списка).

Если вы правильно выберете свою хэш-функцию, столкновений почти не будет. Например, из ваших двух примеров одним таким хэшем будет XOR младший полубайт старшего байта с старшим полубайтом младшего байта (и делайте что хотите с оставшимся 13-м битом).

Answer 3

Если в вашей таблице действительно будет что-то вроде 10 активных записей, вы можете серьезно подумать об использовании несортированного вектора для хранения этого отображения.Примерно так:

typedef int key_type;
typedef int value_type;
std::vector<std::pair<key_type, value_type> > mapping;

inline void put(key_type key, value_type value) {
    for (size_t i=0; i<mapping.size(); ++i) {
        if (mapping[i].first==key) {
            mapping[i].second=value;
            return;
        }
    }
    mapping.push_back(std::make_pair(key, value));
}    

inline value_type get(key_type key) {
    for (size_t i=0; i<mapping.size(); ++i) {
        if (mapping[i].first==key) {
            return mapping[i].second;
        }
    }
    // do something reasonable if not found?
    return value_type();
}

Теперь асимптотическая скорость этих алгоритмов (каждый O(n)) намного хуже, чем у вас с красно-черным деревом (например, std::map при * 1006).*) или хеш-таблица (O(1)).Но вы не говорите о работе с большим количеством объектов, так что асимптотические оценки на самом деле не приносят вам большой пользы.

Кроме того, std::vector дает вам как низкие накладные расходы, так и локальность ссылок, которые ни1011 * ни std::list не можем предложить.Таким образом, более вероятно, что небольшой std::vector останется полностью в кеше L1.Поскольку почти наверняка узкое место в памяти вызывает проблемы с производительностью, использование std::vector даже с моим неудачным выбором алгоритма, скорее всего, будет быстрее, чем в виде дерева или связанного списка.Конечно, только несколько сплошных профилей скажут вам наверняка.

Конечно, есть алгоритмы, которые могут быть лучшим выбором: отсортированный вектор потенциально может дать еще лучшую производительность;хорошо настроенная небольшая хеш-таблица может также подойти.Я подозреваю, что вы довольно быстро столкнетесь с законом Амдаля, пытаясь улучшить простой несортированный вектор.Довольно скоро вы, возможно, столкнетесь с накладными расходами на вызовы функций или с какими-то другими подобными проблемами в качестве крупного участника вашего профиля.

Answer 4

Если вы не пишете для какой-то встроенной системы, где 8K действительно важны, просто используйте массив и продолжайте.Если вы действительно настаиваете на том, чтобы заняться чем-то другим, вы можете рассмотреть идеальный генератор хешей (например, gperf ).

Answer 5

Когда у вас всегда есть только около десяти ключей, используйте список (или массив). Проведите сравнительный анализ, чтобы выяснить, улучшит ли использование отсортированный список (или массив) и двоичный поиск.

Answer 6

Я согласен с GWW, вы не используете столько памяти в конце ... Но если хотите, вы можете использовать массив из 11 или 13 связанных списков и хешировать ключи с помощью функции%. Если номер ключа меньше, чем размер массива, сложности по-прежнему должны быть O (1).

Answer 7

Я бы использовал таблицу поиска.Он крошечный, если вы не используете микроконтроллер или что-то в этом роде.

В противном случае я бы сделал это -

Создайте таблицу из 30 элементов.Для каждого поиска вычислите значение хеша (ключ% 30) и сравните его с сохраненным ключом в этом месте таблицы.Если ключ есть, то вы нашли свою ценность.если слот пуст, добавьте его.Если ключ неправильный, перейдите к следующей свободной ячейке и повторите.

С 30 ячейками и 10 клавишами столкновения должны быть редкими, но если вы получили одну, то быстро перейти к следующей ячейке, и обычный поиск простомодуль и операция сравнения очень быстро

Answer 8

Сначала вы можете посмотреть, есть ли какие-либо ненужные вызовы для поиска ключа. В идеале вы хотите делать это только один раз для каждого пакета - каждый раз, когда вы вызываете функцию, возникают некоторые издержки, поэтому избавление от лишних вызовов - это хорошо.

Карта, как правило, довольно быстрая, но если в способе сопоставления клавиш с элементами есть какой-либо пригодный для использования шаблон, вы могли бы использовать его и потенциально добиться большего успеха. Не могли бы вы предоставить немного больше информации о ключах и связанных с ними 4-битных значениях? Например. они последовательные, есть какой-то шаблон?

Наконец, как уже упоминали другие, таблица поиска очень быстрая, 8192 значения * 4 бита - это всего лишь 4 Кбайт, действительно небольшой объем памяти.