高效地生成数字随机选择没有替代者

Question

我是Python新手。在阅读时，请提及关于改进Python代码的其他建议。在

问题：如何在Python中生成包含随机数的8xN维数组？约束条件是，此数组的每列必须包含8个从整数集[1,8]中提取的数据，而不替换整数集[1,8]。更具体地说，当N=10时，我想要这样的东西。在

[[ 6.  2.  3.  4.  7.  5.  5.  7.  8.  4.]
 [ 1.  4.  5.  5.  4.  4.  8.  5.  7.  5.]
 [ 7.  3.  8.  8.  3.  8.  7.  3.  6.  7.]
 [ 3.  6.  7.  1.  5.  6.  2.  1.  5.  1.]
 [ 8.  1.  4.  3.  8.  2.  3.  4.  3.  3.]
 [ 5.  8.  1.  7.  1.  3.  6.  8.  1.  6.]
 [ 4.  5.  2.  6.  2.  1.  1.  6.  4.  2.]
 [ 2.  7.  6.  2.  6.  7.  4.  2.  2.  8.]]

为此，我使用以下方法：

^{pr2}$

在实践中，N为~1e7。上面的算法在时间上是O（n），当n=1e3时大约需要0.38秒。因此，当N=1e7时，时间约为1小时（即3800秒）。必须有一个更有效的方法。在

为函数计时

from timeit import Timer 
t = Timer(lambda: rand_M(1000))
print(t.timeit(5))
0.3863314103162543

Answer 1

洗牌，也就是说，置换怎么样？在

import random
import numpy
from timeit import Timer 

def B_rand_M(N):
    a = numpy.arange(1,9)
    M = numpy.zeros(shape = (8, N))
    for i in range (0, N):
        M[:, i] = numpy.random.permutation(a)
    return M

# your original implementation
def J_rand_M(N):
    M = numpy.zeros(shape = (8, N))
    for i in range (0, N):
        M[:, i] = numpy.random.choice(8, size = 8, replace = False) + 1 
    return M

一些时间安排：

^{pr2}$

给予

N = 10^0
time for J_rand_M(1): 0.001199
time for B_rand_M(1): 0.000080

N = 10^1
time for J_rand_M(10): 0.001112
time for B_rand_M(10): 0.000335

N = 10^2
time for J_rand_M(100): 0.011118
time for B_rand_M(100): 0.003022

N = 10^3
time for J_rand_M(1000): 0.110887
time for B_rand_M(1000): 0.030528

N = 10^4
time for J_rand_M(10000): 1.100540
time for B_rand_M(10000): 0.304696

N = 10^5
time for J_rand_M(100000): 11.151576
time for B_rand_M(100000): 3.049474

Answer 2

创建一个指定形状的随机数组，然后沿着要保持限制的轴进行排序，从而给我们一个矢量化的非常有效的解决方案。这将基于^{}到{a2}。这是实现-

样本运行-

In [122]: N = 10

In [123]: np.argsort(np.random.rand(8,N),axis=0)+1
Out[123]: 
array([[7, 3, 5, 1, 1, 5, 2, 4, 1, 4],
       [8, 4, 3, 2, 2, 8, 5, 5, 6, 2],
       [1, 2, 4, 6, 5, 4, 4, 3, 4, 7],
       [5, 6, 2, 5, 8, 2, 7, 8, 5, 8],
       [2, 8, 6, 3, 4, 7, 1, 1, 2, 6],
       [6, 7, 7, 8, 6, 6, 3, 2, 7, 3],
       [4, 1, 1, 4, 3, 3, 8, 6, 8, 1],
       [3, 5, 8, 7, 7, 1, 6, 7, 3, 5]], dtype=int64)

运行时测试-

^{pr2}$

因此，等待一个120x加速！在

Answer 3

我的直觉是O（n）是生成O（n）真正随机数时可能获得的最佳运行时。在

你试过用n=1000万运行你的代码吗？您假设当输入增长1000倍时，运行时将扩展1000倍，这在实践中可能是不正确的，因为在执行任何程序（加载库等）时，通常会有一个常量项，根据问题的不同，这一项可能很重要。在

也就是说，看起来the question linked by Eric Wright做了一个非常全面的工作，可以很容易地适应您的问题。在