* Returns "count" elements, randomly selected from "highProbArray" and * "lowProbArray". Elements from highProbArray have a "factor" times * higher chance to be chosen. As a side effect, this swaps the chosen * elements to the end of the respective input arrays. The complexity is * O(count).
(lowProbArray, highProbArray, factor, count)
| 46 | * O(count). |
| 47 | */ |
| 48 | function twoBucketSample(lowProbArray, highProbArray, factor, count) { |
| 49 | // Track number of available elements for choosing. |
| 50 | let low = lowProbArray.length; |
| 51 | let high = highProbArray.length; |
| 52 | assert(low + high >= count); |
| 53 | const result = []; |
| 54 | for (let i = 0; i < count; i++) { |
| 55 | // Map a random number to the summarized indices of both arrays. Give |
| 56 | // highProbArray elements a "factor" times higher probability. |
| 57 | const p = random(); |
| 58 | const index = Math.floor(p * (high * factor + low)); |
| 59 | if (index < low) { |
| 60 | // If the index is in the low part, draw the element and discard it. |
| 61 | result.push(lowProbArray[index]); |
| 62 | swap(lowProbArray, index, --low); |
| 63 | } else { |
| 64 | // Same as above but for a highProbArray element. The index is first |
| 65 | // mapped back to the array's range. |
| 66 | const highIndex = Math.floor((index - low) / factor); |
| 67 | result.push(highProbArray[highIndex]); |
| 68 | swap(highProbArray, highIndex, --high); |
| 69 | } |
| 70 | } |
| 71 | return result; |
| 72 | } |
| 73 | |
| 74 | /** |
| 75 | * Returns a single random element from an array. |
no test coverage detected