Implementing a Zero-Cost Random Picker in Kotlin Sequences

Libraries
1
2

I don’t have a paid account, so I can only read until “How It Works”, but:

  1. I partially agree it may confuse people if some operators on sequences require to consume the whole source sequence. On the other hand, developers should expect reordering operations do this. I don’t have a strong opinion if we should or shouldn’t require people to do: seq.sorted().asSequence() if they need to remain working with sequences.
  2. I don’t see how randomPickOrNull() is a solution to the above problem. It provides a different functionality.
  3. Your code requires to consume the sequence twice which is not always supported. This is also untypical for sequence operators - most (all?) of them consume the source sequence only once, so users of your function might be surprised it’s different.
  4. Because Random.nextInt(0, Int.MAX_VALUE) is almost always bigger than the size of the sequence, I’m not sure if that optimization with looking for the item in the first pass makes too much sense. Your code could be pretty much replaced with simply: seq.drop(Random.nextInt(seq.count())).first().
  5. You could experiment with doing this in a single pass by first taking the first item, then switching to next one with 50% chance, then switching to the third with 33%, then to next one with 25% and so on. I’m not entirely sure this is a correct approach, you would have to test it. Also, that requires generating quite a lot of random numbers: one per each item in the sequence.
1 Like
3

One pass solution using the above approach:

fun main() {
    val seq = (0 until 100).asSequence()

    generateSequence { seq.randomOrNull() }
        .take(1_000_000)
        .groupingBy { it }
        .eachCount()
        .entries
        .sortedBy { it.key }
        .also { println(it) }
}

fun <T> Sequence<T>.randomOrNull(): T? =
    withIndex()
        .fold(null as T?) { acc, (idx, it) ->
            if (Random.nextFloat() * (idx + 1) < 1) it else acc
        }

Histogram looks good, so I think it is a correct solution: Kotlin Playground: Edit, Run, Share Kotlin Code Online