12
\$\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\$
2
\$\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, out W>(val weight: W, val value: T)

fun <T, W> Iterable<T>.withWeight(weigher: (T) -> W): List<WeightedValue<T, W>> {
    return map { WeightedValue(weigher(it), it) }
}

println(
    elements.withWeight { it.length.toDouble() }
        .maxElementsWith(compareBy { it.weight })
        .first()
        .weight
)
// 5.0

Kotlin Playground Link

| improve this answer | |
\$\endgroup\$
5
\$\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.

| improve this answer | |
\$\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 '19 at 19:53
  • \$\begingroup\$ Subclass and change the implementation there. \$\endgroup\$ – Der Kommissar Oct 17 '19 at 19:53
  • \$\begingroup\$ What's wrong with the name? :) \$\endgroup\$ – Simon Forsberg Oct 20 '19 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\$ – Der Kommissar Oct 21 '19 at 18:55
5
\$\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.

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

What I see here is either:

  • Trying to sort list based on a value and getting item (or items) from top of the list. In that case you can use comparator and take stuff from top of that list. I don't see argument in being able to access actual "value". I see it as adding more responsibilities to the class.
  • Trying to filter out and cache some results. In that case I see this as sequence of objects (similar to for example Rx programming) and in that case a simple .filter {} lambda would be enough for me while providing me with more flexibility with how to filter, aggregate data and what to do with them after.

Overall I don't find this class useful unless for something very specific.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Sorting a list and then get one item from that list is a O(n log n) operation, while looping through the list once to get the highest value(s) is a O(n) operation and therefore much more effective. I don't see how this class is related to filtering out and caching results - to do that filtering I would have to loop through the list twice, once to find the maximum value and then once to do the filtering. This class only loops once. \$\endgroup\$ – Simon Forsberg Dec 9 '19 at 14:56
  • \$\begingroup\$ I am talking about semantic value and that's what I semantically see there. We can also talk about effectivity and yes sorting big list would be ineffective. To filter stuff above some threshold (that's what I understand you are doing) you need only one loop, which can work for both cases and speed up them significantly. If you want to focus about efficiency, please specify that ;) \$\endgroup\$ – K.H. Dec 9 '19 at 16:35
  • \$\begingroup\$ An example I gave in the question is the Alpha-Beta pruning algorithm, which while not necessarily creates a big list it takes a lot of time for each element to calculate the value, so I'd really like to avoid looping over the list any more than once. I am filtering stuff based on the biggest value found so far, not based on any pre-known fixed value, therefore a regular .filter wouldn't work unless you accept side-effects from the call to .filter, which IMO is bad practice. \$\endgroup\$ – Simon Forsberg Dec 9 '19 at 19:04
  • \$\begingroup\$ I understand what you mean. I wasn't talking literally only about filter (should have phrased better), but also about other lambdas. You could still implement that using filter and nested lambda without side effects, but that would be a bit clunky and weird way of using it. This sounds more like maxBy as was mentioned earlier already by mfulton26. \$\endgroup\$ – K.H. Dec 10 '19 at 3:32
  • \$\begingroup\$ Exactly, this is maxBy with the difference that I also want the possibility of returning a collection of all the max's and not just one. mfulton26's suggestion of using an extension function is what I will go with. Thank you for your feedback :) \$\endgroup\$ – Simon Forsberg Dec 10 '19 at 15:47

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.