Эффективная случайная выборка - PullRequest
0 голосов
/ 24 июня 2018

Моя проблема проста: у меня есть массив с 20 миллионами операций с плавающей запятой.В этом массиве каждый float имеет вероятность случайного изменения p .

Самый простой способ сделать это - перемещаться по массиву, делая if (rand (0,1)

Однако, даже паралелизацию, она медленная до чертиков, и я подумал, есть ли более быстрый способ случайным образом получить некоторые индексы для изменения.

Моей первой мыслью было выбратьup p * n случайных чисел, где n - общее число чисел с плавающей точкой в ​​массиве, однако это не точно отражает распределение вероятностей, поскольку ничто в первом случае не гарантирует, что будут изменены только числа с плавающей точкой p * n.

Идеи?

PD: Я использую python для реализации, возможно, кто-то имел эту проблему раньше и что-то реализовал в библиотеках, но я не могу ее найти.

Ответы [ 5 ]

0 голосов
/ 25 июня 2018

Если p мало, вы можете сэкономить много времени, используя numpy.random.geometric, чтобы обеспечить выборку расстояний между изменяемыми элементами.

Простой проход по массиву ary:

from numpy.random import geometric

index = -1
while True:
  index += geometric(0.01)
  if index >= len(ary):
    break
  ary[ind] = # compute new value

Функции распределения Numpy могут создавать массив возвращаемых значений, поэтому, пока p мало, возможно, даже быстрее получить все значения шага одновременно:

from numpy import cumsum
from numpy.random import geometric

for index in cumsum(geometric(p, size=int(len(ary) * p * 1.1))):
  if index < len(ary):
    ary[index] = # compute new value

1.1 - выдумкафактор, чтобы убедиться, что достаточно выборок из геометрического распределения.Для больших массивов это должно быть хорошо, но это не гарантировано.Лучшим (хотя и более сложным) решением было бы создание сэмплов, скажем, 10000, и продолжайте делать это до тех пор, пока вам не удастся добраться до конца массива.

0 голосов
/ 24 июня 2018

Это работает ~ 4 сек / раунд на моей машине

import random

rand = random.random
p = 0.1
TOTAL_ROUND = 10

x = [rand() for i in xrange(20000000)]

for i in range(TOTAL_ROUND):
    print "round", i
    x = [rand() if val < p else val for val in x]
0 голосов
/ 24 июня 2018

Вы можете сгенерировать случайный массив со значениями в [0,1) того же размера n, что и ваш вектор данных, используя

rnd = np.random.rand(n)

Теперь вы проверяете, по каким индексам эти случайные значения меньше p

mask = rnd < p

и теперь измените данные по всем индексам, которые были включены в маску, например ::

data[mask]=np.random.rand(data[mask].size)  

или любым другим способом, которым вы хотите изменить данные.

0 голосов
/ 24 июня 2018

Ваш массив:

array = np.random.random(size=100) # Whatever

Массив случайных 0/1:

p = 0.05 # Could be an array itself
markers = np.random.binomial(1, p, array.shape[0])

Массив индексов значений, которые будут изменены:

locations = np.where(markers)[0]
# Something like array([19, 29, 32, 67, 68, 71])

Вы перебираете исходный массив, используя эти индексы, или изменяете все значения одновременно, например, array[locations] = ...

0 голосов
/ 24 июня 2018

Во-первых, если p высокое, т. Е.> = 0.5, вы не сэкономите много времени, чем бы вы ни занимались, потому что вы все равно можете посетить большинство элементов. Однако, если p ниже, вы можете извлечь из биномиального распределения с n = 20M и вашей вероятностью определить, сколько элементов нужно коснуться.

In [23]: np.random.binomial(20*10**6, 0.1)
Out[23]: 1999582

In [24]: np.random.binomial(20*10**6, 0.99999)
Out[24]: 19999801

In [25]: np.random.binomial(20*10**6, 0.5)
Out[25]: 10001202

In [26]: np.random.binomial(20*10**6, 0.0001)
Out[26]: 1986
[...]
In [30]: np.random.binomial(20*10**6, 0.0001)
Out[30]: 1989

In [31]: np.random.binomial(20*10**6, 0.0001)
Out[31]: 1988

Это число - число успехов, предполагающих n испытаний, каждое из которых имеет p шансов на успех, что в точности соответствует вашей ситуации.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...