Package for the RMinimum algorithm
Project description
RMinimumAlgorithm
A Python implementation of the RMinimum algorithm.
The algorithm is presented in the paper Fragile Complexity of ComparisonBased 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 tradeoff 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 noneminimum 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 tradeoffs 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:
 Randomly group the elements into n/2 pairwisedisjoint 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.
 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).
 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 {ww ∈ Wi ∧ w < mi }.
 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
 Runtime: RMinimum requires linear work w(n) = O(n).
 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.
 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
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size RMinimum_Algorithm0.0.1py3noneany.whl (3.5 kB)  File type Wheel  Python version py3  Upload date  Hashes View 
Filename, size RMinimumAlgorithm0.0.1.tar.gz (2.8 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for RMinimum_Algorithm0.0.1py3noneany.whl
Algorithm  Hash digest  

SHA256  3f438468191adce0e9d07a7c0cc447ad9bb57d1478343b572d5341c16808aa91 

MD5  fa285f44f4b70d981183cb823ed34f82 

BLAKE2256  d5f1045c78384ffd03e6e104e442f6a1475941bc0675c0bf3039b836e1a9b0c9 