从 Kotlin 中的不相交范围的并集生成随机数的最有效方法是什么？

Question

我想从 Kotlin 中的范围并集生成随机数。我知道我可以做类似

的事情

((1..10) + (50..100)).random()

但不幸的是，这会创建一个中间列表，当范围很大时，它可能会相当昂贵。

我知道我可以编写一个自定义函数来随机 select 一个具有基于宽度的权重的范围，然后从该范围中随机选择一个元素，但是 我想知道是否使用 Kotlin 内置插件 .

有一种更简洁的方法可以实现此目的

Answer 1

简短的解决方案

我们可以这样做：

fun main() {
    println(random(1..10, 50..100))
}

fun random(vararg ranges: IntRange): Int {
    var index = Random.nextInt(ranges.sumOf { it.last - it.first } + ranges.size)
    ranges.forEach {
        val size = it.last - it.first + 1
        if (index < size) {
            return it.first + index
        }
        index -= size
    }

    throw IllegalStateException()
}

它使用与您描述的相同的方法，但它只调用一次随机整数，而不是两次。

长解

正如我在评论中所说，我经常想念 Java/Kotlin stdlib 中用于创建集合视图的实用程序。如果 IntRange 有类似 asList() 的东西，并且我们有办法通过创建视图来连接列表，那么利用现有的逻辑块，这将非常简单。视图会为我们解决问题，它们会自动计算大小并将随机数转换为正确的值。

我实现了一个 POC，也许你会发现它有用：

fun main() {
    val list = listOf(1..10, 50..100).mergeAsView()
    println(list.size) // 61
    println(list[20]) // 60
    println(list.random())
}

@JvmName("mergeIntRangesAsView")
fun Iterable<IntRange>.mergeAsView(): List<Int> = map { it.asList() }.mergeAsView()

@JvmName("mergeListsAsView")
fun <T> Iterable<List<T>>.mergeAsView(): List<T> = object : AbstractList<T>() {
    override val size = this@mergeAsView.sumOf { it.size }

    override fun get(index: Int): T {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException(index)
        }

        var remaining = index
        this@mergeAsView.forEach { curr ->
            if (remaining < curr.size) {
                return curr[remaining]
            }
            remaining -= curr.size
        }

        throw IllegalStateException()
    }
}

fun IntRange.asList(): List<Int> = object : AbstractList<Int>() {
    override val size = endInclusive - start + 1

    override fun get(index: Int): Int {
        if (index < 0 || index >= size) {
            throw IndexOutOfBoundsException(index)
        }
        return start + index
    }
}

此代码与上面的简短解决方案几乎完全相同。它只是间接地这样做。

再次声明：这只是一个 POC。 asList() 和 mergeAsView() 的这种实现根本不是生产就绪的。我们应该实现更多的方法，例如 iterator()、contains() 和 indexOf()，因为现在它们比应该的要慢得多。但它应该已经针对您的具体情况有效地工作了。你应该至少测试一下。此外，mergeAsView() 假设提供的列表是不可变的（它们具有固定大小），这可能不是真的。

为 IntProgression 和其他原始类型实现 asList() 可能会很好。此外，与扩展函数相比，您可能更喜欢 mergeAsView() 的可变参数版本。

最后一点：我猜有些库已经这样做了——可能有些与不可变集合有关。但如果您正在寻找一个相对轻量级的解决方案，它应该适合您。

Answer 2

假设您的范围是非重叠和排序的，如果不是，您可以进行一些预处理以合并和排序。

算法选择：

O(1)时间复杂度和O(N)space复杂度，其中N为总数，通过将range对象扩展为一组数字，随机取一个。为了紧凑，可以使用数组或列表作为容器。
O(M)时间复杂度和O(1)space复杂度，其中M是范围数，通过线性缩减计算位置。
O(M+log(M))时间复杂度和O(M)space复杂度，其中M是范围数，通过使用二分查找计算位置。如果在同一组范围内有多个世代，则可以将准备 (O(M)) 和世代 (O(log(M))) 分开。

对于最后一个算法，假设有一个所有可用数字的排序列表，然后可以将此列表划分为您的范围。所以没有必要真正创建这个列表，你只需要计算你的 range 相对于这个列表的位置。当你在这个列表中有一个位置，并且想知道它在哪个范围内时，进行二分查找。

fun random(ranges: Array<IntRange>): Int {
    // preparation
    val positions = ranges.map {
        it.last - it.first + 1
    }.runningFold(0) { sum, item -> sum + item }

    // generation
    val randomPos = Random.nextInt(positions[ranges.size])
    val found = positions.binarySearch(randomPos)
    // binarySearch may return an "insertion point" in negative
    val range = if (found < 0)  -(found + 1) - 1 else found
    return ranges[range].first + randomPos - positions[range]
}

从 Kotlin 中的不相交范围的并集生成随机数的最有效方法是什么？

What is the most efficient way to generate random numbers from a union of disjoint ranges in Kotlin?

random

range

kotlin