`entail`

is presumably slower than your industrial-grade C inference algorithm, but logical statements are given as Python expressions, and entailment can be checked at the interactive prompt. This makes the module easy to use, and fun. (Source Code).
## Saturday, October 29, 2005

### Propositional logic in Python

Propositional logic inference via compressed truth tables. Module

## Sunday, October 23, 2005

### Ventiloquate

Hyperventilate + loquacious = ventiloquate, to freak out and speak too much, too fast, and use way more breath than is actually needed to explain the idea. I assumed that this word existed, but I guess it actually doesn't.

## Friday, October 14, 2005

### Basic factorization algorithms

A paper which gives pseudocode and the reasoning behind some basic factorization algorithms: Fermat factorization, Pollard rho, Pollard p-1, and Brent's method. Public domain. (PDF document).

## Saturday, October 08, 2005

### Memoization with cache clear on return of last function call

Memoization is nice, but in dynamic programming, it can eat up ever-increasing amounts of memory as your memoized function is called with various arguments. A simple solution is to clear the cache when the last function call returns. (Python Recipe).

## Thursday, October 06, 2005

### mw2html -- Export Mediawiki to static, traditional website

`mw2html`

is a Python program which exports a Mediawiki site to a traditional-looking HTML site. No indices are generated, and Wikipedia sidebars and extra formatting are removed to give a simple, streamlined site (you can substitute in your own sidebars if you wish). The outputted HTML source code is Monobook-specific and rather verbose at the moment. But the sites thus exported don't look bad. (Source code).
## Tuesday, October 04, 2005

### List of bits in Python

A memory compacted list of bits (uses 1 byte per every 8 elements). Instantiate from a list or string of bits. Otherwise behaves just like the builtin Python list class. Uses the ListMixin class also published on this page. (Source code).

## Sunday, October 02, 2005

### Timing a function (pytime)

Python's timing facilities are...unPythonic. Module

`timeit`

requires you to specify the number of iterations for the timing loop. But that number varies according to the speed of the machine you're running on, level of optimization of your code, etc. It's more Pythonic to calculate the number of iterations in the timing procedure. As so: (Source code).
### Python htmldata module

Extract and modify URLs in an HTML/XHTML/CSS document. Translate HTML/XHTML documents to and from list data structures. Use cases: robots, proxy CGI scripts, filtering of HTML and CSS, and flexible wget-like mirroring. (Module website).

### List mixin for Python

You can use

`UserDict.DictMixin`

to create custom dictionary classes. Now you can use `listmixin.ListMixin`

to create custom list classes. (Source code).
### Modified Dijkstra's algorithm in Python

Algorithm: perform a breadth-first search, always expand the vertex with the smallest cost, and don't remove duplicate vertices in the cost-priority-queue.

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For

The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

This algorithm turns out to be nearly equivalent to Dijkstra's algorithm. For

*n*vertices and*m*edges, it requires O(*n*+*m*) space, O(*m**log(*m*)) time, and always finds the shortest path.The strategy of not removing duplicate vertices is particularly helpful in Python, where the builtin priority queue class doesn't support the DECREASE-KEY operation. See my comment at David Eppstein's recipe (the comment is public domain).

### AI algorithms in Python

Uninformed search algorithms: breadth-first, depth-first, depth-limited, uniform cost, iterative deepening DFS, and bidirectional (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).

Informed search algorithms: greedy best-first, beam, A* (in both tree and graph modes). (Source code).

Subscribe to:
Posts (Atom)