{
    "info": {
        "author": "Pietro Berkes",
        "author_email": "pietro.berkes@googlemail.com",
        "bugtrack_url": null,
        "classifiers": [],
        "description": "=====\nbig_O\n=====\n\nbig_O is a Python module to estimate the time complexity of Python code from\nits execution time.  It can be used to analyze how functions scale with inputs\nof increasing size.\n\nbig_O executes a Python function for input of increasing size `N`, and measures\nits execution time. From the measurements, big_O fits a set of time complexity\nclasses and returns the best fitting class. This is an empirical way to\ncompute the asymptotic class of a function in `\"Big-O\"\n<http://en.wikipedia.org/wiki/Big_oh>`_.  notation. (Strictly\nspeaking, we're empirically computing the Big Theta class.)\n\nUsage\n-----\n\nFor concreteness, let's say we would like to compute the asymptotic behavior\nof a simple function that finds the maximum element in a list of positive\nintegers:\n\n    >>> def find_max(x):\n    ...     \"\"\"Find the maximum element in a list of positive integers.\"\"\"\n    ...     max_ = 0\n    ...     for el in x:\n    ...         if el > max_:\n    ...             max_ = el\n    ...     return max_\n    ...\n\nTo do this, we call `big_o.big_o` passing as argument the function and a\ndata generator that provides lists of random integers of length N:\n\n    >>> import big_o\n    >>> positive_int_generator = lambda n: big_o.datagen.integers(n, 0, 10000)\n    >>> best, others = big_o.big_o(find_max, positive_int_generator, n_repeats=100)\n    >>> print(best)\n    Linear: time = -0.00035 + 2.7E-06*n (sec)\n\n`big_o` inferred that the asymptotic behavior of the `find_max` function is\nlinear, and returns an object containing the fitted coefficients for the\ncomplexity class. The second return argument, `others`, contains a dictionary\nof all fitted classes with the residuals from the fit as keys:\n\n    >>> for class_, residuals in others.items():\n    ...     print('{!s:<60s}    (res: {:.2G})'.format(class_, residuals))\n    ...\n    Exponential: time = -5 * 4.6E-05^n (sec)                        (res: 15)\n    Linear: time = -0.00035 + 2.7E-06*n (sec)                       (res: 6.3E-05)\n    Quadratic: time = 0.046 + 2.4E-11*n^2 (sec)                     (res: 0.0056)\n    Linearithmic: time = 0.0061 + 2.3E-07*n*log(n) (sec)            (res: 0.00016)\n    Cubic: time = 0.067 + 2.3E-16*n^3 (sec)                         (res: 0.013)\n    Logarithmic: time = -0.2 + 0.033*log(n) (sec)                   (res: 0.03)\n    Constant: time = 0.13 (sec)                                     (res: 0.071)\n    Polynomial: time = -13 * x^0.98 (sec)                           (res: 0.0056)\n\nSubmodules\n----------\n\n- `big_o.datagen`: this sub-module contains common data generators, including\n  an identity generator that simply returns N (`datagen.n_`), and a data\n  generator that returns a list of random integers of length N\n  (`datagen.integers`).\n\n- `big_o.complexities`: this sub-module defines the complexity classes to be\n  fit to the execution times. Unless you want to define new classes, you don't\n  need to worry about it.\n\n\nStandard library examples\n-------------------------\n\nSorting a list in Python is O(n*log(n)) (a.k.a. 'linearithmic'):\n\n    >>> big_o.big_o(sorted, lambda n: big_o.datagen.integers(n, 10000, 50000))\n    (<big_o.complexities.Linearithmic object at 0x031DA9D0>, ...)\n\nInserting elements at the beginning of a list is O(n):\n\n    >>> def insert_0(lst):\n    ...     lst.insert(0, 0)\n    ...\n    >>> print(big_o.big_o(insert_0, big_o.datagen.range_n, n_measures=100)[0])\n    Linear: time = -4.2E-06 + 7.9E-10*n (sec)\n\nInserting elements at the beginning of a queue is O(1):\n\n    >>> from collections import deque\n    >>> def insert_0_queue(queue):\n    ...     queue.insert(0, 0)\n    ...\n    >>> def queue_generator(n):\n    ...      return deque(range(n))\n    ...\n    >>> print(big_o.big_o(insert_0_queue, queue_generator, n_measures=100)[0])\n    Constant: time = 2.2E-06 (sec)\n\n`numpy` examples\n----------------\n\nCreating an array:\n\n- `numpy.zeros` is O(n), since it needs to initialize every element to 0:\n\n    >>> import numpy as np\n    >>> big_o.big_o(np.zeros, big_o.datagen.n_, max_n=100000, n_repeats=100)\n    (<class 'big_o.big_o.Linear'>, ...)\n\n- `numpy.empty` instead just allocates the memory, and is thus O(1):\n\n    >>> big_o.big_o(np.empty, big_o.datagen.n_, max_n=100000, n_repeats=100)\n    (<class 'big_o.big_o.Constant'> ...)\n\nAdditional examples\n--------------\n\nWe can compare the estimated time complexities of different Fibonacci number\nimplementations. The naive implementation is exponential O(2^n). Since this\nimplementation is very inefficient we'll reduce the maximum tested n:\n\n    >>> def fib_naive(n):\n    ...     if n < 0:\n    ...         return -1\n    ...     if n < 2:\n    ...         return n\n    ...     return fib_naive(n-1) + fib_naive(n-2)\n    ...\n    >>> print(big_o.big_o(fib_naive, big_o.datagen.n_, n_repeats=20, min_n=2, max_n=25)[0])\n    Exponential: time = -11 * 0.47^n (sec)\n\nA more efficient implementation to find Fibonacci numbers involves using\ndynamic programming and is linear O(n):\n\n    >>> def fib_dp(n):\n    ...     if n < 0:\n    ...         return -1\n    ...     if n < 2:\n    ...         return n\n    ...     a = 0\n    ...     b = 1\n    ...     for i in range(2, n+1):\n    ...         a, b = b, a+b\n    ...     return b\n    ...\n    >>> print(big_o.big_o(fib_dp, big_o.datagen.n_, n_repeats=100, min_n=200, max_n=1000)[0])\n    Linear: time = -1.8E-06 + 7.3E-06*n (sec)\n\n\nLicense\n-------\n\nbig_O is released under BSD-3. See LICENSE.txt .\n\nCopyright (c) 2011-2018, Pietro Berkes. All rights reserved.",
        "description_content_type": "",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/pberkes/big_O",
        "keywords": "",
        "license": "LICENSE.txt",
        "maintainer": "",
        "maintainer_email": "",
        "name": "big_O",
        "package_url": "https://pypi.org/project/big_O/",
        "platform": "",
        "project_url": "https://pypi.org/project/big_O/",
        "project_urls": {
            "Homepage": "https://github.com/pberkes/big_O"
        },
        "release_url": "https://pypi.org/project/big_O/0.9/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Empirical estimation of time complexity from execution time",
        "version": "0.9"
    },
    "last_serial": 4428825,
    "releases": {
        "0.7": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a5da4e1d7ded6acb1f00a429b59bcc8f",
                    "sha256": "40834b0f24590cc76e5b98a731babc15a2ba46142f175e65f622531ad1ca505f"
                },
                "downloads": -1,
                "filename": "big_O-0.7.zip",
                "has_sig": false,
                "md5_digest": "a5da4e1d7ded6acb1f00a429b59bcc8f",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 21023,
                "upload_time": "2011-02-06T14:00:04",
                "url": "https://files.pythonhosted.org/packages/8c/6e/0efb50013e6b739b4747d3c9ddeec54b985d2c2d646b0b9a0a2cc347c2a2/big_O-0.7.zip"
            }
        ],
        "0.8.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "40ad962ac62ebc5a2ef75f8166060467",
                    "sha256": "fe95889830cc88eace8af69d194d14ed19dfbb030d92b1b4ce11297b8c375228"
                },
                "downloads": -1,
                "filename": "big_O-0.8.1.tar.gz",
                "has_sig": false,
                "md5_digest": "40ad962ac62ebc5a2ef75f8166060467",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6232,
                "upload_time": "2018-01-24T08:51:30",
                "url": "https://files.pythonhosted.org/packages/55/c2/a28897f000af9e61de9ba29b90e5275e4cf99ac54c1a3360e06666ae9612/big_O-0.8.1.tar.gz"
            }
        ],
        "0.9": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "6904fe76f951c5fecee5fe53bd79882c",
                    "sha256": "3d34d968e68598913686644e3316ca4990718d966f56bc5d731bb66cd2b45665"
                },
                "downloads": -1,
                "filename": "big_O-0.9.tar.gz",
                "has_sig": false,
                "md5_digest": "6904fe76f951c5fecee5fe53bd79882c",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7737,
                "upload_time": "2018-10-29T19:25:42",
                "url": "https://files.pythonhosted.org/packages/44/df/70f3ad0f78926467c8296a69c8eff6babbc24a855d50e3f1efddf7fbc18a/big_O-0.9.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "6904fe76f951c5fecee5fe53bd79882c",
                "sha256": "3d34d968e68598913686644e3316ca4990718d966f56bc5d731bb66cd2b45665"
            },
            "downloads": -1,
            "filename": "big_O-0.9.tar.gz",
            "has_sig": false,
            "md5_digest": "6904fe76f951c5fecee5fe53bd79882c",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 7737,
            "upload_time": "2018-10-29T19:25:42",
            "url": "https://files.pythonhosted.org/packages/44/df/70f3ad0f78926467c8296a69c8eff6babbc24a855d50e3f1efddf7fbc18a/big_O-0.9.tar.gz"
        }
    ]
}