从 Array 中随机选择 n 个元素

Question

我想从数组中选择n 个唯一元素，其中数组的大小通常为1000并且n 的值为3。我想在迭代算法中实现这个，其中迭代大约为3000000，我必须在每次迭代中获得 n 个唯一元素。这里有一些我喜欢的可用解决方案，但由于它们的缺点，我无法使用它们，如下所述。

import scala.util.Random
val l = Seq("a", "b", "c", "d", "e")
val ran = l.map(x => (Random.nextFloat(), x)).sortBy(_._1).map(_._2).take(3)

此方法较慢，因为必须创建三个数组并对数组进行排序。

 val list = List(1,2,3,4,5,1,2,3,4,5)
 val uniq = list.distinct
 val shuffled = scala.util.Random.shuffle(uniq)
 val sampled = shuffled.take(n)

生成两个数组并且对大数组进行混洗是较慢的过程。

 val arr = Array.fill(1000)(math.random )
 for (i <- 1 to n; r = (Math.random * xs.size).toInt) yield arr(r)

这是一种更快的技术，但有时会多次返回相同的元素。这是一个输出。

val xs = List(60, 95, 24, 85, 50, 62, 41, 68, 34, 57)
for (i <- 1 to n; r = (Math.random * xs.size).toInt) yield xs(r)

res: scala.collection.immutable.IndexedSeq[Int] = Vector( 24 , 24 , 41)

可以观察到24返回了2 次。

如何更改最后一种方法以获取唯一元素？是否有其他更优化的方法来执行相同的任务？

Answer 1

这是一个递归例程，它比其他答案更有效地完成这项工作。

它构建一个索引列表，然后检查这些值是否不同。在极少数情况下，存在重复项，这些重复项将被删除并添加新值，直到出现一组不同的索引。

其他答案检查每次添加元素时列表是否不同。

def randomIndices(arraySize: Int, nIndices: Int): List[Int] = {
  def loop(done: Int, res: List[Int]): List[Int] =
    if (done < nIndices) {
      loop(done + 1, (Math.random * arraySize).toInt +: res)
    } else {
      val d = res.distinct
      val dSize = d.size

      if (dSize < nIndices) {
        loop(dSize, d)
      } else {
        res
      }
    }

  if (nIndices > arraySize) {
    randomIndices(arraySize, arraySize)
  } else {
    loop(0, Nil)
  }
}

randomIndices(xs.size, 3).map(xs)

当元素数量与数组大小相比较小时，这应该是有效的。