Hey guys, Does anyone know a mechanism to sort a p...
# getting-started
a
Hey guys, Does anyone know a mechanism to sort a possibly infinite
Sequence
or one with a really a large count of objects lazily without it being too time consuming like the factory methods?
r
If you can find a way to sort an infinite number of things in finite time, you get all the money.
😂 1
a
True, I guess I worded it wrong. Let say it’s not infinite. It’s just a sequence with a thousand objects. Is there a way to yield objects in a sorted order without waiting for all of the objects to arrive beforehand?
e
unless you know something about the order they arrive in, you must receive every object to determine the minimum, which is the first element in the sorted result, so no.
âž• 1
with additional knowledge - for example, if there is a guarantee that objects won't come out of order by more than some displacement of
n
- then you have some options
a
The use case is as follows. There are five sequences, each of them in ascending order; they are then flattened into a single sequence, which is expected to be in a sorted order.
Copy code
// list.size == 5

list.map {
    `yield objects in ascending order`()
}.asSequence().flatten()
Is there a solution for this?
e
if they weren't flattened then there would be a solution
a
Could you elaborate?
e
well-known CS algorithm,
Copy code
fun <T : Comparable<T>> Iterable<Sequence<T>>.mergeSorted(): Sequence<T> = mergeSorted(comparator = naturalOrder())
fun <T> Iterable<Sequence<T>>.mergeSorted(comparator: Comparator<T>): Sequence<T> = sequence {
    val queue = PriorityQueue<Pair<Iterator<T>, T>>(compareBy(comparator) { it.second })
    mapNotNullTo(queue) { it.iterator().takeIf { it.hasNext() }?.let { it to it.next() } }
    while (queue.isNotEmpty()) {
        val (iterator, value) = queue.remove()
        yield(value)
        if (iterator.hasNext()) queue.add(iterator to iterator.next())
    }
}

fun main() {
    listOf(
        generateSequence(1) { 2 * it },
        generateSequence(1) { 3 * it },
        generateSequence(1) { 5 * it },
    ).mergeSorted().take(20).forEach { println(it) }
}
a
I see it! Thank you very much, @ephemient!