Как сохранить случайное подмножество потока данных? - PullRequest
Новая
       10

Как сохранить случайное подмножество потока данных?

14 голосов
/ 03 декабря 2010

У меня есть поток событий, проходящий через мои серверы.Я не могу хранить все из них, но я хотел бы периодически иметь возможность обрабатывать некоторые из них в совокупности.Итак, я хочу сохранить подмножество потока, которое является случайной выборкой всего, что я видел, но ограничено максимальным размером.

Итак, для каждого нового элемента мне нужен алгоритм, чтобы решить, должен ли я добавить его к сохраненному набору или отказаться от него.Если я добавлю это, и я уже нахожусь на своем пределе, мне нужен алгоритм, чтобы выселить один из старых предметов.

Очевидно, это легко, пока я не достигаю своего предела (просто сохраняйте все).Но как я могу поддерживать хорошую случайную выборку, не склоняясь к старым предметам или новым предметам, когда я превышаю этот предел?

Спасибо,

Ответы [ 6 ]

6 голосов
/ 03 декабря 2010

Это обычный вопрос для интервью.

Один простой способ сделать это - сохранить n-й элемент с вероятностью k / n (или 1, в зависимости от того, что меньше).Если вам нужно удалить элемент для сохранения нового образца, удалите случайный элемент.

Это дает вам равномерно случайное подмножество из n элементов.Если вы не знаете n, вы можете оценить его и получить приблизительно равномерное подмножество.

5 голосов
/ 31 января 2014

Это называется случайной выборкой. Источник: http://en.wikipedia.org/wiki/Reservoir_sampling

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

Достойное объяснение / доказательство: http://propersubset.com/2010/04/choosing-random-elements.html

1 голос
/ 03 декабря 2010

хранить выборки в очереди «первым пришел - первым обслужен» (FIFO).

установите частоту дискретизации такого большого количества событий между выборками или немного ее рандомизируйте - в зависимости от ваших шаблонов событий.

сохраняйте каждое n-е событие или всякий раз, когда ваша ставка говорит вам об этом, затем вставьте его в конец очереди.

выскочить один сверху, если размер слишком велик.

1 голос
/ 03 декабря 2010

Хотя эта статья не совсем то, что вы ищете, она может стать хорошей отправной точкой в ​​вашем поиске.

0 голосов
/ 03 декабря 2010

Предполагается, что вы не знаете общее количество событий, которые будут получены, и вам не нужно минимальное количество элементов в подмножестве. 

arr = arr[MAX_SIZE] //Create a new array that will store the events. Assuming first index 1.
counter = 1 //Initialize a counter.

while(receiving event){
  random = //Generate a random number between 1 and counter
  if( counter == random ){
     if( counter <= MAX_SIZE ){
        arr[counter] = event
     }
     else{
        tmpRandom = //Generate a random number between 1 and MAX_SIZE
        arr[tmpRandom] = event
     }
  }
  counter =+ 1

}
0 голосов
/ 03 декабря 2010

Назначьте вероятность записи каждого события и сохраните событие в индексируемой структуре данных. Когда размер структуры достигнет порога, удалите случайный элемент и добавьте новые элементы. В Ruby вы можете сделать это: 

@storage = []
prob = 0.002

while ( message = getnextMessage) do
    @storage.delete((rand() * @storage.length).floor) if @storage.length > MAX_LEN
    @storage << message if (rand() < prob) 
end

Это относится к вашему максимальному размеру и вашему непредвзятому отношению к тому, когда произошло событие. Вы также можете выбрать, какой элемент будет удален, разбив свои сохраненные элементы на сегменты, а затем удалив элемент из любого сегмента, содержащего более одного элемента. Например, метод bucket позволяет хранить по одному на каждый час.

Вы также должны знать, что теория выборки - это Big Math. Если вам нужно нечто большее, чем просто идея об этом, вы должны проконсультироваться с квалифицированным математиком в вашем районе.

...