Popular Python recipes tagged "meta:requires=heapq"

Python A* Pathfinding (With Binary Heap) (Python)

2014-08-06T10:03:01-07:00

Python recipe 578919 by Christian Careaga (algorithms, binary_search). Revision 3.

Implementation of the A-star Pathfinding algorithm in Python, using Binary heap to sort the open list

Priority Queue (with deletion) (Python)

2013-12-08T21:12:55-08:00

Python recipe 578780 by elazar (artificial_intelligence, heap, heapq, priority_queue, queue). Revision 5.

Based on the interface defined in aima-python http://aima-python.googlecode.com/svn/trunk/utils.py

Yields better performance.

heap class (Python)

2015-09-17T12:41:15-07:00

Python recipe 578694 by yota (heap). Revision 2.

heapq is a nice python module, but the interface is not so clean. I found a one-liner on this blog, it's as short as possible, but not really pythonic either :) Here is my contribution to a most readable heap class.

Simple Dijkstra Algorithm (Python)

2012-06-08T02:20:18-07:00

Python recipe 578156 by Filippo Squillace (graph). Revision 3.

The algorithm uses the priority queue version of Dijkstra and return the distance between the source node and the others nodes d(s,i).

Recursively defined, Haskell-style infinite lists (Python)

2012-05-04T14:09:14-07:00

Python recipe 578119 by John Crichton (decorator, functional, generator, infinite, itertools, lazy, recursive). Revision 2.

A decorator to simplify the creation of recursively defined, Haskell-style infinite lists -- ie. recursive generators -- inspired by Raymond Hettinger's "Technique for cyclical iteration" [*].

[*] http://code.activestate.com/recipes/576961-technique-for-cyclical-iteration/

Dijkstra shortest path implementation (Python)

2011-10-05T09:06:50-07:00

Python recipe 577892 by Shao-chuan Wang (dijkstra, optimization, shortest).

This code snippet is the implementation of Dijkstra's algorithm.

Compare algorithms for heapq.smallest (Python)

2011-12-25T23:41:23-08:00

Python recipe 577573 by Raymond Hettinger (algorithms, benchmark, heaps, performance). Revision 3.

General purpose technique for counting comparisons in various searching and sorting applications.

Queue for managing multiple SIGALRM alarms concurrently (Python)

2012-12-06T18:58:11-08:00

Python recipe 577600 by Glenn Eychaner (alarm, queue, signal). Revision 3.

In asynchronous code, signal.alarm() is extremely useful for setting and handling timeouts and other timed and periodic tasks. It has a major limitation, however, that only one alarm function and alarm time can be set at a time; setting a new alarm disables the previous alarm. This package uses a heapq to maintain a queue of alarm events, allowing multiple alarm functions and alarm times to be set concurrently.

Counter class (Python)

2011-04-17T21:27:05-07:00

Python recipe 577664 by Praveen .

Bag/multiset class for convenient tallying of hashable objects.

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.

Counter class (Python)

2009-06-29T12:24:14-07:00

Python recipe 576611 by Raymond Hettinger . Revision 11.

Bag/multiset class for convenient tallying of hashable objects.

Technique for cyclical iteration (Python)

2009-12-03T23:08:38-08:00

Python recipe 576961 by Raymond Hettinger (concurrency_model, cyclic_iterator). Revision 7.

Solution to the Hamming Number problem. Demonstrates a lazy evaluation evaluation technique using itertools.tee() to feed an iterator into itself. This is a common technique with Haskell. The deferred_output() function is the key technique for implementing a forward reference to the output of the stream.

Merge multiple (potentially infinite) sorted inputs into a single sorted output (Python)

2010-04-01T04:54:16-07:00

Python recipe 577041 by Gabriel Genellina (algorithm, algorithms, merge, sort). Revision 4.

Merge a (possibly infinite) number of already sorted inputs (each of possibly infinite length) into a single sorted output.

Similar to heapq.merge and sorted(itertools.chain(*iterables)).

Like heapq.merge, returns a generator, does not pull the data into memory all at once, and assumes that each of the input iterables is already sorted (smallest to largest).

Unlike heapq.merge, accepts an infinite number of input iterables, but requires all of them to come in ascending order (that is, their starting point must come in ascending order).

In addition, accepts a key function (like sorted, min, max, etc.)

Technique for cyclical iteration II (Python)

2010-01-20T03:54:15-08:00

Python recipe 577014 by Jakub Wroniecki (cyclic_iterator, recursive_iterator).

Inspired by this recipe: http://code.activestate.com/recipes/576961/, I played a little with the code and came with a more general piece of code implementing recursive iterators.

Sorting big files the Python 2.6 way (Python)

2009-05-30T21:51:09-07:00

Python recipe 576755 by Gabriel Genellina (binary, file, sort, sorting, text). Revision 3.

This is just a rewrite of Recipe 466302 "Sorting big files the Python 2.4 way", taking advantage of heapq.merge, context managers, and other niceties of newer Python versions. It can be used to sort very large files (millions of records) in Python. No record termination character is required, hence a record may contain embedded binary data, newlines, etc. You can specify how many temporary files to use and where they are located.

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]

LRU and LFU cache decorators (Python)

2010-08-01T01:19:23-07:00

Python recipe 498245 by Raymond Hettinger (shortcuts). Revision 6.

One-line decorator call adds caching to functions with hashable arguments and no keyword arguments. When the maximum size is reached, the least recently used entry or least frequently used entry is discarded -- appropriate for long-running processes which cannot allow caches to grow without bound. Includes built-in performance instrumentation.

Sort extremely large and/or binary files in Python (Python)

2008-02-18T18:46:39-08:00

Python recipe 546524 by Jeremy Mortis (files).

This recipe can be used to sort very large files (millions of records) in Python. No record termination character is required, hence a record may contain embedded binary data, newlines, etc. You can specify how many temporary files to use and where they are located.

Iterator merge 2 (Python)

2007-12-07T22:16:05-08:00

Python recipe 535160 by Jonathan Cronin (algorithms). Revision 2.

Memory efficient multi-way iterator merge, without using heapq

Priority dict: a priority queue with updatable priorities (Python)

2007-06-26T09:20:06-07:00

Python recipe 522995 by Matteo Dell'Amico (search).

You may have needed a priority queue with the ability to change the priorities of elements that were in the queue. This recipe solves this problem in an efficient way.