算法查找匹配布尔查询的大型int数组的子集

Question

假设我有一个大的M 32位整数数组,其中每个值设置不超过N位.现在我想返回匹配查询Target AND Value == Target的子集,即目标位出现在数组值中的值.

蛮力很容易,只需迭代数组并提取target&value == target.如果M变得非常大,这变得太慢了.任何人都知道如何将数组转换为更适合搜索的数据结构？

一种方法是为每个位存储数组或值(因此对于32位数组,您需要其中的32个),然后仅搜索与目标值中的每个位匹配的值.除非N接近32或目标接近N位设置,否则这会有所帮助.由于我所寻找的基本上是部分匹配,散列或排序似乎没有帮助.

确切的正确结果是必需的.这将无需访问并行硬件(如GPU或使用SIMD).

我将使用C++,但只是一些指向算法或想法的指针是好的.最可能的情况是M = 100000和N = 8并且经常被调用.

重申一点:我需要部分匹配(如item = 011000匹配目标= 001000)不完全匹配.尽管M项是提前知道的,但目标的可能值可以是任何值.

我终于决定坚持使用蛮力.对于80,000件物品,不值得做其他任何事情.我想如果数据集的大小更像是800,000,000,那么它可能是值得的.

Answer 1

这似乎是 SQL 数据库擅长的事情。如果您在（MSB、BitsSet、Value）上放置复合索引，您的结果应该非常快。

IntegerList:
    Value INT
    BitsSet INT
    MSB INT

INSERT INTO IntegerList(Value, BitsSet, MSB) VALUES(@Value, GetBitsSet(@Value), GetMSB(@Value)

SELECT Value FROM IntegerList WHERE MSB = GetMSB(@Target) AND BitsSet >= GetBitsSet(@Target) AND (Value & @Target) = @Target

---GetMSB
DECLARE @b BIGINT
DECLARE @c INT
SELECT @b = 0x80000000
SELECT @c = 32
WHILE (@b <> 0)
BEGIN
    IF (@b & @value) = @b
    BEGIN
        RETURN @c
    END
    SELECT @b = @b / 2
    SELECT @c = @c - 1
END

---GetBitsSet
DECLARE @b BIGINT
DECLARE @c INT
SELECT @b = 0x80000000
SELECT @c = 0
WHILE (@b <> 0)
BEGIN
    IF (@b & @value) = @b
    BEGIN
        SELECT @c = @c + 1
    END
    SELECT @b = @b / 2
END
RETURN @c

如果您必须直接使用 C++ 进行操作，我建议尝试模拟 SQL 方法。

使用 int Value、BitsSet、MSB 创建结构体或类

创建 2 个节点数组，一个按 MSB 排序，另一个按 BitsSet 排序。

对 MSB（匹配 Target 的 MSB）数组和 BitsSet（匹配所有 BitsSet >= Target）数组使用二分查找。

获取这两个结果的并集，然后执行 Target & Value == Target 检查。