Most viewed recipes tagged "meta:requires=heapq"http://code.activestate.com/recipes/tags/meta:requires=heapq/views/2014-08-06T10:03:01-07:00ActiveState Code RecipesCounter class (Python)
2009-06-29T12:24:14-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/576611-counter-class/
<p style="color: grey">
Python
recipe 576611
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
.
Revision 11.
</p>
<p>Bag/multiset class for convenient tallying of hashable objects.</p>
LRU and LFU cache decorators (Python)
2010-08-01T01:19:23-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/498245-lru-and-lfu-cache-decorators/
<p style="color: grey">
Python
recipe 498245
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/shortcuts/">shortcuts</a>).
Revision 6.
</p>
<p>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.</p>
Sorting big files the Python 2.4 way (Python)
2006-04-13T10:43:13-07:00Nicolas Lehuenhttp://code.activestate.com/recipes/users/1599156/http://code.activestate.com/recipes/466302-sorting-big-files-the-python-24-way/
<p style="color: grey">
Python
recipe 466302
by <a href="/recipes/users/1599156/">Nicolas Lehuen</a>
(<a href="/recipes/tags/files/">files</a>).
Revision 6.
</p>
<p>This recipe can be used to sort big files (much bigger than the available RAM) according to a key. The sort is guaranteed to be stable on Python 2.3.</p>
bag collection class (Python)
2004-11-30T07:57:31-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/259174-bag-collection-class/
<p style="color: grey">
Python
recipe 259174
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 6.
</p>
<p>Implement Smalltalk's bag class (similar to MultiSets in C++ or bag's in Objective C or Haskell's Edison module).</p>
Python A* Pathfinding (With Binary Heap) (Python)
2014-08-06T10:03:01-07:00Christian Careagahttp://code.activestate.com/recipes/users/4186639/http://code.activestate.com/recipes/578919-python-a-pathfinding-with-binary-heap/
<p style="color: grey">
Python
recipe 578919
by <a href="/recipes/users/4186639/">Christian Careaga</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/binary_search/">binary_search</a>).
Revision 3.
</p>
<p>Implementation of the A-star Pathfinding algorithm in Python, using Binary heap to sort the open list</p>
Sorting big files the Python 2.6 way (Python)
2009-05-30T21:51:09-07:00Gabriel Genellinahttp://code.activestate.com/recipes/users/924636/http://code.activestate.com/recipes/576755-sorting-big-files-the-python-26-way/
<p style="color: grey">
Python
recipe 576755
by <a href="/recipes/users/924636/">Gabriel Genellina</a>
(<a href="/recipes/tags/binary/">binary</a>, <a href="/recipes/tags/file/">file</a>, <a href="/recipes/tags/sort/">sort</a>, <a href="/recipes/tags/sorting/">sorting</a>, <a href="/recipes/tags/text/">text</a>).
Revision 3.
</p>
<p>This is just a rewrite of <a href="http://code.activestate.com/recipes/466302/">Recipe 466302</a> "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.</p>
Iterator Merge (Python)
2007-02-09T18:01:54-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/491285-iterator-merge/
<p style="color: grey">
Python
recipe 491285
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
Revision 3.
</p>
<p>Memory efficient multi-way iterator merge.</p>
Priority dict: a priority queue with updatable priorities (Python)
2007-06-26T09:20:06-07:00Matteo Dell'Amicohttp://code.activestate.com/recipes/users/4057132/http://code.activestate.com/recipes/522995-priority-dict-a-priority-queue-with-updatable-prio/
<p style="color: grey">
Python
recipe 522995
by <a href="/recipes/users/4057132/">Matteo Dell'Amico</a>
(<a href="/recipes/tags/search/">search</a>).
</p>
<p>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.</p>
Dijkstra shortest path implementation (Python)
2011-10-05T09:06:50-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/577892-dijkstra-shortest-path-implementation/
<p style="color: grey">
Python
recipe 577892
by <a href="/recipes/users/4168519/">Shao-chuan Wang</a>
(<a href="/recipes/tags/dijkstra/">dijkstra</a>, <a href="/recipes/tags/optimization/">optimization</a>, <a href="/recipes/tags/shortest/">shortest</a>).
</p>
<p>This code snippet is the implementation of Dijkstra's algorithm.</p>
Lazy sorting (Python)
2004-05-03T12:30:10-07:00Matteo Dell'Amicohttp://code.activestate.com/recipes/users/1782068/http://code.activestate.com/recipes/280501-lazy-sorting/
<p style="color: grey">
Python
recipe 280501
by <a href="/recipes/users/1782068/">Matteo Dell'Amico</a>
(<a href="/recipes/tags/search/">search</a>).
Revision 2.
</p>
<p>This generator will sort only the requested part of a list. Useful for getting just the first few elements of a list and avoiding the overhead of sorting the whole thing.</p>
Simple Dijkstra Algorithm (Python)
2012-06-08T02:20:18-07:00Filippo Squillacehttp://code.activestate.com/recipes/users/4174931/http://code.activestate.com/recipes/578156-simple-dijkstra-algorithm/
<p style="color: grey">
Python
recipe 578156
by <a href="/recipes/users/4174931/">Filippo Squillace</a>
(<a href="/recipes/tags/graph/">graph</a>).
Revision 3.
</p>
<p>The algorithm uses the priority queue version of Dijkstra and return the distance between the source node and the others nodes d(s,i). </p>
Compare algorithms for heapq.smallest (Python)
2011-12-25T23:41:23-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/577573-compare-algorithms-for-heapqsmallest/
<p style="color: grey">
Python
recipe 577573
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/benchmark/">benchmark</a>, <a href="/recipes/tags/heaps/">heaps</a>, <a href="/recipes/tags/performance/">performance</a>).
Revision 3.
</p>
<p>General purpose technique for counting comparisons in various searching and sorting applications.</p>
N-way merge sort (Python)
2007-05-01T18:58:46-07:00Mike Klaashttp://code.activestate.com/recipes/users/4052999/http://code.activestate.com/recipes/511509-n-way-merge-sort/
<p style="color: grey">
Python
recipe 511509
by <a href="/recipes/users/4052999/">Mike Klaas</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>Merge sorted iterables with stability and built-in DSO</p>
Coroutines in Python (Python)
2004-08-23T06:47:19-07:00Bernhard Mulderhttp://code.activestate.com/recipes/users/189076/http://code.activestate.com/recipes/300019-coroutines-in-python/
<p style="color: grey">
Python
recipe 300019
by <a href="/recipes/users/189076/">Bernhard Mulder</a>
.
Revision 4.
</p>
<p>This recipe shows how you can emulate coroutines in pure Python using generators.</p>
<p>With coroutine I mean a construct as available, for example, in Simula 67 or Modula2. They are like threads with two additional restrictions: at most one coroutine can be running at any time, and each coroutine yields control only at very specific points. Other terms I have heard for this concept are "cooperative multitasking", "non-preemptive multitasking" or Fibers (on Windows).</p>
Technique for cyclical iteration (Python)
2009-12-03T23:08:38-08:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/576961-technique-for-cyclical-iteration/
<p style="color: grey">
Python
recipe 576961
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/concurrency_model/">concurrency_model</a>, <a href="/recipes/tags/cyclic_iterator/">cyclic_iterator</a>).
Revision 7.
</p>
<p>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.</p>
Add key= argument to min(), max(), heapq.nsmallest() and nlargest() (Python)
2010-07-30T22:44:13-07:00Raymond Hettingerhttp://code.activestate.com/recipes/users/178123/http://code.activestate.com/recipes/355690-add-key-argument-to-min-max-heapqnsmallest-and-nla/
<p style="color: grey">
Python
recipe 355690
by <a href="/recipes/users/178123/">Raymond Hettinger</a>
(<a href="/recipes/tags/shortcuts/">shortcuts</a>).
Revision 3.
</p>
<p>Modeled after the key= argument to list.sort() and sorted().</p>
Handling ties for top largest/smallest elements (Python)
2009-04-07T18:57:35-07:00George Sakkishttp://code.activestate.com/recipes/users/2591466/http://code.activestate.com/recipes/576712-handling-ties-for-top-largestsmallest-elements/
<p style="color: grey">
Python
recipe 576712
by <a href="/recipes/users/2591466/">George Sakkis</a>
(<a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/largest/">largest</a>, <a href="/recipes/tags/smallest/">smallest</a>, <a href="/recipes/tags/top/">top</a>).
Revision 8.
</p>
<p>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:</p>
<pre class="prettyprint"><code>>>> nsmallest(3, [4,3,-2,-3,2], key=abs)
[-2, 2, 3]
</code></pre>
<p>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.</p>
<p>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:</p>
<pre class="prettyprint"><code>>>> nsmallest(3, [4,3,-2,-3,2], key=abs, ties=True)
[-2, 2]
</code></pre>
Heap, a heapq wrapper class (Python)
2007-03-09T13:55:05-08:00bearophile -http://code.activestate.com/recipes/users/2403049/http://code.activestate.com/recipes/502295-heap-a-heapq-wrapper-class/
<p style="color: grey">
Python
recipe 502295
by <a href="/recipes/users/2403049/">bearophile -</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>).
</p>
<p>A Heap wrapper class around the standard heapq, it helps avoid some common bugs with a useful OOP, and it manages a key parameter too.</p>
Sort extremely large and/or binary files in Python (Python)
2008-02-18T18:46:39-08:00Jeremy Mortishttp://code.activestate.com/recipes/users/4126022/http://code.activestate.com/recipes/546524-sort-extremely-large-andor-binary-files-in-python/
<p style="color: grey">
Python
recipe 546524
by <a href="/recipes/users/4126022/">Jeremy Mortis</a>
(<a href="/recipes/tags/files/">files</a>).
</p>
<p>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.</p>
Priority Queue (with deletion) (Python)
2013-12-08T21:12:55-08:00elazarhttp://code.activestate.com/recipes/users/4187847/http://code.activestate.com/recipes/578780-priority-queue-with-deletion/
<p style="color: grey">
Python
recipe 578780
by <a href="/recipes/users/4187847/">elazar</a>
(<a href="/recipes/tags/artificial_intelligence/">artificial_intelligence</a>, <a href="/recipes/tags/heap/">heap</a>, <a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/priority_queue/">priority_queue</a>, <a href="/recipes/tags/queue/">queue</a>).
Revision 5.
</p>
<p>Based on the interface defined in aima-python
<a href="http://aima-python.googlecode.com/svn/trunk/utils.py" rel="nofollow">http://aima-python.googlecode.com/svn/trunk/utils.py</a></p>
<p>Yields better performance.</p>