Is there faster way to randomly swap one "0" to one "1" in a one dimensional array?

user_5855131 0
Viewed 112

I would like to randomly swap one 0 and one 1 in a one dimensional array which contain only 0 and 1 many many times say up to N = 10^6. Here is my code for doing the swap one time.

import numpy as np

# a contains only 0 and 1
a = np.array([0,1,1,0,1,1,0,0,0,1])
# j1 random position of 0, j2 random position of 1
j1 = np.random.choice(np.where(a==0)[0])
j2 = np.random.choice(np.where(a==1)[0])
# swap
a[j1], a[j2] = a[j2], a[j1]

Since I would like to do this process many many time, at every iteration, I need to use np.where() to locate posistions of 0 and 1, which I think is not that efficient.

Is there any other approach which can be more effecient ?

scipy numpy arrays algorithm python
2 Answers

You could maintain the result of the where expressions yourself, as swaps are executed, so that you don't need to re-execute that where call. You'd only do it once, at the start of the procedure, but then in the loop, you'd incrementally adjust.

Also, the swap can be replaced by two assignments, since you know that the 0 will become 1 and vice versa.

a = np.array([0,1,1,0,1,1,0,0,0,1])

# One-time preprocessing

zeroes = np.where(a==0)[0]
ones = np.where(a==1)[0]
num_zeroes = len(zeroes)
num_ones = len(ones)

# In a loop:

for _ in range(100):
    # Choose random indices in zeroes/ones
    j0 = np.random.randint(num_zeroes)
    j1 = np.random.randint(num_ones)
    # Get the chosen indices for use in `a`:
    i0 = zeroes[j0]
    i1 = ones[j1]
    # Keep the two collections in sync with the swap that now happens
    zeroes[j0] = i1
    ones[j1] = i0
    # The swap itself
    a[i0] = 1
    a[i1] = 0

    # ...

Note that the length of zeroes and ones doesn't change: we can just reuse the two slots that were selected at every swap.

user_54598390

I want to drop what i described in my comment here as an answer based on the assumption that the array is somewhat close to a 50:50 distribution of 0s and 1s.

The beauty of this approach, while not on a fixed execution time the time complexity in regards to the array size is O(1) so for larger arrays it can handily beat trincots approach.

length = 1e8
a = (np.random.randint(0,2,int(length))).astype(np.uint8)

t = time.time_ns()
rng = np.random.default_rng()
for i in range(10000):
    b = rng.integers(0, length)
    while(True):
        c = rng.integers(0, length)
        if c == b:
            continue
        if a[c] != a[b]:
            a[c] ^= 1
            break
a[b] ^= 1
print((time.time_ns()-t)/1e9)

# Trincot

t = time.time_ns()
zeroes = np.where(a==0)[0]
ones = np.where(a==1)[0]
num_zeroes = len(zeroes)
num_ones = len(ones)

for _ in range(10000):
    # Choose random indices in zeroes/ones
    j0 = np.random.randint(num_zeroes)
    j1 = np.random.randint(num_ones)
    # Get the chosen indices:
    i0 = zeroes[j0]
    i1 = ones[j1]
    # Keep the two collections in sync with the swap that now happens
    zeroes[j0] = i1
    ones[j1] = i0
    # The swap itself
    a[i0] = 1
    a[i1] = 0
print((time.time_ns()-t)/1e9)

result:

0.1360712
1.3667251
user_55246370
Related