汉明立方体顶点上的查询点
Query points on the vertices of a Hamming cube
我有 N 个点仅位于 D 维立方体的顶点上,其中 D 大约为 3。
顶点不能包含任何点。所以每个点的坐标都在{0, 1}D。我只对 查询时间 感兴趣,只要内存成本合理(例如 N 不是指数级的 :))。
给定位于立方体的一个顶点和输入参数 r
上的查询,找到具有 汉明距离 <= 的所有顶点(即点) r
与查询。
在 c++ 环境中的方法是什么?
我正在考虑 kd 树,但我不确定并希望得到帮助,任何输入,即使是近似值,都将不胜感激!由于 汉明距离 开始发挥作用,按位操作应该有所帮助(例如 XOR)。
从一个设置了 k
位的位掩码到 lexicographically next permutation 有一个很好的 bithack,这意味着循环遍历设置了 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
-with-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);
}
这应该相当快;与上面的 bithack 相比速度更快(nextBitPermutation
,它相当重,在那里使用了很多)并且还与遍历所有顶点并测试它们是否在范围内相比(即使使用内置 popcnt
,即自动至少需要 16 个周期,而以上不应该,假设所有内容都被缓存甚至永久保存在寄存器中)。缺点是结果很烦人,因为它是一个掩码,表示哪些顶点既存在又在查询点的范围内,而不是它们的列表。不过,它可以很好地结合对与点相关的数据进行一些处理。
当然这也缩小到D=3,只要让none的点>=8有效即可。 D>4 可以类似地完成,但它需要更多的代码,并且由于这实际上是一个蛮力解决方案,它只是由于并行性而很快,它从根本上说在 D 中呈指数级变慢。
我有 N 个点仅位于 D 维立方体的顶点上,其中 D 大约为 3。
顶点不能包含任何点。所以每个点的坐标都在{0, 1}D。我只对 查询时间 感兴趣,只要内存成本合理(例如 N 不是指数级的 :))。
给定位于立方体的一个顶点和输入参数 r
上的查询,找到具有 汉明距离 <= 的所有顶点(即点) r
与查询。
在 c++ 环境中的方法是什么?
我正在考虑 kd 树,但我不确定并希望得到帮助,任何输入,即使是近似值,都将不胜感激!由于 汉明距离 开始发挥作用,按位操作应该有所帮助(例如 XOR)。
从一个设置了 k
位的位掩码到 lexicographically next permutation 有一个很好的 bithack,这意味着循环遍历设置了 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
-with-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);
}
这应该相当快;与上面的 bithack 相比速度更快(nextBitPermutation
,它相当重,在那里使用了很多)并且还与遍历所有顶点并测试它们是否在范围内相比(即使使用内置 popcnt
,即自动至少需要 16 个周期,而以上不应该,假设所有内容都被缓存甚至永久保存在寄存器中)。缺点是结果很烦人,因为它是一个掩码,表示哪些顶点既存在又在查询点的范围内,而不是它们的列表。不过,它可以很好地结合对与点相关的数据进行一些处理。
当然这也缩小到D=3,只要让none的点>=8有效即可。 D>4 可以类似地完成,但它需要更多的代码,并且由于这实际上是一个蛮力解决方案,它只是由于并行性而很快,它从根本上说在 D 中呈指数级变慢。