performance - 在保持顺序的同时有效地随机抽样列表

Question

我想在保持顺序的同时从非常大的列表中随机抽取样本。我写了下面的脚本，但是它需要 .map(idx => ls(idx)) 这很浪费。我可以看到一种通过辅助函数和尾递归提高效率的方法，但我觉得必须有一个我缺少的更简单的解决方案。

有没有更干净、更有效的方法来做到这一点？

import scala.util.Random

def sampledList[T](ls: List[T], sampleSize: Int) = {
  Random
    .shuffle(ls.indices.toList)
    .take(sampleSize)
    .sorted
    .map(idx => ls(idx))
}

val sampleList = List("t","h","e"," ","q","u","i","c","k"," ","b","r","o","w","n")
// imagine the list is much longer though

sampledList(sampleList, 5) // List(e, u, i, r, n)

编辑: 看来我不清楚:我指的是维护值的顺序，而不是原始的 List 集合。

Answer 1

如果通过

maintaining the order of the values

您了解如何使示例中的元素与 ls 列表中的元素保持相同的顺序，然后通过对原始解决方案进行小的修改，可以大大提高性能:

import scala.util.Random

def sampledList[T](ls: List[T], sampleSize: Int) = {
  Random.shuffle(ls.zipWithIndex).take(sampleSize).sortBy(_._2).map(_._1)
}

此解决方案的复杂度为 O(n + k*log(k))，其中 n 是列表的大小，k 是样本大小，而您的解决方案是 O(n + k * log(k) + n*k).