两个整数的二进制表示的均匀重组

Question

我需要快速实现以下问题，最好是作为 numba 函数。我从名为 integerlist 的列表中取出两个随机整数 a&b 并考虑它们长度的二进制表示 l，例如 a=10->1010、b=6->0110。之后，我在两个二进制表示之间执行统一交叉，并将生成的二进制数的整数值保存在 integerlist 中的随机位置。均匀重组意味着整数 c 的二进制表示的每个条目都以相等的概率取自 a 或 b 的二进制表示条目，例如

a=10->1010
b=6 ->0110
      1110 ->c=14

为此，我想出了以下代码，但速度不是很快。目前我正在尝试获取此功能的 numba 版本，但到目前为止还没有成功。你能帮忙吗？

def recombination(integerlist, l):
    N = len(integerlist)
    for x1 in range(N):
        a = integerlist[random.randint(0, N-1)]
        b = integerlist[random.randint(0, N-1)]
        binary_a = list(map(int, numpy.binary_repr(a, width=l)))
        binary_b = list(map(int, numpy.binary_repr(b, width=l)))
        binary_c = [0]*l
        for x2 in range(l):
            if random.random() <= 0.5:
                binary_c[x2] = binary_a[x2]
            else:
                binary_c[x2] = binary_b[x2]
        c = 0
        for bit in binary_c:
            c = (c << 1) | bit
        integerlist[random.randint(0, N-1)] = c

编辑： 如果我用以下函数替换 list(map(int, numpy.binary_repr(a, width=l)))

@nb.njit
def dec_to_binary_fct(a, l):
    bin_temp = []
    for i in range(l):
        i = l-i-1
        k = a >> i
        if (k & 1):
            bin_temp.append(1)
        else:
            bin_temp.append(0)
    return bin_temp

我可以把 @nb.njit 放在 def recombination(integerlist, l): 前面，这已经大大提高了性能。我还是很好奇能不能提高性能。

Answer 1

这是一种计算交叉的方法，我敢肯定它更快：

def xover(a, b):
    l = max(a.bit_length(), b.bit_length())
    return a^((a^b)&random.randint(0, (1<<l)-1))

说明：

我们首先使用按位互斥或找出不同的位（对于其他位我们从哪里取并不重要，所以我们不妨从a中取所有）
然后我们使用按位和随机掩码平均删除一半
最后再次使用按位异或来翻转a中剩余的位（我们知道在这些位置a翻转的是b）

两个整数的二进制表示的均匀重组

Uniform recombination of binary representation of two integers

python

performance

numpy

numba