10
\$\begingroup\$

Have you ever wanted to get just not one "best" element from a list, but all of them, or a random element of the best ones? That's what the Best class is here for. Opinion-based? Definitely not!

Features:

  • Should work with any kind of element.
  • Should always keep track of the best elements seen so far.
  • Should be able to get a list of all best elements
  • Should be able to get a single best element

I thought about supporting both Comparator<T> and (T) -> Double, but realized that I have a use-case for actually finding out the actual value as well (for an implementation of Alpha-Beta pruning in Minmax algorithm). I thought that (T) -> Double option is more flexible in the long run (feel free to convince me about otherwise).

Code

The code is written for multi-platform Kotlin projects. It should be able to compile to both JVM, JavaScript, and Kotlin Native.

class Best<T>(private val valueFunction: (T) -> Double) {

    private var bestValue: Double = Double.NEGATIVE_INFINITY
    private var bestElements: MutableList<T> = mutableListOf()

    fun next(element: T) {
        val value = valueFunction(element)
        if (value > bestValue) {
            bestValue = value
            bestElements = mutableListOf(element)
        } else if (value >= bestValue) {
            bestElements.add(element)
        }
    }

    fun randomBest(): T = bestElements.random()
    fun getBest(): List<T> = bestElements.toList()
    fun firstBest(): T = bestElements.first()
    fun isBest(element: T): Boolean = bestElements.contains(element)
    fun getBestValue(): Double = bestValue

}

Tests

class BestTest {

    private fun createBest(): Best<String> {
        val best = Best<String> { it.length.toDouble() }
        best.next("hi")
        best.next("hello")
        best.next("")
        best.next("world")
        return best
    }

    @Test
    fun empty() {
        val emptyBest = Best<Double> { it }
        assert(emptyBest.getBest().isEmpty())
        assertThrows<NoSuchElementException> { emptyBest.randomBest() }
        assertThrows<NoSuchElementException> { emptyBest.firstBest() }
        assertFalse(emptyBest.isBest(4.2))
    }

    @Test
    fun random() {
        val randomBest = createBest().randomBest()
        assertTrue(randomBest == "hello" || randomBest == "world")
    }

    @Test
    fun bestList() {
        val allBest = createBest().getBest()
        assertEquals(listOf("hello", "world"), allBest)
    }

    @Test
    fun firstBest() {
        assertEquals("hello", createBest().firstBest())
    }

    @Test
    fun isBest() {
        val best = createBest()
        assertFalse(best.isBest(""))
        assertFalse(best.isBest("hi"))
        assertFalse(best.isBest("something random that was never added"))
        assertTrue(best.isBest("hello"))
        assertTrue(best.isBest("world"))
    }

}

Questions

  • Does this class seem useful? (Is it as useful as the name sounds?)
  • Would this class benefit from implementing Kotlin's Collection interface?
  • Any improvement suggestions that you can think of
\$\endgroup\$
4
\$\begingroup\$

I hate the name, but don't have a better one so I'll leave that for another answer.

Here's what I do have though: why not make it more generic?

I'm looking at this function:

fun next(element: T) {
    val value = valueFunction(element)
    if (value > bestValue) {
        bestValue = value
        bestElements = mutableListOf(element)
    } else if (value >= bestValue) {
        bestElements.add(element)
    }
}

Why not make a isBetterThanFunction: (T, T) -> Boolean and isEqualToFunction: (T, T) -> Boolean. Then, you can support a wider array of items, and you don't need valueFunction.

class Best<T>(private val isBetterThanFunction: (T, T) -> Boolean, private val isEqualToFunction: (T, T) -> Boolean) {

    private var bestValue: ...
    private var bestElements: MutableList<T> = mutableListOf()

    fun next(element: T) {
        if (isBetterThanFunction(element, bestValue)) {
            bestValue = element
            bestElements = mutableListOf(element)
        } else if (isEqualToFunction(element, bestValue)) {
            bestElements.add(element)
        }
    }

    fun randomBest(): T = bestElements.random()
    fun getBest(): List<T> = bestElements.toList()
    fun firstBest(): T = bestElements.first()
    fun isBest(element: T): Boolean = bestElements.contains(element)
    fun getBestValue(): Double = bestValue

}

To me, it makes things more clear. I'm no longer inferring what you mean with (T) -> Double. How is that weighted? Well, now I make that decision.

Why does this matter? What if I defined best as "shortest"? With your version, I have to get clever about it and probably negate the value or something. With this version, I pick how that works.

