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

我该如何修改最后的方法以获取唯一元素？有没有其他更优化的方式执行相同的任务？

- Asif

---

这三个元素的索引顺序必须是随机的吗？或者，例如，它们可以被排序吗？ - Tim

@Tim 随机排序 - Asif

我之所以问这个问题是因为将值制成一个“Set”来解决问题时，当值再次出现时会应用某种排序，因此它们在技术上不会是随机的。 - Tim

看一下Fisher-Yates shuffle。运行前三个迭代，使用选择的三个元素。如果您只想选三个元素，那么对整个数组进行洗牌是没有意义的。 - rossum

@rossum 那个算法要求改变原始数组，这可能是不可能的，或者创建一个包含每个索引的新数组，这将会很慢。但请将代码发布为答案，以便我们进行比较。 - Tim

Answer 1

你提供的例子似乎不相关（字符串？整数？），但也许这个例子可以用。

import scala.util.Random.nextInt

val limit = 1000  // 0 to 999 inclusive
val n = 3
Iterator.iterate(Set.fill(n)(nextInt(limit)))(_ + nextInt(limit))
        .dropWhile(_.size < n)
        .next()
//res0: Set[Int] = Set(255, 426, 965)

- jwvh

---

如果您希望结果真正随机，请使用ListSet。使用Set会使一些序列不可能出现，因为元素没有顺序。 - Tim

Answer 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)

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

- Tim

Answer 3

这是 Fisher-Yates 洗牌算法的一种变体。它不会修改原始数组，而是将索引数组随机打乱后再映射到原始数组上。通过添加一层间接引用，许多问题都可以得到解决。它不会完全打乱整个数组，只会打乱数组中的 num 项。

我不了解 Scala，所以这是伪代码：

partShuffle(num, originalArray)

  // 1. Make a copy of the original array's indices.
  indexAry <- new Array(originalArray.length)
  for (i <- 0; i < originalArray.length; i++)
    indexAry[i] <- i
  end for

  // 2. Shuffle num random unique indices to the front.
  for (i <- 0; i < num; i++)
    // 2.1 New pick from the unpicked part of the array.
    currentPick <- i + random(originalArray.length - i)

    // 2.2 Swap the current pick to the front of the array.
    temp <- indexAry[i]
    indexAry[i] <- indexAry[currentPick]
    indexAry[currentPick] <- temp
  end for

  // 3. Build the return array.
  returnAry <- new Array(num)
  for (i <- 0; i < num; i++)
    returnAry[i] <- originalAry[indexAry[i]]
  end for

  return returnAry

end partShuffle()

当你选择一个索引时，它会被交换到索引数组的前面并从进一步的选择中排除。第一个选择来自[0..size-1]；第二个选择来自[1..size-1]；第三个选择来自[2..size-1]等等。所选原始数组中的索引将在较短的数组中返回，长度为num。

假设：

• 数组是以零为基础的
• indexAry是一个整数数组
• returnAry与originalAry相同
• random()在代码的其他地方进行了初始化
• random(x)返回从0（包括）到x（不包括）的整数

- rossum

Answer 4

你可以在边界之间生成随机索引。通过逻辑将列表分成n个部分来生成边界值。

例如：给定一个包含100个元素的列表，n为3，则边界将是 (0,32) (33,65) (66,99)

  // Gets random int between "start" and "end"
  def randomInt(start: Int, end: Int): Int =
    start + scala.util.Random.nextInt((end - start) + 1)

  // Generates random int; given limit, total number of chunks and nth chunk
  def randomIntN(limit: Int, n: Int, nth: Int): Int =
    randomInt(
      (((limit / n) * nth) - (limit / n)),
      (((limit / n) * nth) - (if (n == nth) 0 else 1))
    )

  // Generate sequence
  for (
    i <- 1 to n;
    r = randomIntN(xs.size, n, i)
  ) yield xs(r)

以下是一些输出结果

res4: IndexedSeq[Int] = Vector(60, 50, 57)
res5: IndexedSeq[Int] = Vector(60, 85, 34)
res6: IndexedSeq[Int] = Vector(24, 50, 41)

- bellam

---

这不是随机的；你总会有来自每个范围的一个值。 - Tim

每个范围内的一个随机值。但我理解你的意思。 - bellam