javascript - 在 Z 时间内从大小为 N 的数组中获取 Z 个随机项？

Question

我有一个大小为 N 的数组，它可以按某种方式排序。我想在 < O(N) 时间内从这个数组中获取 Z 个随机项。

我的理解是，如果我使用 Underscore 的 _.shuffle() 洗牌我的数组，这将花费 O(N) 时间。所以，洗牌然后抓取第一个 Z 项目已经过时了。

如果我在 N 之间生成 Z 个随机数，我想我会遇到非常丑陋的最坏情况。这是因为如果 N 大约是 105 而 Z 是 100.. 好吧，会有很多重叠，也许我会重掷 Z 几百次。

我想知道是否有一个简单的解决方案来解决这个问题？我没有看到任何专门针对该任务的 Underscore 方法。

Answer 1

这里有一些算法需要考虑:

A.随机播放

1. 随机排列数组； O(N)
2. 选择前 Z 个项目； O(Z) 或更好

整体复杂度:O(N)

function A(array, z) {
  return _.first(_.shuffle(array), z);
}

B.重新掷骰的随机选择

1. 从 0..N-1 中选择一个随机数； O(1)
2. 如果之前已经选过号码，则转到步骤1
3. 记录选择的号码； O(1)
4. 从给定索引处的数组中选择一个项目； O(1)
5. 如果我们选择的项目少于 Z，请转到第 1 步

整体复杂度:

对于 Z << N, O(Z) 平均情况

对于 Z = N，O(N^2) 平均情况

function B(array, z) {
  var pickedIndices = {};
  var result = [];
  while (result.length < z) {
    var randomIndex = Math.floor(Math.random() * array.length);
    if (!(randomIndex in pickedIndices)) {
      pickedIndices[randomIndex] = 1;
      result.push(array[randomIndex]);
    }
  }
  return result;
}

C.带移除的随机选择

1. 复制数组； O(N)
2. 从数组中随机选择一项； O(1)
3. 从数组中删除项目； O(N)
4. 如果我们选择的项目少于 Z，请转到第 2 步

整体复杂度:O(Z*N)

function C(array, z) {
  var result = [];
  array = array.slice(0);
  for (var i = 0; i < z; i++) {
    var randomIndex = Math.floor(Math.random() * array.length);
    result.push(array.splice(randomIndex, 1)[0]);
  }
  return result;
}

性能测试

http://jsperf.com/fetch-z-random-items-from-array-of-size-n

当 N = 100 和 Z = 10 时，算法 C 是最快的(可能是因为大多数逻辑使用原生函数和/或易于优化，对于较小的 N 和 Z 值，这比算法复杂性更重要).

当 N = 100 且 Z = 100 时，算法 A 是最快的。

当 N = 1000 且 Z = 100 时，算法 B 是最快的。

结论

在我考虑过的算法中没有最好的算法；这取决于您的数据的特征。如果您的数据的特征可能会有所不同，则可能值得进行进一步的测试并根据 N 和 Z 的值创建一些标准以有选择地选择最佳算法。

例如，如果 Z <= N/2，您可能会使用算法 B；否则，算法A。

简而言之，没有始终具有出色性能的“简单”解决方案。