\$\endgroup\$
  • \$\begingroup\$ I imagine there would be quite a bit of duplicated code in a lot of cases between the isBetterThan and isEqualTo. Also, as I wrote in the question, I have a use-case for getting the actual value as well. But you are right that I had to negate the value in my minimax implementation, which is indeed a problem I would like to avoid. \$\endgroup\$ – Simon Forsberg Oct 17 at 19:53
  • \$\begingroup\$ Subclass and change the implementation there. \$\endgroup\$ – 410_Gone Oct 17 at 19:53
  • \$\begingroup\$ What's wrong with the name? :) \$\endgroup\$ – Simon Forsberg Oct 20 at 18:54
  • \$\begingroup\$ @SimonForsberg I just don't like it, but I don't have an alternative so take that with a grain of salt lol \$\endgroup\$ – 410_Gone Oct 21 at 18:55
4
\$\begingroup\$

The question whether to use (T) -> Double or Comparator<T> probably depends on your use case. If you have a scenario where you explicitly know, that your objects can always be mapped to a double, then it's fine to use (T) -> Double.

On the other hand, once you have such a weighting function, then it's trivial to create a Comparator based on that. And (my gut says - I haven't researched it) the reverse (creating a weighting function out of a Comparator) may not be possible. That means a version using a Comparator would be more flexible.

Does this class seem useful? (Is it as useful as the name sounds?)

I'm sure there is a scenario where this could be used, but I don't like the name either. Maybe something like BestWeightHolder?

Would this class benefit from implementing Kotlin's Collection interface?

IMO, no, not directly. That actually touches one of my criticisms I have: You have several "utility" methods (randomBest, firstBest and possibly contains) which don't seem to fit into the purpose of the class IMO, especially since they can just as well be executed on the list returned by toList.

I think you should drop those methods and replace toList with an asCollection method, which returns not a copy of the list of best items, but a direct reference of your internal list limited to the Collection interface (or if you want to make sure it is not cast back to a MutableList and modified, an instance of a thin wrapper class that implements Collection). The user then can use first(), random(), contains()and more on that.

Any improvement suggestions that you can think of

I'm not a big fan of the method name next. Methods of that name usually indicate a supplying method (as in an Iterator, for example). I'd suggest add or (following Java's Integer/Long/DoubleSummaryStatistics classes which have a similar function and which implement Consumer<T>) accept.

One tiny thing:

} else if (value >= bestValue) {

should use == instead of >=.

And finally, personally, following Kotlin's pattern, I would consider implementing this as an immutable class.

\$\endgroup\$
  • \$\begingroup\$ What's wrong with the name? :) \$\endgroup\$ – Simon Forsberg Oct 20 at 18:54
  • 1
    \$\begingroup\$ @SimonForsberg It's not the best :) \$\endgroup\$ – RoToRa Oct 21 at 6:52
0
\$\begingroup\$

One of the things I really like about Kotlin is how the source code for existing functions in the stdlib are readily available and can be leveraged to quickly create very efficient functions that are similar to existing ones.

In your particular case I suggest taking a look at max, maxBy, and maxWith. We can create our own extension functions that instead of returning a single "max" element returns a List of them. e.g. maxElements, maxElementsBy, and maxElementsWith.

For this example we only need a maxElementsWith function which takes a Comparator (based on maxWith source code):

fun <T> Iterable<T>.maxElementsWith(comparator: Comparator<in T>): List<T> {
    val iterator = iterator()
    if (!iterator.hasNext()) return emptyList()
    var max = iterator.next()
    var maxElements = mutableListOf(max)
    while (iterator.hasNext()) {
        val e = iterator.next()
        when (comparator.compare(e, max).sign) {
            1 -> {
                max = e
                maxElements = mutableListOf(max)
            }
            0 -> maxElements.add(e)
        }
    }
    return maxElements
}

You can then use maxElementsWith to find a single "best" (max) value, a list of them, a random one, etc.

If you need the weight of the best/max values then you could first map your list of items to a list of pairs of the weight to the item. Pairs often get a bit tricky to read so you might even create a WeightedValue data class to improve readability:

Examples:

val elements = listOf("hi", "hello", "", "world")

val bestElements = elements.maxElementsWith(compareBy(String::length))
println(bestElements)
// [hello, world]

println(bestElements.random())
// ${either hello or world}

val newBestElements = bestElements.plus("supercalifragilisticexpialidocious")
    .maxElementsWith(compareBy(String::length))
println(newBestElements)
// [supercalifragilisticexpialidocious]

println(
    elements.map { it.length to it }
        .maxElementsWith(compareBy { it.first })
        .first()
        .first
)
// 5

data class WeightedValue<out T>(val weight: Double, val value: T)
println(
    elements.map { WeightedValue(it.length.toDouble(), it) }
        .maxElementsWith(compareBy { it.weight })
        .first()
        .weight
)
// 5.0
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.