0

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

我的理解是，如果我使用 Underscore 的 _.shuffle() 对数组进行洗牌，这将花费 O(N) 时间。所以，洗牌然后抓住第一个 Z 项目就结束了。

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

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

4

2 回答 2

2

以下是一些需要考虑的算法：

A. 随机播放

  1. 洗牌数组；上）
  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. 制作数组的副本；上）
  2. 从数组中选择一个随机项；O(1)
  3. 从数组中删除项目；上）
  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。

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

于 2013-04-30T15:45:18.260 回答
1

我不认为我完全理解你的问题，但是如果你想从一个数组中获取一个随机元素并且它不被重复，因此你被限制滚动的次数少于元素，那么你可以尝试这个

function shuffle(obj, rounds, deep) {
  var length = obj.length;
  if (length < 2) {
    return;
  }

  var rounds32 = rounds >>> 0 || 1;
  var deepBool = deep === true;
  var roundCount = 0;
  var index, rnd, tmp;
  while (roundCount < rounds32) {
    index = length;
    while (index) {
      if (Array.isArray(obj[index - 1])) {
        shuffle(obj[i], rounds32, deepBool);
      }

      rnd = Math.floor(Math.random() * index);
      index -= 1;
      tmp = obj[index];
      obj[index] = obj[rnd];
      obj[rnd] = tmp;
    }

    roundCount += 1;
  }
}

var array = [];
for (var count = 0; count < 100; count += 1) {
  array.push(count);
}

shuffle(array);

var rolls = 10;
console.log(array.slice(0, rolls));

于 2013-04-27T03:04:53.383 回答