Kotlin - Find minimum value in an IntArray within range of indices

user_13931668 0
Viewed 680

I am refactoring some older Java code over to Kotlin. There is a function that returns the index of the minimum value held by an element in a Kotlin IntArray within the range [a, b]. The range values default to 0 and the size of the array - 1.

I would like to do something along the lines of...

return data.minOf().indexOf()

...but while only iterating between the a and b indices of data.

Here is the function:

// data is the IntArray property that I'm looping through. 
fun absMinIndex(a: Int = 0, b: Int = (data.size - 1)) : Int {
    var minVal = data[a]
    var minIndex = 0

    for (i in (a + 1)..b) {
        val e = data[i]
        if (e < minVal) {
            minVal = e
            minIndex = i
        }
    }
    return maxIndex
}

This [for loop] solves the issue nicely by never visiting indices out of range, and by not generating a copied array/sub-array. I'm wondering if it could be done 'prettier'.

Question

Is there a more idiomatic Kotlin approach to iterating through an array within a range that would not negatively impact the performance of my current solution?

Edited some code for clarity.

kotlin idioms iterator loops
2 Answers

I believe this approach would be more idiomatic:

  1. Use IntRange as an input parameter
  2. Define extension method for IntArray providing custom iterator to traverse the list in the desired range wrapping values into IndexedValue:
fun IntArray.withIndexInRange(range: IntRange = 0..lastIndex) = Iterable {
    require(range.first >= 0 && range.last <= lastIndex)
    object : Iterator<IndexedValue<Int>> {
        private var index = range.first
        override fun hasNext() = index <= range.last
        override fun next() = IndexedValue(index, this@withIndexInRange[index++])
    }
}
  1. Use minByOrNull method from stdlib to find minimal value or wrap it into another extension method for convenience:
fun <T : Comparable<T>> Iterable<IndexedValue<T>>.indexOfMinOrNull() = minByOrNull { it.value }?.index

Usage:

data.withIndexInRange(a..b).indexOfMinOrNull()

Note, that this will have some performance penalties (creation and GC of N extra objects), but as Donald Knuth says:

Premature optimization is the root of all evil

So, I believe better readability worth it.

user_139686730

As Tenfour04 suggested, not much you can do without loosing performance. But as per your idea with changing the way you call it, you can make it an extension function.

fun IntArray.findIndexOfMinInRange(a: Int = 0, b: Int = this.size - 1): Int {
    var maxVal = get(a)
    var maxIndex = 0

    for (i in (a + 1)..b) {
        if (get(i) < maxVal) {
            maxVal = get(i)
            maxIndex = i
        }
    }
    return maxIndex
}

//and call it like this: 

data.findIndexOfMinInRange(0, 15) //or without anything in the parentheses for the default values

One thing that I would change is the variable names inside the function, we are searching for the minimum value, not max, and also for the index of the minimum, not the maximum index. Also maybe (big maybe) creating a val of data[it] instead of accessing it twice might be better (honestly not sure, we would be trading a .get for a few bytes of memory).

So all in all, I'd probably leave it at this:

fun IntArray.findIndexOfMinInRange(fromIndex: Int = 0, toIndex: Int = this.size - 1): Int {
    var min = get(fromIndex)
    var indexOfMin = fromIndex

    for(i in (fromIndex + 1)..toIndex){
        val current = get(i)
        if (current < min) {
            min = current
            indexOfMin = i
        }
    }

    return indexOfMin
}

//would be called in the same way the one above

Also, a note of caution, if you create an IntArray of a certain size, and do not populate it in full, the default values it will hold for the non populated ones is 0. If you do:

val data = IntArray(6)
data[0] = 10
data[1] = 11
data[2] = 100
data[3] = 9
data[4] = 50

Then the actual array is [10, 11, 100, 9, 50, 0].

user_99408200
Related