Точки запроса на вершинах куба Хэмминга
У меня есть N точек, которые лежат только на вершинах куба, размерности D, где D — что-то вроде 3.
Вершина не может содержать какую-либо точку. Таким образом, каждая точка имеет координаты в {0, 1}D. Меня интересует только время запроса, до тех пор, пока стоимость памяти разумна (не экспоненциально в N, например :)).
Учитывая запрос, который лежит на одной из вершин куба и входного параметра rнайти все вершины (то есть точки), которые имеют расстояние Хемминга <знак равно r с запросом.
Какой способ пойти в C ++ среда?
Я думаю о kd-дереве, но я не уверен и хочу помочь, любой вход, даже приблизительный, был бы оценен! поскольку расстояние Хемминга вступает в игру, битовые манипуляции должны помочь (например, XOR).
Решение
Есть хороший битхак из одной битовой маски с k биты установлены в лексикографически следующая перестановка, а это значит, что довольно просто пройти через все маски с k биты установлены. КСОРКА этих масок с начальным значением дает все значения на расстоянии Хэмминга точно k подальше от этого.
Таким образом, для D размеры, где D меньше 32 (в противном случае меняйте типы),
uint32_t limit = (1u << D) - 1;
for (int k = 1; k <= r; k++) {
uint32_t diff = (1u << k) - 1;
while (diff <= limit) {
// v is the input vertex
uint32_t vertex = v ^ diff;
// use it
diff = nextBitPermutation(diff);
}
}
куда nextBitPermutation может быть реализовано в C ++ как-то так (если у вас есть __builtin_ctz)
uint32_t nextBitPermutation(uint32_t v) {
// see https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
uint32_t t = v | (v - 1);
return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}
Или для MSVC (не проверено)
uint32_t nextBitPermutation(uint32_t v) {
// see https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
uint32_t t = v | (v - 1);
unsigned long tzc;
_BitScanForward(&tzc, v); // v != 0 so the return value doesn't matter
return (t + 1) | (((~t & -~t) - 1) >> (tzc + 1));
}
Если D действительно низкий, 4 или ниже, старый popcnt-с-pshufb работает очень хорошо, и в целом все хорошо выстраивается, вот так:
uint16_t query(int vertex, int r, int8_t* validmask)
{
// validmask should be array of 16 int8_t's,
// 0 for a vertex that doesn't exist, -1 if it does
__m128i valid = _mm_loadu_si128((__m128i*)validmask);
__m128i t0 = _mm_set1_epi8(vertex);
__m128i r0 = _mm_set1_epi8(r + 1);
__m128i all = _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
__m128i popcnt_lut = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
__m128i dist = _mm_shuffle_epi8(popcnt_lut, _mm_xor_si128(t0, all));
__m128i close_enough = _mm_cmpgt_epi8(r0, dist);
__m128i result = _mm_and_si128(close_enough, valid);
return _mm_movemask_epi8(result);
}
Это должно быть довольно быстро; быстрый по сравнению с битхаком выше (nextBitPermutation, который является довольно тяжелым, часто используется там), а также по сравнению с циклическим перебором по всем вершинам и проверкой, находятся ли они в диапазоне (даже с помощью встроенного popcnt, это автоматически занимает не менее 16 циклов, а вышеперечисленное не должно, при условии, что все кэшировано или даже постоянно в регистре). Недостатком является то, что работать с результатом раздражает, поскольку это маска, из которой вершины существуют и находятся в пределах диапазона запрашиваемой точки, а не их список. Хотя это хорошо сочетается с некоторой обработкой данных, связанных с точками.
Это также уменьшает до D = 3, конечно, просто не используйте ни одну из точек> = 8. D> 4 можно сделать аналогичным образом, но тогда потребуется больше кода, и, поскольку это действительно грубое решение, которое является быстрым только благодаря параллелизму, оно существенно замедляется экспоненциально в D.
Другие решения
Других решений пока нет …