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.

Source Distribution

RMinimum-Algorithm-0.0.1.tar.gz (2.8 kB view details)

Uploaded Source

Built Distribution

RMinimum_Algorithm-0.0.1-py3-none-any.whl (3.5 kB view details)

Uploaded Python 3

File details

Details for the file RMinimum-Algorithm-0.0.1.tar.gz.

File metadata

  • Download URL: RMinimum-Algorithm-0.0.1.tar.gz
  • Upload date:
  • Size: 2.8 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.6.1 requests/2.24.0 setuptools/50.3.2 requests-toolbelt/0.9.1 tqdm/4.51.0 CPython/3.8.5

File hashes

Hashes for RMinimum-Algorithm-0.0.1.tar.gz
Algorithm Hash digest
SHA256 a0b782a05884956f9b8e9eb119e3cc61e4c19171a10ce29f8626aba223c39284
MD5 76b8a2472f80c184ce002c8b287e0ef1
BLAKE2b-256 53f6115832f5acb62c7ddaa1af088c83621e6b27d85bd9f21932a63633de1cd2

See more details on using hashes here.

File details

Details for the file RMinimum_Algorithm-0.0.1-py3-none-any.whl.

File metadata

  • Download URL: RMinimum_Algorithm-0.0.1-py3-none-any.whl
  • Upload date:
  • Size: 3.5 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.6.1 requests/2.24.0 setuptools/50.3.2 requests-toolbelt/0.9.1 tqdm/4.51.0 CPython/3.8.5

File hashes

Hashes for RMinimum_Algorithm-0.0.1-py3-none-any.whl
Algorithm Hash digest
SHA256 3f438468191adce0e9d07a7c0cc447ad9bb57d1478343b572d5341c16808aa91
MD5 fa285f44f4b70d981183cb823ed34f82
BLAKE2b-256 d5f1045c78384ffd03e6e104e442f6a1475941bc0675c0bf3039b836e1a9b0c9

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page