scipy 在一维数组中,有没有更快的方法将一个“0”随机交换为一个“1”?

wyyhbhjk  于 2022-11-10  发布在  其他
关注(0)|答案(2)|浏览(171)

我想在一个一维数组中随机交换一个0和一个1,这个数组只包含0和1,交换的次数很多,比如说最多可以达到N = 10^6

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]

因为我想做很多次这个过程,在每次迭代中,我需要使用np.where()来定位0和1的位置,我认为这不是很有效。

是否有其他更有效的方法?

yqlxgs2m

yqlxgs2m1#

你可以在执行交换时自己维护where表达式的结果,这样你就不需要重新执行where调用了。你只需要在过程开始时做一次,然后在循环中,你需要逐渐调整。
同样,交换可以被两个赋值替换,因为你知道0会变成1,反之亦然。

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

    # ...

请注意,zeroesones的长度不会改变:我们可以重用在每次交换时选择的两个插槽。

zyfwsgd6

zyfwsgd62#

我想放弃我在这里的评论中所描述的,作为一个基于假设的答案,即数组在某种程度上接近于0和1的50:50分布。
这个方法的优点是,虽然不是在固定的执行时间上,但与数组大小有关的时间复杂度是O(1),因此对于较大的数组,它可以轻松地击败trincots方法。

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)

实验结果:

0.1360712
1.3667251

相关问题