python 2 的高性能加权随机选择？

Question

我有以下python方法，它从序列"seq"中选择一个加权运行dom元素运行domly由其他序列加权，其中包含权重对于 seq 中的每个元素：

def weighted_choice(seq, weights):
    assert len(seq) == len(weights)

    total = sum(weights)
    r = random.uniform(0, total)
    upto = 0
    for i in range(len(seq)):
        if upto + weights[i] >= r:
            return seq[i]
        upto += weights[i]
    assert False, "Shouldn't get here"

如果我用 1000 个元素的序列调用上面一百万次，如下所示：

seq = range(1000)
weights = []
for i in range(1000):
    weights.append(random.randint(1,100))

st=time.time()
for i in range(1000000):
    r=weighted_choice(seq, weights)
print (time.time()-st)

it 运行s 在 cpython 2.7 中大约 45 秒，在 cpython 3.6 中大约 70 秒。在 pypy 5.10 中它在 2.3 秒左右完成，这对我来说很好，遗憾的是由于某些原因我不能使用 pypy。

关于如何在 cpython 上加速这个函数有什么想法吗？我对其他实现（算法上或通过外部库，如 numpy）也很感兴趣，如果它们表现更好的话。

ps: python3 有 random.choices 有权重，它运行s 大约 23 秒，比上面的函数好，但仍然正好是十比 pypy 慢 1 倍运行.

我已经用 numpy 试过了：

weights=[1./1000]*1000
st=time.time()
for i in range(1000000):
    #r=weighted_choice(seq, weights)
    #r=random.choices(seq, weights)
    r=numpy.random.choice(seq, p=weights)
print (time.time()-st)

它运行 70 秒。

Answer 1

你可以使用numpy.random.choice（p参数是权重）。通常 numpy 函数是向量化的，因此运行速度 near-C。

实施为：

def weighted_choice(seq, weights):
    w = np.asarray(weights)
    p = w / w.sum()  # can skip if weights always sum to 1
    return np.random.choice(seq, p=w)

编辑：

时间：

%timeit np.random.choice(x, p=w)  # len(x) == 1_000_000
13 ms ± 238 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit np.random.choice(y, p=w)  # len(y) == 100_000_000
1.28 s ± 18.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

您可以在 numpy 中采用这种方法。如果你简化 for 循环，你可以通过索引你需要的位置来获得 numpy 的真正力量

#Untimed since you did not
seq = np.arange(1000)
weights = np.random.randint(1,100,(1000,1))


def weights_numpy(seq,weights,iterations):
    """
    :param seq: Input sequence
    :param weights: Input Weights
    :param iterations: Iterations to run
    :return: 
    """
    r = np.random.uniform(0,weights.sum(0),(1,iterations)) #create array of choices
    ar = weights.cumsum(0) # get cumulative sum
    return seq[(ar >= r).argmax(0)] #get indeces of seq that meet your condition

和时间 (python 3,numpy '1.14.0')

%timeit weights_numpy(seq,weights,1000000)
4.05 s ± 256 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

比 PyPy 慢一点，但几乎...

python 2 的高性能加权随机选择？

High performance weighted random choice for python 2?

python

random

pypy

numpy