Quickselect playground

The QuickSelect algorithm alloys to find the k-th smallest element of an unordered list, yielding performances on-average better than if we had to previously order the list. This algorithm is particularly usefull when computing the median of an unordered list. For more explanations see the Wikipedia article Quickselect.

This repository contains several implementations of the Quickselect algorithm:

• Python
• Cython
• Scala
• Java
• C

Comparing the mean execution time

The implementations of the algorithm are compared by computing the median of lists of different sizes. For each list size we build the array [1, ..., list_size] and time the execution of 250 Quickselect computations, the array is shuffle between each computation, the mean of those computations represent the mean execution time for that algorithm.

The C-implementation seems to be doing worse than the Scala and Java implementations (which are non suprinsingly yielding similar performances), I believe this is because the method used to measure execution times in C is not adequat.

Executing the benchmark

Schematically each implementation consist in a file "Quickselect" (with the implementation of the algorithm) and a file "Benchmark" that uses "Quickselect" as a library to conduct the benchmark.

For each implementation executing the "Benchmark" will output a file "benchmark_results.txt" in the implementation's directory. Those results are then aggregated by the "benchmark.py" script at the root of the repositiory in order to produce the graph.

Caution: The methods detailed below might not be the best way of compiling/executing thoses type of scripts, those are just indications of how those files were tested during their writing

Python

The code is written in Python 3.5 (3.5.2)

quickselect-playground/python$ python benchmark.py

Cython

For Cython we first need to build the Cython file of the QuickSelect library (to know more about Cython Go here)

quickselect-playground/cython$ python setup.py build_ext --inplace

Then we can just call the benchmark python file (which is identical to the python implemention)

quickselect-playground/cython$ python benchmark.py

Scala

The code is written in Scala 2.11 (2.11.8) and SBT 0.13 (0.13.8).

We need first to compile the source code

quickselect-playground/scala$ sbt compile

Then to execute the benchmark,

quickselect-playground/scala$ sbt run

Java

The code is written in Java 1.8 (1.8.0_101).

We need first to compile the source code. Caution: this is executed from java/src folder

quickselect-playground/java/src$ javac io/github/maximerihouey/Quickselect.java io/github/maximerihouey/Benchmark.java

Then to execute the benchmark,

quickselect-playground/java/src$ java io.github.maximerihouey.Benchmark

C

The code is compiled using Gcc 4.9.3.

We first compile the quickselect as a library, the benchmark script and then linking everything together in an executable file

quickselect-playground/C$ gcc -c quickselect.c -o quickselect.o
quickselect-playground/C$ gcc -c benchmark.c -o benchmark.o
quickselect-playground/C$ gcc benchmark.o quickselect.o -o benchmark

To execute the "benchmark" file one can just do

quickselect-playground/C$ ./benchmark

R

The code is written in R 3.3 (3.3.1)

quickselect-playground/R$ Rscript benchmark.R