生成不重复二进制序列

Question

生成不重复二进制序列

6

我想生成仅包含 0 和 1 的序列。我编写了以下代码，它可以正常运行。

import numpy as np

batch = 1000
dim = 32

while 1:
    is_same = False
    seq = np.random.randint(0, 2, [batch, dim])
    for i in range(batch):
        for j in range(i + 1, batch):
            if np.array_equal(seq[i], seq[j]):
                is_same = True
    if is_same:
        continue
    else:
        break

我的batch变量有成千上万个。上面的循环需要大约30秒才能完成。这是另一个for循环的数据生成部分，该循环运行约500次，因此非常慢。是否有更快的方法生成此列表，使其不重复？谢谢。

期望的结果是一组序列，每个序列的长度为dim，包含仅由0和1组成的batch_size数量，以便集合中的任何两个序列都不相同。

- learner

这可能更适合于代码审查。 - buran

请讨论期望和不期望的结果。也许有一种根本不同的解决方案。 - Yunnosch

@Yunnosch 我已经添加了所需的结果。我希望通过我所做的编辑，您能清楚地了解不需要的结果。如果还不清楚，我会再次添加。谢谢。 - learner

你可能需要更详细地描述可接受和不可接受的结果。因为根据你描述的解决方案，可以创建一个由连续的递增二进制数字列表组成并对其进行随机排序。这只能得到与“较低”批处理大小相等的数字。但是也许您想填充以使最后一个数字尽可能接近“batch_size-1”。如果您没有异议，我将把它作为答案。 - Yunnosch

@buran 谢谢。需要一些调整来进行随机化和序列打破。我在我的答案中尝试了一下。 - Yunnosch

显示剩余2条评论

4个回答

1

使用random模块中的sample函数可以获得不重复的随机比特模式作为整数。将这些整数转换为比特最好由numpy完成（而不是字符串操作）。

def sequenceBatch(batch,dim):
    bits  = np.array(random.sample(range(2**dim),batch),dtype=np.int)
    masks = 2**np.arange(dim)
    return (np.bitwise_and(bits[:,None],masks)>0).astype(np.int)

这比你的函数快500多倍（比buran的generate2()函数快5倍）。

- Alain T.

1

为了实现所描述的期望结果，您可以使用数字0...batch_size-1（乘以(2^dim)/batch_size）的二进制表示并对它们进行混洗。
该方法更加高效，因为没有丢弃试生成的数字，并且没有嵌套循环的时间复杂度更好。

要将随机组件引入其中（未定义所需的结果，但显而易见），您可以在范围0...( (2^dim)/batch_size -1)内为每个数字添加一个随机数。这也不会导致相同的结果，因为原始序列的间距是如上所述生成的。随机数永远不会达到下一个生成数字的范围。

例如：

维度为5，批量大小为8

顺序	二进制	随机数	总和	洗牌索引
0	00000	10	00010	5
4	00100	00	00100	2
8	01000	11	01011	6
12	01100	11	01111	0
16	10000	01	10001	3
20	10100	00	10100	7
24	11000	10	11010	1
28	11100	00	11100	4

剩下的是洗牌，以打破这种“连续运行”的状态。

- Yunnosch

谢谢，但是你的序列总是会有一个连续的运行。假设我从 x 开始，那么至少会一直运行到 x+32。很抱歉我没有达到期望的结果，但这是我想要实现的一些随机性。 - learner

在我的回答中，我忘记了我在评论中提到的洗牌。很好地发现了。 - Yunnosch

1

使用哈希算法可以轻松加速长序列的大量检查。为每个序列计算一个哈希码，然后为具有给定哈希码的所有序列保留一个桶（或链接列表）。

当您生成新序列时，您只需要在其哈希码的哈希桶中检查重复项。例如，使用16位哈希码，重复检查将快约65536倍。

- 6502

你能分享一段代码示例或者一个链接来展示如何实现吗？ - learner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- buran · Accepted Answer

生成batch个介于0到2 ** dim + 1之间的int数。将这些数字转换为二进制，然后转换为一串由0和1组成的序列。

from random import sample

def generate(batch, dim):
    my_sample = [f'{n:0>32b}' for n in sample(range(2**dim+1), batch)]
    return [[int(n) for n in item] for item in my_sample]

def generate2(batch, dim):
    return [list(map(int, f'{n:0>32b}')) for n in sample(range(2**dim+1), batch)]

第二个稍微快一点

from timeit import timeit
print(timeit("generate(1000, 32)", setup="from __main__ import generate", number=100))
print(timeit("generate2(1000, 32)", setup="from __main__ import generate2", number=100))

输出

1.4956848690007973
1.1187048860001596