Popular recipes tagged "meta:requires=bisect"

SortedCollection (Python)

2010-09-01T02:12:33-07:00

Python recipe 577197 by Raymond Hettinger (bisect, collection, sorted). Revision 9.

Wraps bisect.bisect() in an easy to use class that supports key-functions and straight-forward search methods.

Running median, mean and mode (Python)

2013-03-06T17:33:32-08:00

Python recipe 578480 by Virgil Stokes (mean, median, mode, python, running).

The following is a small contribution that I hope can be useful to Python programmers for the calculation of the running median, mean and mode. It is important to note that all the "running" calculations are done for full windows. Here is a simple example:

y = [1, 2, 3, 3, 1, 4], with a sliding window of size = 3 for the running estimations, means = 2, 2.6667, 2.3333, 2.6667 medians = 2, 3, 3, 3 modes = 1, 3, 3, 1

Efficient Running Median using an Indexable Skiplist (Python)

2010-02-07T14:40:03-08:00

Python recipe 576930 by Raymond Hettinger (advanced_data_structure, container, median, new_algorithm, skiplist, sliding_window). Revision 10.

Maintains sorted data as new elements are added and old one removed as a sliding window advances over a stream of data. Also gives fast indexed access to value. Running time per median update is proportional to the log of the window size.

An interval mapping data structure (Python)

2010-12-23T12:51:27-08:00

Python recipe 577515 by Matteo Dell'Amico (algorithms, interval, mapping).

This structure is a kind of dictionary which allows you to map data intervals to values. You can then query the structure for a given point, and it returns the value associated to the interval which contains the point. Boundary values don't need to be an integer.

In this version, the excellent blist library by Daniel Stutzbach is used for efficiency. By using the collections.MutableMapping abstract base class, the whole signature of mappings is supported.

Weighted random choice (Python)

2010-08-19T08:40:38-07:00

Python recipe 577363 by Carlos Valiente (random, sequence).

This function returns a random element from a sequence. The probability for each element in the sequence to be selected can be weighted by a user-provided callable

Sorted dictionary (Python)

2010-01-20T17:11:59-08:00

Python recipe 576998 by Jan Kaliszewski (collections, dict, dictionary, mapping, sorted, sorteddict). Revision 29.

A simple implementation of a dictionary which always (when applicable) returns keys, values, items (key-value pairs) sorted by keys (inserting/removing order doesn't matter and only keys are important; so please note that it is something different than OrderedDict in Python 3.1/2.7 or Django's SortedDict).

Handling ties for top largest/smallest elements (Python)

2009-04-07T18:57:35-07:00

Python recipe 576712 by George Sakkis (heapq, largest, smallest, top). Revision 8.

The heapq module provides efficient functions for getting the top-N smallest and largest elements of an iterable. A caveat of these functions is that if there are ties (i.e. equal elements with respect to the comparison key), some elements may end up in the returned top-N list while some equal others may not:

>>> nsmallest(3, [4,3,-2,-3,2], key=abs)
[-2, 2, 3]

Although 3 and -3 are equal with respect to the key function, only one of them is chosen to be returned. For several applications, an all-or-nothing approach with respect to ties is preferable or even required.

A new optional boolean parameter 'ties' is proposed to accomodate these cases. If ties=True and the iterable contains more than N elements, the length of the returned sorted list can be lower than N if not all ties at the last position can fit in the list:

>>> nsmallest(3, [4,3,-2,-3,2], key=abs, ties=True)
[-2, 2]

Weighted random choice (Python)

2008-07-22T06:11:19-07:00

Python recipe 576370 by Facundo Batista (algorithms).

Choices randomly an element from a list, not uniformly, but using a given weight for each element.

Weighted choice (Python)

2006-10-30T13:48:55-08:00

Python recipe 498229 by bearophile - (algorithms).

To choose among a list of objects using a specified frequency distribution.

PyDbLite, a small in-memory database engine (Python)

2011-07-18T19:36:04-07:00

Python recipe 496770 by Pierre Quentel (database). Revision 4.

A small, fast, in-memory database management program

The database object supports the iterator protocol, so that requests can be expressed with list comprehensions or generator expressions instead of SQL. The equivalent of :

cursor.execute("SELECT name FROM table WHERE age=30")
rows = cursor.fetchall()

is :

rows = table(age=30)

The module stores data in a cPickled file. Records are indexed by a unique record identifier, that can be used for direct access. Since operations are processed in memory they are extremely fast, nearly as fast as SQLite in the few tests I made, and MUCH faster than other pure-Python modules such as Gadfly or KirbyBase. An index can be created on a field to even speed up selections

Concurrency control is supported by a version number set for each record

Complete documentation is here

Iterator Algebra Implementations of Relational Join Algorithms (Python)

2006-04-26T10:55:01-07:00

Python recipe 492216 by Jim Baker (algorithms).

Implements the three standard relational join algorithms: nested loops join, hash join, and merge join, using the iterator algebra support in Python 2.4. This recipe presents code that can be used for inner join, left outer join, full outer join, and semijoins. The nested loops join supports a theta join.

An interval mapping data structure (Python)

2006-01-18T08:09:18-08:00

Python recipe 457411 by Nicolas Lehuen (algorithms). Revision 3.

Unique stable-unstable (Python)

2005-07-27T18:23:55-07:00

Python recipe 438599 by bearophile - (algorithms). Revision 3.

Python needs a unique function, this is my best try so far. It uses the faster algorithm (among five) for each situation.

Binary Search with the bisect Module (Python)

2005-02-22T15:27:36-08:00

Python recipe 389169 by Chris Perkins (shortcuts).

Writing a binary search algorithm is surprisingly error-prone. The solution: trick the built-in bisect module into doing it for you.

The documentation for bisect says that it works on lists, but it really works on anything with a __getitem__ method. You can exploit this fact to make bisect work in ways that you may not have thought of.

Example: Using a library that controls a digital video camera, I wanted to do a poor-man's auto-exposure. The goal is to find the exposure time, in milliseconds, that makes the mean pixel value about 128 (out of 0 to 255).

The trick is to create an object that "looks like" a list to the bisect module.

Implementation of sets using sorted lists (Python)

2007-05-19T07:07:23-07:00

Python recipe 230113 by Raymond Hettinger (algorithms). Revision 2.

Inspired by Py2.3's TimSort, this implementation of sets.py uses sorted lists instead of dictionaries. For clumped data patterns, the set operations can be super-efficient (for example, two sets can be determined to be disjoint with only O(n) comparisons). Also note, that the set elements are not required to be hashable; this provides a great deal more freedom than dictionary based implementations.

Rating class with mapping interface (Python)

2004-01-14T09:10:42-08:00

Python recipe 265879 by Dmitry Vasiliev (algorithms). Revision 2.

Rating with items sorted by value and accessed by key or rating index.

Priority queue (Python)

2001-09-24T10:03:00-07:00

Python recipe 68435 by Sébastien Keim (algorithms).

Priority queues are a kind of container that allows specification of the relative order of the data.

Binary search and insert in Python (Python)

2001-04-25T05:09:37-07:00

Python recipe 54159 by Noah Spurrier (search). Revision 3.

This demonstrates a simple binary search through sorted data. A binary search is a basic algorithm provided by bisect in Python. The binary search can be summarized by two lines of code: list.sort() item_insert_point = bisect.bisect (list, item)