Generating binary sequences without repetition

user_6997665 0
Viewed 363

I am trying to generate sequences containing only 0's and 1's. I have written the following code, and it works.

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

My batch variable is in the thousands. This loop above takes about 30 seconds to complete. This is a data generation part of another for loop that runs for about 500 iterations and is therefore extremely slow. Is there a faster way to generate this list of sequences without repetition? Thanks.

The desired result is a collection of batch_size number of sequences each of length dim containing only 0s and 1s such that no two sequences in the collection are the same.

python-3.x random numpy python performance
4 Answers

Generate batch number of int in range(0, 2**dim + 1) Convert these numbers to binary, then convert to sequence of 0a and 1s.

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)]

the second one is bit faster

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))

output

1.4956848690007973
1.1187048860001596
user_40466320

For the described desired result you can use binary representations of the numbers 0...batch_size-1 (multiplied by (2^dim)/batch_size) and shuffle them.
That approach is much more efficient, because there is no discarding of tentatively generated numbers and the time complexity without nested loops is much better.

For getting a random component into this (not defined for the desired result, but kind of obvious) you can add a random number to each in the range 0...( (2^dim)/batch_size -1). That will not result in identicals either, because of the spacing of the original sequence generated as described above. The randoms will never reach into the range of the next generated number.

E.g.

dim 5, batch_size 8

sequential binary random total shuffled index
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

What remains is shuffling, to break the "continuos run" of this.

user_77334180

An easy way to speed up a lot checking for long sequences is using hashing. For every sequence compute an hash code and then keep a bucket (or a linked list) for all sequences with a given hash.

When you generate a new sequence you only need to check duplicates in the hash bucket of its hash code. For example using 16 bits of hash code the duplication check will be about 65536 times faster.

user_3207260

You can get non-repeating random bit patterns as integers using the sample function from the random module. Converting these integers to bit is a job better done by numpy (as opposed to string manipulations)

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)

This is more than 500 times faster than your function (5x faster than buran's generate2() function)

user_52375600
Related