Is there a way to get the "lowest n elements" from...

# random

[Ryan Rolnicki]

Is there a way to get the "lowest n elements" from a collection without sorting? It's not so hard to write myself as an extension, but hoping it already exists in some form

[Ryan Rolnicki]

If anyone is interested:

fun <T, R : Comparable<R>> Iterable<T>.minBy(n: Int, selector: (T) -> R): List<T> {
    val buffer = sortedSetOf<Pair<R, T>>(compareBy { it.first })
    for (el in this) {
        buffer += selector(el) to el
        if (buffer.size > n) {
            buffer.remove(buffer.last())
        }
    }

    return buffer.map { it.second }
}

[Dominaezzz]

Are you on Java only? If so, there's a slightly better way to do this.

[Ryan Rolnicki]

I am, but try to keep things in kotlin when possible

[Dominaezzz]

I was going to suggest using PriorityQueue but you can implement a minheap yourself.

[Ryan Rolnicki]

I think only slight improvements...better to use maxheap perhaps, but still marginal improvements. Would have to test to be sure I think

[Dominaezzz]

Ah for sure you'll want to measure, depends on the size of n.

[Ryan Rolnicki]

For my use case n is '3', so it's probably more academic 😛 Maybe if this were being added to the kotlin standard libs it could do with some more rigorous testing

[Klitos Kyriacou]

Instead of sortedSetOf<Pair<R, T>>(compareBy { it.first }) , why not just use sortedMapOf<R, T>() ?

[Ryan Rolnicki]

There's no guarantee either R or T is unique in the collection, which I think would cause that to have issues. Could use a multimap type, but I think the pair approach feels cleaner

[Klitos Kyriacou]

In that case, SortedSet<Pair<R, T>> won't work either, since it won't store entries with the same it.first value. It has exactly the same problem that a Map would have.

[Ryan Rolnicki]

Ah yeah I guess it does - perhaps will spend time optimizing later 🙂

[Youssef Shoaib [MOD]]

I think a sequence might work here, no?

[Dominaezzz]

How?

[Youssef Shoaib [MOD]]

Oh nevermind. I thought the stdlib implementation of Sequence.sortedBy was lazy but sadly it just converts the underlying iterator to a mutable list and sorts that
(stdlib):

public fun <T> Sequence<T>.sortedWith(comparator: Comparator<in T>): Sequence<T> {
    return object : Sequence<T> {
        override fun iterator(): Iterator<T> {
            val sortedList = [e-mail]()
            sortedList.sortWith(comparator)
            return sortedList.iterator()
        }
    }
}

[Dominaezzz]

Interesting, I guess min/max heap would be a nice way to implement lazy but expensive sorting.