Выборка элемента переменной длины из списка на основе весов - PullRequest
Новая
       12

Выборка элемента переменной длины из списка на основе весов

0 голосов
/ 24 февраля 2020

Я хочу выбрать некоторые элементы из списка в зависимости от заданного веса для каждого элемента. Длина вывода не известна. Это нужно делать много раз.

Итак, скажем, у меня есть список [id, probability] вроде [[1, 0.2], [2, 0.3], [3, 0.45], [4, 0.05], [5,1.]], я хочу получить что-то вроде [[1,3,5], [5], [3,5], [5], [1,2,4,5], ...]

Вот мой код сделать это. Это работает, но довольно медленно (список длинный, более 10000 элементов [id, probability], а мой результат - тысячи 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)

1 Ответ

1 голос
/ 24 февраля 2020

Вы можете векторизовать шаг выборки следующим образом: 

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

Если вероятности относительно высоки (результирующие выборы не редки), вы можете сохранить индикаторы выбора в двумерном массиве для дальнейшей производительности прибыль.

...