Python has another set of function in several popular packages, which is related to Selection and Partitioning – Quantile. These function take an an array as input, along with one or more floating-point arguments, each in the range of 0.0 to 1.0. For instance, providing a value of 0.75 returns the array value which is the smallest of the top 25% of the array.

Python quantile function can also accept an array of floating-point values. For example, 0.25, 0.5, 0.75. In this case, it returns array values for the 25%, 50% and 75% of all array values. This is done without sorting the array, by using a comparison-based Selection algorithm.

Quantile functionality can also be implemented using Radix methodology instead of using comparisons.

Radix Quantile

Quantile function, single floating-point value or an array of floats, is simply a different interface to the Selection algorithm. Instead of specifying an array index, which is an integer, a floating-point value is given. The value of 0.0 means finding the minimum value within the array. The value of 1.0 means finding the maximum value. The minimum is at index of zero if the array was sorted in ascending order. The maximum is at index of (length_of_array – 1) if the array was sorted.

Thus, the floating-point value can be translated to an index by scaling it by (length_of_array – 1). Then the Selection algorithm could be used to achieve Quantile. Radix Selection algorithm would achieve Radix Quantile.

When an array of floating-point values are used, each of them can be scaled in the same manner, achieving multi-value Radix Quantile.

Radix Quantile with Partition

Comparison-based algorithms use partitioning to achieve Selection. This means, partitioning is achieved as a byproduct of doing Selection.

Radix Selection, on the other hand, does not require to use partitioning to achieve Selection. Doing partitioning is extra unnecessary work for Radix Selection. If we want to achieve Selection (or Quantile) with Partition, then extra work needs to be performed by the Radix Selection algorithm – this variant is Radix Quantile with Partition.

Radix Quantile with Partition uses an MSD Radix Sort variant. During first digit processing, the entire array is sorted based on the most significant digit, as is normally done by the MSD Radix Sort algorithm. However, for the next and subsequent digits, only the bins where the Quantile floating-point values (scaled to integer indexes) land are processed further. These bins are sorted fully by the next digit. Less work than sorting is achieved by only processing these particular bins, instead of processing all of the bins.

Performance

Radix Quantile has been implemented in the HPCsharp (C#) nuget package. It will also be implemented in the ParallelAlgorithm (C++) package shortly.

Coming shortly…