# Difference between revisions of "TADM2E 2.43"

From Algorithm Wiki

(Recovering wiki) |
(Alternative solution to TADME2E 2.43) |
||

Line 1: | Line 1: | ||

Whether we know <math>n</math> or not we can sample <math>k</math> values uniformly by assigning a random value to each element, sorting, and taking the top <math>k</math> values. However, this is not very efficient so instead we can use a <i>priority queue</i> of size <math>k</math> with random priority. | Whether we know <math>n</math> or not we can sample <math>k</math> values uniformly by assigning a random value to each element, sorting, and taking the top <math>k</math> values. However, this is not very efficient so instead we can use a <i>priority queue</i> of size <math>k</math> with random priority. | ||

+ | |||

+ | Alternatively, we can iterate over the elements in <math>S</math> from <math>i = 0</math> until <math>S[i]</math> is empty. If <math>i < k</math>, <math>S'[i] = S[i]</math>. After that, for each <math>i</math>, replace a random element in <math>S'</math> with <math>S[i]</math>, with probability <math>\frac{k}{i + 1}</math> of performing the replacement rather than skipping to the next. | ||

Return to [[Algo-analysis-TADM2E]] ... | Return to [[Algo-analysis-TADM2E]] ... |

## Revision as of 06:49, 18 May 2015

Whether we know $ n $ or not we can sample $ k $ values uniformly by assigning a random value to each element, sorting, and taking the top $ k $ values. However, this is not very efficient so instead we can use a *priority queue* of size $ k $ with random priority.

Alternatively, we can iterate over the elements in $ S $ from $ i = 0 $ until $ S[i] $ is empty. If $ i < k $, $ S'[i] = S[i] $. After that, for each $ i $, replace a random element in $ S' $ with $ S[i] $, with probability $ \frac{k}{i + 1} $ of performing the replacement rather than skipping to the next.

Return to Algo-analysis-TADM2E ...