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

Question

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

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

但不幸的是，这会创建一个中间列表，当范围很大时，这可能会相当昂贵。
我知道我可以编写一个自定义函数来根据宽度随机选择一个具有权重的范围，然后从该范围中随机选择一个元素，但我想知道是否有更简洁的方法可以使用 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 中用于创建集合 View 的 utils。如 IntRange会有类似 asList() 的内容我们将有一种通过创建 View 来连接列表的方法，这将非常简单，利用现有的逻辑块。 View 会帮我们解决问题，它们会自动计算大小并将随机数转换为正确的值。
我实现了一个 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()假设提供的列表是不可变的(它们具有固定的大小)，这可能不是真的。
实现 asList() 可能会很好为 IntProgression以及其他原始类型。你也可能更喜欢 mergeAsView() 的可变参数版本比扩展功能。
最后一点:我想已经有一些库可以做到这一点 - 可能有些与不可变集合有关。但是如果你寻找一个相对轻量级的解决方案，它应该适合你。