• + 5 comments

    Yes, and don't be fooled by thinking that an algorithm that iterates only once over the items is necessarily faster than one that iterates over them multiple times.

    The number of operations per iteration plays an important role, so an algorithm that iterates once, but with many operations, can be slower than an algorithm that iterates multiple times with very few operations per iteration, because the latter algorithm may perform fewer total operations.

    As a case in point, here is a close Kotlin equivalent of the Python code at the top of this thread:

    fun miniMaxSum(arr: Array<Long>): Unit =
        arr.sum().let {
            println("${it - arr.max()!!} ${it - arr.min()!!}")
        }
    

    The code above iterates over the array 3 times: once each for sum, max, and min.

    Here's another solution that iterates over the array only once, collecting the running sum, min, and max simultaneously along the way. Yes, you might argue it's a bit contrived, but it's not a totally unreasonable solution, as it proves my point.

    fun miniMaxSum(arr: Array<Long>): Unit =
        arr.fold(listOf(0, Long.MAX_VALUE, Long.MIN_VALUE)) { (sum, min, max), e ->
            listOf(sum + e, Math.min(min, e), Math.max(max, e))
        }.let { (sum, min, max) ->
            println("${sum - max} ${sum - min}")
        }
    

    The overhead of this approach (1 iteration) causes it to take nearly 10 times longer than the preceding solution (3 iterations). Of course, the timings I took were very rough, and if the array were longer, the overhead of the latter solution might be less significant, but in any case, the latter solution (1 iteration) is clearly and significantly less performant than the former solution (3 iterations).

    Here is another solution that iterates over the array only once, but is indeed faster than the first solution (3 iterations) above, by approximately 50% for 5 items (YMMV):

    fun miniMaxSumLoop(arr: Array<Long>) {
        var sum = 0L
        var min = Long.MAX_VALUE
        var max = Long.MIN_VALUE
    
        for (e in arr) {
            sum += e
            if (e < min) min = e
            if (e > max) max = e
        }
    
        println("${sum - max} ${sum - min}")
    }
    

    The code is longer than the first solution, and is arguably less readable. It certainly (arguably?) imposes a bit more cognitive load to comprehend than the first solution does. In this case, it could be argued that the first solution is more desirable. In other words, at some point, the difference in performance might not be large enough to give up the arguably clearer solution. Ease of understanding might simply trump performance.

    There's one more thing to consider here as well. Because of the simplicity (and clarity) of the first solution, the likelihood of bugs is greatly reduced due to the use of built-in functionality that precludes the need for explicit looping, as given in the third solution. When you use explicit looping, you introduce the chance for one-off bugs, and the like.