Поиск с маской

Question

Существует большой массив записей следующего типа:

typedef struct {
    int value;
    int mask;
    int otherData;
} Entry;

Я бы хотел найти запись в этом массиве в соответствии с предоставленным int key; как можно быстрее. Запись необходима для того, чтобы (key & mask) == value.

Каков наилучший способ для организации такого массива и каков соответствующий алгоритм его обработки?

Редактировать: нет ограничений на организацию массива; это статично и может быть подготовлено перед поиском. value и mask могут иметь произвольные значения.

Edit2: value и mask могут иметь произвольные значения, но количество записей в массиве составляет около 10000. Таким образом, некоторые «патерны» могут быть вычислены заранее.

Количество поисков велико.

Answer 1

Каждый бит является независимым, поэтому на этапе предварительной обработки [*] вы могли бы классифицировать каждую запись 32 (или сколько бы вы ни были int) раз.Каждая классификация хранит 2 набора: те, которые соответствуют этому биту, когда key равен 0, и те, которые соответствуют, когда key равен 1.

То есть, если значение == 1 и маска == 0 при этомбит, то эта классификация вообще не хранит эту запись, поскольку она не соответствует ни одному значению key (фактически, независимо от используемой схемы, такие записи должны быть удалены на любом этапе предварительной обработки, поэтому нет классификация должна хранить запись, если хотя бы один бит такой).Если оба 0, хранить в обоих наборах.В противном случае сохраните в один из двух наборов.

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

В зависимости от размера исходного массива, это может бытьчто лучший способ сохранить каждый набор - это гигантский битовый массив, указывающий, находится ли каждая запись в массиве в наборе или нет.Затем найти пересечение можно одним словом за один раз - & вместе 32 словами, по одному в каждом битовом массиве.Если результат 0, продолжайте.Если результат не равен 0, у вас есть совпадение, и бит, установленный в результате, сообщает вам, какая запись соответствует.Конечно, размер массива по-прежнему линейный, и на самом деле вы выполняете 31 & операций, чтобы проверить совпадение 32 записей, что примерно равно простому линейному поиску в исходном массиве.Но сравнений и разветвлений меньше, и данные, которые вы просматриваете, более сжаты, так что вы можете получить более высокую производительность.

Или может быть лучший способ сделать пересечение.

Если ключи, как правило, используются повторно, вам следует кэшировать результаты поиска на карте от ключей до записей.Если число возможных ключей достаточно мало (т. Е. Если возможно менее 2 ^ 32 ключей являются возможными входами и / или у вас много свободной памяти), то фаза предварительной обработки может быть просто:

1. принимать каждую запись по очереди
2. определить, какие возможные ключи ей соответствуют
3. добавить ее на карту для этих ключей

[*] Без каких-либопредобработка, очевидно, все, что вы можете сделать, это проверить каждый член массива, пока вы не найдете совпадение или не проверили все.

Answer 2

Поскольку у вас нет дополнительной информации (например, что массив отсортирован), вам необходим линейный поиск - переберите массив и проверьте условие - псевдокод:

for( size_t index = 0; index < arraySize; index++ ) {
   if( ( array[index].mask & key ) == array[index].value ) ) {
      return index;
   }
}
return -1;

Answer 3

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

• Если бы ваш массив был отсортирован по ключу,тогда вы могли бы выполнить лексикографический бинарный поиск с небольшим усилием. [на самом деле, может быть, нет!]

• На самом деле, вы просто собираетесь обходить массив, пока не найдете то, что ищете .То есть, переходя от начала к концу и останавливаясь, когда вы его найдете.

_{Кроме того, это отличный пример того, как выбор структуры данных влияет на доступностьалгоритмы вниз по линии.Вы не можете просто бросить алгоритмы на проблему, если вы сначала выбрали неправильные структуры данных!}

Answer 4

Если количество нулевых битов в вашей маске мало, вы можете продублировать запись для каждого "небезразличного" бита в маске. Например, если value=0 и mask=0xfffe, вы бы поместили в таблицу запись для key=0 и key=1. Для value=0 и mask=0xfeef поместите в таблицу 4 записи: key=0x0000, key=0x0010, key=0x0100 и key=0x0110. Теперь вы можете сортировать записи и использовать двоичный поиск или использовать структуру двоичного поиска, такую ​​как std::map.

Answer 5

Если mask изменяется произвольно для каждой записи, я не вижу большой альтернативы линейному поиску.Если существуют существенные ограничения на mask, такие, что возможны только несколько значений, может быть лучше использовать какой-то map для каждого значения mask, выполняя линейный поиск, чтобы найти первое mapкоторый содержал значение, которое вы ищете.В качестве альтернативы, если mask s относится только к нескольким битам, возможно, стоит использовать multimap, упорядоченный по value, замаскированный с помощью and из всех mask с и проиндексированный с помощью keyобрабатывается то же самое, затем выполняется линейный поиск с использованием полного key, чтобы найти точное совпадение.

Answer 6

Конечно, будет работать линейный поиск, но если вам нужно много поисков с одним и тем же ключом, вы можете сначала попытаться отсортировать диапазон в соответствии с (key & mask).Если у вас есть только несколько фиксированных ключей, вы можете попробовать использовать boost.multi_index с одним индексом для каждого значения ключа.