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

Question

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

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

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

我知道我可以编写一个自定义函数来随机选择一个范围，其权重基于其宽度，然后从该范围中随机选择一个元素，但我想知道是否有更干净的方法来使用 Kotlin 内置函数来实现此目的。

Answer 1

假设您的范围不重叠且已排序，如果没有，您可以进行一些预处理来合并和排序。

这涉及到一个算法选择：

• O(1) 时间复杂度和 O(N) 空间复杂度，其中 N 是总数，通过将范围对象扩展为一组数字，并随机选取一个。为了紧凑，可以使用数组或列表作为容器。
• 通过计算线性归约中的位置，时间复杂度为 O(M)，空间复杂度为 O(1)，其中 M 是范围数。
• 通过使用二分搜索计算位置，时间复杂度为 O(M+log(M))，空间复杂度为 O(M)，其中 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]
}