Самый быстрый взвешенный случайный алгоритм в Scala?

Question

Я пишу серверный модуль для проекта на основе Scala, и мне нужно найти самый быстрый способ для генерации взвешенного случайного числа между некоторыми весами Int. Метод должен быть максимально быстрым, поскольку он будет называться очень часто.

Теперь, это то, что я придумал:

import scala.util.Random 

trait CumulativeDensity { 

    /** Returns the index result of a binary search to find @n in the discrete 
    * @cdf array. 
    */ 
    def search(n: Int, cdf: Array[Int]): Int = { 
    val i: Int = cdf.indexWhere(_ != 0) 
    if (i<0 | n<=cdf(i)) 
     i 
    else 
     search(n-cdf(i), {cdf.update(i,0); cdf}) 
    } 

    /** Returns the cumulative density function (CDF) of @list (in simple terms, 
    * the cumulative sums of the weights). 
    */ 
    def cdf(list: Array[Int]) = list.map{ 
    var s = 0; 
    d => {s += d; s} 
    } 
} 

И я определяю основной метод с этим фрагментом кода:

def rndWeighted(list: Array[Int]): Int = 
    search(Random.nextInt(list.sum + 1), cdf(list)) 

Однако, это все еще не достаточно быстро. Есть ли какая-то черная магия, которая делает ненужным перебирать список с самого начала (библиотеки, встроенные, эвристические)?

EDIT: это окончательный вариант кода (гораздо быстрее):

def search(n: Int, cdf: Array[Int]): Int = { 
    if (n > cdf.head) 
    1 + search(n-cdf.head, cdf.tail) 
    else 
    0 
} 

Answer 1

Вместо cdf.update(i,0) и передавая всю cdf назад cdf.indexWhere(_ != 0) в следующем рекурсивном вызове, рассмотрим

cdf.splitAt(i) 

и пропускает только элементы на справа из i, поэтому в следующей рекурсии , indexWhere сканирует меньший массив. Обратите внимание, что размер массива, монотонно уменьшающийся при каждом рекурсивном вызове, обеспечивает завершение.