• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2020 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5/**
6 * @fileoverview Random helpers.
7 */
8
9'use strict';
10
11const assert = require('assert');
12
13function randInt(min, max) {
14  return Math.floor(Math.random() * (max - min + 1)) + min;
15}
16
17function choose(probability) {
18  return Math.random() < probability;
19}
20
21function random() {
22  return Math.random();
23}
24
25function uniform(min, max) {
26  return Math.random() * (max - min) + min;
27}
28
29function sample(iterable, count) {
30  const result = new Array(count);
31  let index = 0;
32
33  for (const item of iterable) {
34    if (index < count) {
35      result[index] = item;
36    } else {
37      const randIndex = randInt(0, index);
38      if (randIndex < count) {
39        result[randIndex] = item;
40      }
41    }
42
43    index++;
44  }
45
46  if (index < count) {
47    // Not enough items.
48    result.length = index;
49  }
50
51  return result;
52}
53
54function swap(array, p1, p2) {
55  [array[p1], array[p2]] = [array[p2], array[p1]];
56}
57
58/**
59 * Returns "count" elements, randomly selected from "highProbArray" and
60 * "lowProbArray". Elements from highProbArray have a "factor" times
61 * higher chance to be chosen. As a side effect, this swaps the chosen
62 * elements to the end of the respective input arrays. The complexity is
63 * O(count).
64 */
65function twoBucketSample(lowProbArray, highProbArray, factor, count) {
66  // Track number of available elements for choosing.
67  let low = lowProbArray.length;
68  let high = highProbArray.length;
69  assert(low + high >= count);
70  const result = [];
71  for (let i = 0; i < count; i++) {
72    // Map a random number to the summarized indices of both arrays. Give
73    // highProbArray elements a "factor" times higher probability.
74    const p = random();
75    const index = Math.floor(p * (high * factor + low));
76    if (index < low) {
77      // If the index is in the low part, draw the element and discard it.
78      result.push(lowProbArray[index]);
79      swap(lowProbArray, index, --low);
80    } else {
81      // Same as above but for a highProbArray element. The index is first
82      // mapped back to the array's range.
83      const highIndex = Math.floor((index - low) / factor);
84      result.push(highProbArray[highIndex]);
85      swap(highProbArray, highIndex, --high);
86    }
87  }
88  return result;
89}
90
91function single(array) {
92  return array[randInt(0, array.length - 1)];
93}
94
95function shuffle(array) {
96  for (let i = 0; i < array.length - 1; i++) {
97    const j = randInt(i, array.length - 1);
98    swap(array, i, j);
99  }
100
101  return array;
102}
103
104module.exports = {
105  choose: choose,
106  randInt: randInt,
107  random: random,
108  sample: sample,
109  shuffle: shuffle,
110  single: single,
111  twoBucketSample: twoBucketSample,
112  uniform: uniform,
113}
114