从数组中随机选择n个元素

Asif 发表于 Dev

127

阿西夫

我想从数组中选择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次。

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

提姆

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

它建立索引列表，然后检查值是否不同。在极少数情况下，如果有重复项，则会将其删除并添加新值，直到有一组独特的索引为止。

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

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)

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。