algorithm - 概率数据结构

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，则实际元素概率必须通过将其原始概率除以所有元素概率之和来计算。例如，由 “A”到 0.1F 和 “B”到 0.3F 组成的 ProbabilitySet 返回 “A” 在 25% 的案例中，“B” 在 75% 的案例中。

这是我实现的可变 ProbabilitySet，add 在 O(1) 中运行，在 next 中运行O(logN):

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