Skip to main content

Package for the RMinimum algorithm

Project description

RMinimum-Algorithm

GitHub status GitHub top language Travis GitHub

A Python implementation of the RMinimum algorithm.

The algorithm is presented in the paper Fragile Complexity of Comparison-Based Algorithms by Prof. Dr. Ulrich Meyer and others in 2018. A reworked version of it can can be found on arXiv.org.

It introduces the algorithms RMinimum and RMedian and also the concept of fragile complexity, i.e. the amount of times an element has been compared during the process of the algorithm.

The package was published on PyPI and tested on Travis CI.


Folder Content
data all experimental data as .csv files
docs scientific paper presenting the algorithm (from arXiv)
jupyter Jupyter Notebook validation and test files
src Python source code
tests PyTest test files

Algorithm

In the following we present RMinimum, a randomized recursive algorithm for finding the min- imum among n distinct elements. The algorithm has a tuning parameter k(n) controlling the trade-off between the expected fragile complexity f_min(n) of the minimum element and the maxi- mum expected fragile complexity f_rem(n) of the remaining none-minimum elements; if n is clear from the context, we use k instead of k(n). Depending on the choice of k, we obtain interest- ing trade-offs for the pair hE [fmin (n)] , max E [frem (n)]i ranging from <O(ε−1loglog(n)), O(n_ε)> to <O(log(n)/loglog(n)), O(log(n)/loglog(n))>. Given a total ordered set X of n distinct elements, RMinimum performs the following steps:

  1. Randomly group the elements into n/2 pairwise-disjoint pairs and use one comparison for each pair to partition X into two sets L and W of equal size: W contains all winners, i.e. elements that are smaller than their partner. Set L gets the losers, who are larger than their partner and hence cannot be the global minimum.
  2. Partition L into n/k random disjoint subsets L_1 , . . . , L_n/k each of size k and find the minimum element mi in each Li using a perfectly balanced tournament tree (see Theorem 1).
  3. Partition W into n/k random disjoint subsets W_1 , . . . , W_n/k each of size k and filter out all elements in W_i larger than mi to obtain W_0 = U_i {w|w ∈ Wi ∧ w < mi }.
  4. If |W_0| ≤ log2 (n_0) where n0 is the initial problem size, find and return the minimum using a perfectly balanced tournament tree (see Theorem 1). Otherwise recurse on W_0.

Complexity

  1. Runtime: RMinimum requires linear work w(n) = O(n).
  2. Let k(n) = n_ε for 0 < ε ≤ 1/2. Then RMinimum requires E(f_min) = O(ε−1loglogn) comparisons for the minimum and E(f_rem) = O(n_ε) for the remaining elements.
  3. Let k(n) = logn/loglogn. Then RMinimum requires E(f_min) = O(logn/loglogn) comparisons for the minimum and E(f_rem) = O(logn/loglogn) for the remaining elements.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for RMinimum-Algorithm, version 0.0.1
Filename, size File type Python version Upload date Hashes
Filename, size RMinimum_Algorithm-0.0.1-py3-none-any.whl (3.5 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size RMinimum-Algorithm-0.0.1.tar.gz (2.8 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page