根据权重从列表中抽取可变长度元素

Question

我想 select 根据每个元素的给定权重从列表中选择一些项目。输出的长度未知。这需要做很多次。

所以，假设我有一个像 [[1, 0.2], [2, 0.3], [3, 0.45], [4, 0.05], [5,1.]] 这样的 [id, probability] 的列表，我想得到像 [[1,3,5], [5], [3,5], [5], [1,2,4,5], ...]

这样的东西

这是我的代码。它有效，但速度很慢（列表很长，[id, probability] 的 10,000 多个元素，我的结果是数千 selection 长）。你知道有什么方法可以让这个（多）更快吗？

import numpy as np

items  = [[1, 0.2], [2, 0.3], [3, 0.45], [4, 0.05], [5,1.]]

combinations = []
for n in range(1000):
    selection = []
    for i in items:
        chosen = np.random.choice([True, False], p=[i[1], 1.-i[1]])
        if chosen:
            selection.append(i[0])
    combinations.append(selection)

Answer 1

您可以按如下方式矢量化采样步骤：

import numpy as np

# items  = [[1, 0.2], [2, 0.3], [3, 0.45], [4, 0.05], [5,1.]]
items = [(i, np.random.rand()) for i in range(1000)]

def sample_original(itms, n=1000):
  combinations = []
  for n in range(n):
      selection = []
      for i in items:
          chosen = np.random.choice([True, False], p=[i[1], 1.-i[1]])
          if chosen:
              selection.append(i[0])
      combinations.append(selection)


def sample_numpy(itms, n=1000):
  elts, probs = np.array(itms).T
  m = len(elts)
  return [elts[np.random.rand(m) < probs] for _ in range(n)]

主要观察结果是 np.random.rand(m) < probs 给出了 True/False 的随机向量，它以正确的概率选择原始列表中的元素。当有 1000 个项目时，这似乎快了 1000 倍：

%timeit sample_numpy(items)
%timeit sample_original(items)
10 loops, best of 3: 22.6 ms per loop
1 loop, best of 3: 21.9 s per loop

如果概率相对较高（结果选择并不稀疏），您可能希望将选择指示符存储在二维数组中以进一步提高性能。

根据权重从列表中抽取可变长度元素

Variable length element sampling from list based on weights

python

numpy

probability

choice