Структура вероятностных данных

Question

Идея состоит в том, чтобы иметь структуру данных, к которой вы можете обращаться к ее элементам только случайным образом, но на основе вероятностного коэффициента, определенного пользователем для каждого элемента. Таким образом, если вероятность структуры, которая содержит 100 элементов для получения x, равна 0,5, то теоретически, если мы попытаемся извлечь случайный элемент сто раз, то x будет возвращено примерно в ~ 50 раз.

Я не смог найти готовое решение, которое бы это делало, так что я взял это на себя:

import kotlin.math.absoluteValue

/**
 *@author mhashim6 on 13/10/2019
 */
class ProbabilitySet<T>(private val items: Array<out Pair<T, Float>>) {
    private var probabilityIndices: List<Int>

    private fun calcFutureSize(count: Int, probability: Float) =
            ((count / (1f - probability)) - count).toInt().absoluteValue

    init {
        probabilityIndices = items.withIndex().flatMap { (i, item) ->
             item.act { (_, probability) ->
                calcFutureSize(items.size, probability).minus(items.size).act { delta ->
                    Iterable { ConstIterator(delta, i) }
                }
            }
        }
    }

    fun next(): T = items.random().first
}

class ConstIterator(private var size: Int, private val const: Int) : IntIterator() {

    override fun nextInt(): Int {
        size--
        return const
    }

    override fun hasNext(): Boolean = size > 0

}

fun <E> probabilitySetOf(vararg items: Pair<E, Float>) = ProbabilitySet(items)

inline fun <T, R> T.act(action: (T) -> R) = action(this)

Я пытался сделать его изменчивым, но я столкнулся с множеством сложностей, касающихся времени и памяти,Так что пока он неизменен.

Это жизнеспособная реализация? Есть ли реализация для этой проблемы уже? Как сделать его изменчивым?

Answer 1

Я предполагаю, что если сумма вероятностей элементов не равна 1 , фактическая вероятность элемента должна быть рассчитана путем деления его первоначальной вероятности на сумму вероятностей всех элементов. Например, ProbabilitySet, состоящий из "A" to 0.1F и "B" to 0.3F, возвращает "A" в 25% дел и "B" в 75% дел.

Вот моя реализация изменяемого ProbabilitySet с add, работающего в O (1) и next, работающего в O (logN) * ​​1020 *:

class ProbabilitySet<E>(
    private val random: Random = Random.Default
) {
    private val nodes = mutableListOf<Node>()
    private var sum = 0F

    fun add(element: E, probability: Float) {
        require(probability >= 0) { "[$element]'s probability ($probability) is less than 0" }
        val oldSum = sum
        sum += probability
        nodes += Node(oldSum..sum, element)
    }

    fun isEmpty() = sum == 0F

    fun next(): E {
        if (isEmpty()) throw NoSuchElementException("ProbabilitySet is empty")
        val index = random.nextFloat() * sum
        return nodes[nodes.binarySearch {
            when {
                it.range.start > index -> 1
                it.range.endInclusive < index -> -1
                else -> 0
            }
        }].element
    }

    private inner class Node(
        val range: ClosedRange<Float>,
        val element: E
    )
}

Заводской метод:

fun <E> probabilitySetOf(vararg items: Pair<E, Float>, random: Random = Random.Default) =
    ProbabilitySet<E>(random).apply {
        items.forEach { (element, probability) -> add(element, probability) }
    }

Вариант использования:

val set = probabilitySetOf("A" to 0.4F, "B" to 0.3F)
println(set.next())
set.add("C", 0.9F)
println(set.next())