CODEWITHSUNDEEP
sortingfunctional-programmingkotlinquicksort
Chintan Shah
Chintan Shah

Reputation: 955

Is it possible that functional quick-sort runs faster than imperative quick-sort?

I am trying to understand functional programming, and while the code looks beautiful, I was worried that there will be a performance hit as compared to an imperative implementation.

However, I am completely surprised to see that the functional implementation is much much faster than my imperative implementation (which looks ugly).

Now, I am sure that there is some mistake in my imperative implementation, yet, I am not sure what that mistake is..

Some benchmarks: functional on a size of 35 elements: 152954779 ns

Imperative on 35: 198337749325 ns

This worsens even if I add 10 elements to the list

Code is in kotlin:

Imperative:

fun quickSort(numbers: IntArray, l: Int, r: Int): IntArray {
if (l >= r)
    return numbers

fun swap(m: Int, n: Int) {
    val temp = numbers[m]
    numbers[m] = numbers[n]
    numbers[n] = temp
}

var i = l + 1
var j = l + 1
val pivot = numbers[l]
while (j < r) {
    if (numbers[j] < pivot) {
        if (numbers[i] > pivot) {
            swap(i, j)
        }
        i++
    }
    j++
}
swap(l, i - 1)
quickSort(numbers, 0, i - 1)
quickSort(numbers, i, r)
return numbers
}

I am sure I can refactor this and improve it, yet, that is not my goal right now.

Imperative 2:

fun partitionTest(arr: IntArray, left: Int, right: Int): Int {

var i = left
var j = right
var tmp: Int

val pivot = arr[(left + right) / 2]

while (i <= j) {
    while (arr[i] < pivot)
        i++
    while (arr[j] > pivot)
        j--
    if (i <= j) {
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
        i++
        j--
    }
}
return i
}


fun quickSortTest(arr: IntArray, left: Int, right: Int) {

val index = partitionTest(arr, left, right)

if (left < index - 1)

    quickSort(arr, left, index - 1)

if (index < right)

    quickSort(arr, index, right)

}

Functional:

fun functionalQuickSort(numbers: IntArray): IntArray {
return when {
    numbers.size <= 1 -> numbers
    else -> {
        val pivotIndex = 0
        functionalQuickSort(numbers.filter { it < numbers[pivotIndex] }.toIntArray()) + numbers[pivotIndex] + functionalQuickSort(
            numbers.filter { it > numbers[pivotIndex] }.toIntArray()
        )
    }
  }
}

Main:

val numbers = Random().ints(10).toArray()
var start = System.nanoTime()
functionalQuickSort(numbers).also { println(it.contentToString()) }
var end = System.nanoTime()
println("Took ${end - start}")


start = System.nanoTime()
quickSort(numbers,0,numbers.size).also { println(it.contentToString()) }
end = System.nanoTime()
println("Took ${end - start}")

Upvotes: 1

Views: 346

Answers (2)

Marko Topolnik
Marko Topolnik

Reputation: 200158

I used a known-good imperative QuickSort algorithm instead of yours which looks quite broken to me. My partitioning code is structurally different than yours because it uses C.A.R. Hoare's original scheme, while yours seems to be using the Lomuto scheme (popular for its simplicity, but not its efficiency).

I also wrote the code that takes care of most of the JVM microbenchmarking issues. Here it is:

import java.util.concurrent.ThreadLocalRandom
import kotlin.system.measureTimeMillis

const val PROBLEM_SIZE = 1_000_000L

fun quickSort(array: IntArray, lo: Int, hi: Int) {
    if (lo >= hi) {
        return
    }
    val p = partition(array, lo, hi)
    quickSort(array, lo, p)
    quickSort(array, p + 1, hi)
}

private fun partition(array: IntArray, lo: Int, hi: Int): Int {
    val pivot = array[(lo + hi) / 2]
    var i = lo - 1
    var j = hi + 1
    while (true) {
        do {
            i++
        } while (array[i] < pivot)
        do {
            j--
        } while (array[j] > pivot)
        if (i >= j) {
            return j
        }
        array[i] = array[j].also { array[j] = array[i] }
    }
}

fun functionalQuickSort(numbers: IntArray): IntArray {
    return when {
        numbers.size <= 1 -> numbers
        else -> {
            val pivotIndex = 0
            functionalQuickSort(numbers.filter { it < numbers[pivotIndex] }.toIntArray()) +
                    numbers[pivotIndex] +
                    functionalQuickSort(numbers.filter { it > numbers[pivotIndex] }.toIntArray()
                    )
        }
    }
}

fun main(args: Array<String>) {
    benchmark("imperative", ::runImperativeQuickSort)
    benchmark("functional", ::functionalQuickSort)
}

fun benchmark(name: String, block : (IntArray) -> IntArray) {
    println("Warming up $name")
    (1..4).forEach {
        validate(block(randomInts()))
    }
    println("Measuring")
    val average = (1..10).map {
        var result: IntArray? = null
        val input = randomInts()
        val took = measureTimeMillis {
            result = block(input)
        }
        validate(result!!)
        took
    }.average()
    println("An average $name run took $average ms")
}

private fun runImperativeQuickSort(array: IntArray): IntArray {
    quickSort(array, 0, array.size - 1)
    return array
}

private fun randomInts() = ThreadLocalRandom.current().ints(PROBLEM_SIZE).toArray()

private fun validate(array: IntArray) {
    var prev = array[0]
    (1 until array.size).forEach {
        array[it].also { curr ->
            require(curr >= prev)
            prev = curr
        }
    }
}

Typical output:

Warming up imperative
Measuring
An average imperative run took 106.6 ms
Warming up functional
Measuring
An average functional run took 537.4 ms

So... no, the functional version isn't faster.

Upvotes: 4

Thomas
Thomas

Reputation: 181745

It took me a while to find it, but there's a bug in your recursive call:

  quickSort(numbers, 0, i - 1)

This should be:

  quickSort(numbers, l, i - 1)
                     ^

As a small optimization, you can also return early on segments of length 1 (in addition to length 0):

  if (l + 1 >= r)
    return numbers

There seem to be a few more issues that I haven't looked into in detail. The nested if in your while loop looks dodgy to me; I think the inner if could be removed:

  while (j < r) {
    if (numbers[j] < pivot) {
      swap(i, j)
      i++
    }
    j++
  }

Think carefully about what your invariants are and whether each statement maintains them.

With these adjustments, the imperative version runs about 10 times faster on 100000 elements.

Also consider what happens if two elements are equal, which is unlikely with such a small array but will happen for arrays of 100000 elements (birthday paradox). You will find that your functional implementation is broken in this case.

On the subject of benchmarking:

  • Make sure that your input is big enough to get data instead of noise. A running time of more than a second is good.
  • Don't include the generation of input data.
  • Definitely don't include the printing of output. I/O is relatively slow.

Upvotes: 2

Related Questions