Wie kann man aus einer Scala-Liste oder einem Array zufällig Stichproben ziehen?

Question

Ich möchte aus einer Scala Liste oder Array zufällig auf Probe (kein RDD) kann die Probengröße wesentlich länger ist als die Länge der Liste oder Array, wie kann ich diese tun effizient? Da die Probengröße sehr groß sein kann und die Probenahme (auf verschiedenen Listen/Arrays) benötigt eine große Anzahl von Malen durchgeführt werden.

ich für eine Spark wissen RDD können wir takeSample() verwenden, es zu tun, ist es ein Äquivalent für Scala Liste/Array?

Vielen Dank.

Answer 1

Für Arrays:

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

Sie einen Zufallszahlengenerator (rnd), basierend auf dem Samen. Füllen Sie dann ein Array mit Zufallszahlen von 0 bis zur Größe Ihres Arrays.

Der letzte Schritt ist die Anwendung jeder Zufallswert an den Indexierungs Bediener des Eingangsfeldes. Mit ihm in der REPL könnte wie folgt aussehen:

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) 

Für Listen, würde ich einfach die Liste Array umwandeln und die gleiche Funktion verwenden. Ich bezweifle, dass du sowieso viel effizienter für Listen werden kannst.

Es ist wichtig zu beachten, dass das gleiche Funktionslisten unter Verwendung nimmt O würde (n^2) Zeit, während die Liste Umwandeln erstes O wird, um Arrays (n) Zeit

Answer 2

Ein einfach zu -Verstehen Version würde wie folgt aussehen:

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

eine Verwendung für das Verständnis für ein gegebenes Array xs wie folgt

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

Hinweis der Zufallsgenerator erzeugt hier die Werte innerhalb des Einheitsintervalls, das die Größe des Arrays -umspannen skaliert sind, und zu Int zum Indexieren über die Anordnung umgewandelt.

Hinweis Für reine Funktions Zufallsgenerator zum Beispiel aus Functional Programming in Scala, diskutiert den Staat Monad Ansatz betrachten here.

Hinweis Beachten Sie auch NICTA, eine andere rein funktionale Zufallswertgenerator, es Verwendung zum Beispiel here dargestellt ist.

Answer 4

Mit klassischen Rekursion.

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

Entweder:

• Mixin SeqHelpers zum Beispiel mit einem Scalatest spec
• Fügen import your.pkg.SeqHelpers._

die dann folgenden sollte funktionieren:

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

Bearbeitungen zum Entfernen der Besetzung sind willkommen.

Auch wenn es eine Möglichkeit gibt, eine leere Instanz der Sammlung für den Akkumulator zu erstellen, ohne vorher den konkreten Typ zu kennen, kommentieren Sie bitte. Das heißt, der Erbauer ist wahrscheinlich effizienter.

Answer 6

Wenn Sie ohne Ersatz probieren möchten - RV mit randoms, sortieren O(n*log(n), randoms verwerfen, nehmen

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)