根据列表B过滤列表A中的元素，使得A中的a在B中至少存在一个元素b，其中a = (a&b)

Question

我有 2 个整数列表：A 和 B。如何有效地确保 A 中的每个元素在 B 中至少存在一个元素，这样当它们按位与运算时，答案就是 A 中的该元素。

例如。 B = [14, 13 ]

因此对于 A 中的元素： a1 = 12 有效，因为 12&14 = 12 a2 = 3 无效，因为 3&14 = 2 且 3&13 = 1

A 和 B 可以有 10^10 个条目。

我正在从 csv 中将 B 作为一列读取，并动态生成 A。并使用

检查上述条件

df.applymap(lambda x: (x&a) == a ).any().any()

但是随着 B 大小的增加，这个检查是我的瓶颈。

Answer 1

如果速度是一场音乐会，你可以尝试使用numba：

from numba import njit


@njit
def check(a, b):
    for val_a in a:
        for val_b in b:
            if (val_b & val_a) == val_a:
                return True
    return False


a = np.array([12, 3], dtype=np.uint8)
b = np.array([14, 13], dtype=np.uint8)

print(check(a, b))

打印：

True

---

基准：

from statistics import median
from timeit import repeat

np.random.seed(42)


def setup():
    a = np.random.randint(0, 255, size=10_000_000, dtype=np.uint8)
    b = np.random.randint(0, 255, size=10_000_000, dtype=np.uint8)
    return a, b


t = repeat(
    "check(a, b)", setup="a, b = setup()", repeat=1000, number=1, globals=globals()
)

print(f"t={median(t):.8f}")

在我的计算机（AMD 5700x）上打印：

t=0.00000496