Come campionare casualmente da una lista Scala o array?

Question

Voglio campionare casualmente da una lista Scala o array (non da un RDD), la dimensione del campione può essere molto più lunga della lunghezza della lista o della matrice, come posso fare questo efficientemente? Perché la dimensione del campione può essere molto grande e il campionamento (su diversi elenchi/matrici) deve essere fatto un gran numero di volte.

So che per uno Spark RDD possiamo usare takeSample() per farlo, esiste un equivalente per Scala list/array?

Grazie mille.

Answer 1

Per gli array:

import scala.util.Random 
import scala.reflect.ClassTag 

def takeSample[T:ClassTag](a:Array[T],n:Int,seed:Long) = { 
    val rnd = new Random(seed) 
    Array.fill(n)(a(rnd.nextInt(a.size))) 
} 

Fai un generatore di numeri casuali (rnd) in base al seme. Quindi, riempire una matrice con numeri casuali da 0 fino alla dimensione della matrice.

L'ultimo passaggio consiste nell'applicare ogni valore casuale all'operatore di indicizzazione dell'array di input. Usandolo in REPL potrebbe apparire come segue:

scala> val myArray = Array(1,3,5,7,8,9,10) 
myArray: Array[Int] = Array(1, 3, 5, 7, 8, 9, 10) 

scala> takeSample(myArray,20,System.currentTimeMillis) 
res0: scala.collection.mutable.ArraySeq[Int] = ArraySeq(7, 8, 7, 3, 8, 3, 9, 1, 7, 10, 7, 10, 
1, 1, 3, 1, 7, 1, 3, 7) 

Per le liste, vorrei semplicemente convertire la lista di array e utilizzare la stessa funzione. Dubito che puoi ottenere molto più efficiente per le liste comunque.

E 'importante notare che la stessa funzione utilizzando gli elenchi prenderebbe O (n^2) tempo, mentre convertendo la lista agli array prima avrà O (n)

Answer 2

Un facile da -Comprendere versione sarebbe simile a questa:

import scala.util.Random 

Random.shuffle(list).take(n) 
Random.shuffle(array.toList).take(n) 

// Seeded version 
val r = new Random(seed) 
r.shuffle(...) 

Answer 3

Usando una di comprensione, per un dato array xs come segue,

for (i <- 1 to sampleSize; r = (Math.random * xs.size).toInt) yield a(r) 

Nota il generatore casuale qui produce valori all'interno dell'intervallo unitario, che vengono ridimensionati per coprire le dimensioni della matrice e convertiti in Int per l'indicizzazione sull'array.

Nota Per puro generatore casuale funzionale considerare ad esempio l'approccio Stato Monade da Functional Programming in Scala, discusso here.

Nota consideri inoltre NICTA, un altro generatore puro valore casuale funzionale, è uso illustrato per esempio here.

Answer 4

Uso della ricorsione classica.

import scala.util.Random 

def takeSample[T](a: List[T], n: Int): List[T] = { 
    n match { 
     case n: Int if n <= 0 => List.empty[T] 
     case n: Int => a(Random.nextInt(a.size)) :: takeSample(a, n - 1) 
    } 
} 

Answer 5

package your.pkg 

import your.pkg.SeqHelpers.SampleOps 

import scala.collection.generic.CanBuildFrom 
import scala.collection.mutable 
import scala.language.{higherKinds, implicitConversions} 
import scala.util.Random 

trait SeqHelpers { 

    implicit def withSampleOps[E, CC[_] <: Seq[_]](cc: CC[E]): SampleOps[E, CC] = SampleOps(cc) 
} 

object SeqHelpers extends SeqHelpers { 

    case class SampleOps[E, CC[_] <: Seq[_]](cc: CC[_]) { 

    private def recurse(n: Int, builder: mutable.Builder[E, CC[E]]): CC[E] = n match { 
     case 0 => builder.result 
     case _ => 
     val element = cc(Random.nextInt(cc.size)).asInstanceOf[E] 
     recurse(n - 1, builder += element) 
    } 

    def sample(n: Int)(implicit cbf: CanBuildFrom[CC[_], E, CC[E]]): CC[E] = { 
     require(n >= 0, "Cannot take less than 0 samples") 
     recurse(n, cbf.apply) 
    } 
    } 
} 

O:

• Mixin SeqHelpers, per esempio, con una specifica ScalaTest
• Includere import your.pkg.SeqHelpers._

Poi il seguente dovrebbe funzionare:

Seq(1 to 100: _*) sample 10 foreach { println } 

Le modifiche per rimuovere il cast sono le benvenute.

Inoltre, se esiste un modo per creare un'istanza vuota della raccolta per l'accumulatore, senza conoscere il tipo concreto in anticipo, si prega di commentare. Detto questo, il costruttore è probabilmente più efficiente.

Answer 6

Se volete assaggiare senza sostituzione - ZIP con randoms, sorta O(n*log(n), scartare randoms, prendere

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)