如何從Scala數組中有效地進行採樣

我想從一個Scala數組中抽樣，樣本大小可能比數組長度大得多。我怎樣纔能有效地？通過使用下面的代碼的運行時間是線性的樣本量，當樣本量是非常大的它是緩慢的，如果我們需要做多次抽檢：如何從Scala數組中有效地進行採樣

def getSample(dataArray: Array[Double], sampleSize: Int, seed: Int): Array[Double] = 
{ 
    val arrLength = dataArray.length 
    val r = new scala.util.Random(seed) 
    Array.fill(sampleSize)(dataArray(r.nextInt(arrLength))) 
} 

val myArr= Array(1.0,5.0,9.0,4.0,7.0) 
getSample(myArr, 100000, 28)

來源

2015-10-06 Carter

你確定這是你的瓶頸？即使有100萬個樣本，上述程序在47 ms內完成。這些操作速度非常快，所以我的另一個問題是爲什麼你甚至需要打算預先計算大量的操作。爲什麼不能根據需要隨時計算它們？ – JimN

有沒有辦法解決它。如果您需要使用具有恆定時間元素訪問權限的N個元素，則無論如何複雜度將爲O(n)（線性）。

您可以通過使其懶惰來減免/攤銷成本。例如，您可以返回一個Stream或Iterator，在您訪問它時評估每個元素。這將有助於節省內存使用量，因爲如果您可以摺疊該流，則可以節省內存使用量。換句話說，您可以跳過複製部分並直接使用初始數組 - 並非總是可行，取決於任務。

來源

2015-10-06 02:42:34

感謝您的回覆。有沒有辦法同時進行採樣？例如，我們有10個線程，每個線程獲得10000個樣本元素，然後我們將所有這些樣本元素組合在一起以獲得最終的抽樣結果？ – Carter

並行處理集合的最簡單方法是使用'par'（http://docs.scala-lang.org/overviews/parallel-collections/overview.html）。有時它可能讓事情變慢而不是變快。你可以用你喜歡的'Future'，'Akka'等任何併發框架分割工作。 –

爲了使此採樣程序運行得更快，請使用Akka actor框架並行運行採樣作業。創建一個主要角色，將抽樣作品分發給工作人員，並將不同工作人員的元素進行連接。因此，每位工人演員都會準備/收集固定數量的樣本元素，並將所得到的集合作爲不可變數組返回給主人。在接收到來自Worker的'WorkDone'用戶定義消息後，主角色將元素連接到最終集合中。

來源

2015-10-06 03:59:23

長度爲$ n $的數組中的任何給定元素在大小爲$ k $的樣本中至少出現過一次的概率爲$ 1-（1-1/n）^ k $。如果這個值接近1，相對於$ N $ $ķ$大發生，那麼下面的算法可能會根據您的需要是一個不錯的選擇：

import org.apache.commons.math3.random.MersennseTwister 
import org.apache.commons.math3.distribution.BinomialDistribution 

def getSampleCounts[T](data: Array[T], k: Int, seed: Long): Array[Int] = { 
    val rng = new MersenneTwister(seed) 
    val counts = new Array[Int](data.length) 
    var i = k 
    do { 
    val j = new BinomialDistribution(rng.nextLong(), i, 1.0/i) 
    counts(i) = j 
    i -= j 
    } while (i > 0) 
    counts 
}

注意，這種算法不返回一個樣品。相反，它會返回一個Array[Int]，它的$ i $ -th條目等於data(i)出現在隨機樣本中的次數。這可能不適用於所有應用程序，但對於某些使用情況（例如，可通過data.view.zip(getSampleCounts(data, k, seed))獲得）的某種類型的Iterable以上（value，count）對的樣例，實際上非常方便，因爲它經常使我們能夠對樣本組進行一次計算（因爲它們相同）。例如，假設我有一個昂貴的函數f: T => Double，並且我想計算應用於大小爲$ k $的隨機樣本的樣本均值fdata。然後我們可以做到以下幾點：

data.view.zip(getSampleCounts(data, k, seed)).map({case (x, count) => f(x)*count}).sum/k

這個計算的樣本均值計算f $ N $，而不是$ķ$倍（還記得我們假設$ķ$相比，$ n $的大。）

請注意，getSampleCounts將最多循環$ n $次，其中$ n $爲data.length。另外，假設在apache.commons.math3庫中以合理的方式完成每次迭代中二項分佈的採樣，則複雜度應不低於$ O（\ log k）$（反CDF方法和二分搜索）。）因此，上述算法的複雜性是$ O（n \ log k）$，其中$ n $是data.length，$ k $是要繪製的樣本數。

來源

2015-10-06 06:12:32

它很容易與一個列表。使用下面的隱函數

object ListImplicits { 
    implicit class SampledArray[T](in: List[T]) { 
    def sample(n: Int, seed:Option[Long]=None): List[T] = { 
     seed match { 
     case Some(s) => Random.setSeed(s) 
     case _ => // nothing 
     } 
     Random.shuffle(in).take(n) 
    } 
    } 
}

，然後導入對象，並使用集合轉換爲從Array切換到列表（少量的開銷）：

import ListImplicits.SampledArray 
val n = 100000 
val list = (0 to n).toList.map(i => Random.nextInt()) 
val array = list.toArray 

val t0 = System.currentTimeMillis() 
array.toList.sample(5).toArray 
val t1 = System.currentTimeMillis() 
list.sample(5) 
val t2 = System.currentTimeMillis() 

println("Array (conversion) => delta = " + (t1-t0) + " ms") // 10 ms 
println("List => delta = " + (t2-t1) + " ms") // 8 ms

來源

2017-05-19 13:30:17 Boris

如何從Scala數組中有效地進行採樣

回答

相關問題