在保持秩序的同时有效地随机抽样List

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

如果通过

维持值的顺序

您理解保持样本中的元素的顺序与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 ).

Answer 2

这是一个复杂的(更复杂的)替代方案O(n).你无法在复杂性方面做得更好(尽管你可以通过使用另一个集合来获得更好的性能,特别是具有恒定时间size实现的集合).我做了一个快速的基准测试,表明加速是非常可观的.

import scala.util.Random
import scala.annotation.tailrec

def sampledList[T](ls: List[T], sampleSize: Int) = {
  @tailrec
  def rec(list: List[T], listSize: Int, sample: List[T], sampleSize: Int): List[T] = {
    require(listSize >= sampleSize, 
      s"listSize must be >= sampleSize, but got listSize=$listSize and sampleSize=$sampleSize"
    )
    list match {
      case hd :: tl => 
        if (Random.nextInt(listSize) < sampleSize)
          rec(tl, listSize-1, hd :: sample, sampleSize-1)
        else rec(tl, listSize-1, sample, sampleSize)
      case Nil =>
        require(sampleSize == 0, // Should never happen
          s"sampleSize must be zero at the end of processing, but got $sampleSize"
        )
        sample
    }
  }
  rec(ls, ls.size, Nil, sampleSize).reverse
}

上述实现简单地遍历列表并根据设计为每个元素提供相同机会的概率保持(或不保持)当前元素.我的逻辑可能有一个流,但乍一看,这对我来说似乎是合理的.