Быстрое моделирование Монте-Карло с NumPy?

Question

Я следую упражнениям из «Выполнения байесовского анализа данных» на R и Python.

Я хотел бы найти быстрый метод симуляции Монте-Карло, который использует постоянное пространство .

Проблема ниже тривиальна, но служит хорошим тестом для различных методов:

из 4.3

Определите точную вероятность получения 10 из перетасованной колоды. (В колоде pinochle есть 48 карт. Есть шесть значений: 9, 10, Джек, Королева, Король, Туз. В каждой из четырех стандартных мастей по две копии каждого значения: сердца, алмазы, булавы, пики .)

(A) Какова вероятность получения 10?

Конечно, ответ 1/6.

Самое быстрое решение, которое я смог найти (сравнимое со скоростью R), - генерировать большой массив карт, используя np.random.choice, затем применяя Counter. Мне не нравится идея создания массивов без необходимости, поэтому я попытался использовать словарь и цикл for, вытягивая по одной карточке за раз и увеличивая количество для карточек такого типа. К моему удивлению, это было намного медленнее!

Полный код приведен ниже для 3 методов, которые я тестировал. Есть ли способ сделать это, который будет таким же быстродействующим, как method1 (), но с использованием постоянного пространства?

Код Python: ( ссылка Google Colab )

deck = [c for c in ['9','10','Jack','Queen','King','Ace'] for _ in range(8)]
num_draws = 1000000

def method1():
  draws = np.random.choice(deck, size=num_draws, replace=True)
  df = pd.DataFrame([Counter(draws)])/num_draws
  print(df)

def method2():
  card_counts = defaultdict(int)
  for _ in range(num_draws):
    card_counts[np.random.choice(deck, replace=True)] += 1
  df = pd.DataFrame([card_counts])/num_draws
  print(df)

def method3():
  card_counts = defaultdict(int)
  for _ in range(num_draws):
    card_counts[deck[random.randint(0, len(deck)-1)]] += 1
  df = pd.DataFrame([card_counts])/num_draws
  print(df)

Python timeit () результаты:

method1: 1,2997

method2: 23.0626

method3: 5.5859

R код:

card = sample(deck, numDraws, replace=TRUE)
print(as.data.frame(table(card)/numDraws))

Answer 1

Вот один с np.unique + np.bincount -

def unique():    
    unq,ids = np.unique(deck, return_inverse=True)
    all_ids = np.random.choice(ids, size=num_draws, replace=True)
    ar = np.bincount(all_ids)/num_draws
    return pd.DataFrame(ar[None], columns=unq)

Как NumPy помогает здесь?

Здесь нам помогают два основных улучшения:

1. Преобразуем строковые данные в числовые. NumPy хорошо работает с такими данными. Для этого мы используем np.unique.

2. Мы используем np.bincount для замены шага счета. Опять же, он хорошо работает с числовыми данными, и мы получили его из числового преобразования, сделанного в начале этого метода.

3. NumPy в целом хорошо работает с большими данными, как здесь.

---

Синхронизация с данным набором данных сравнения по сравнению с самыми быстрыми method1 -

In [177]: %timeit method1()
328 ms ± 16.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [178]: %timeit unique()
12.4 ms ± 265 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)