priority queue

[Tim Peters]

[Nick Perkins]
> I need a priority queue, but I am not sure what kind I should use.  I
> will be doing insertions that will likely fall somewhere in the middle,
> and will only be removing from the front of the queue.  I expect
> insertions to out-number removals by about 2 or 3 to one.
> ...
> I am re-coding into Python a C program that I wrote which finds the
> shortest solution to 'sokoban' puzzles.  It uses an A* search.

Could be that none of the data structures you have in mind will work in the
end:  an A* search can expand too much state space to live in RAM, even if
you code it in assembler.  Look and you'll eventually find "bounded-memory
A*" algorithms, to worm around that.  In essence, when the queue "gets too
big", expanded nodes at the "bad" end of the queue are thrown away, and
replaced with a thunk for regenerating them if they ever get interesting
again (and they often never do:  the better the heuristic component of your
search, the less likely that low-scoring nodes will ever become interesting;
in the limit, this is clearly true, as with a perfect heuristic you'd never
expand a node not on an optimal path).

Also note that if the space is really a graph, it's possible to see the same
node more than once.  Depending on the problem, it may or may not be
possible for a second (third, ...) way of getting to a node to lead to a
cheaper solution, but in either case you need to *recognize* that you've
seen the node before.  So in the graph case you also need to search the
priority queue efficiently (or arrange for the node generator to remember
which nodes have been generated, and return a unique object per distinct
node).

IOW, it can get complicated.

> The easy way would be to just have a list, and .sort() it at each
> insertion.  This, i am sure, would not be the fastest way.

Even easier is to use an unsorted list L, and do

    cheapest = min(L)
    L.remove(cheapest)

to "pop" the queue.  Does it scale well?  Heck no!  It's two O(len(L))
operations.  But it will let you focus on the *interesting* part of your
problem at once, without worries that a fancy priority queue structure is
introducing bugs of its own.  Since you're presumably going to be most
interested in developing better heuristics, it's likely adequate for weeding
out bad heuristic ideas via trying simple problem instances.  Alex's
suggestion to use a sorted list in conjunction with the bisect module is
also a good one.

> I think that a heap would best suit my needs.

Last time I tried that with an A* the heap eventually got too big -- and it
was actually slower than a dirt dumb list for the small initial problem
instances alluded to above.  Doing O(N) operations via a single Python
primitive (which runs at C speed) is cheaper than coding an O(log(N))
operation *in* Python, until N gets big enough to make this an obvious lie.

> I could code one myself, but it must have been done before.
> I can't find one in the cookbook, or the vaults!

If you find a canned A* algorithm, it's probably going to be too much of a
pig to stick with before you're solving problems of the size you *want* to
tackle.  Since you're going to have to invent your own custom A* in the end
anyway, may as well begin with something dirt simple.

> I think that the ease of implementing heuristics and algorithms in
> Python will allow me to write a 'smarter' program than the C version.
> In AI, smarter algorithms can give a performance boost of many orders
> of magnitude, which I hope will overwhelm any mere constant factor in
> speed penalty for going from C to Python.

You're on the right track!  I've often had the joy of writing Python
programs that ran 100s of times faster than competing C programs, simply
because I was able to throw away 10 full implementations before my coworkers
were able to get the bugs out of their first C stab.  The more poorly
understood the problem, the more likely this is to win big (assuming you've
got lots of ideas for approaching it!  Python will be a real aid in *trying*
them quickly.  The only real help it is in *suggesting* an approach, though,
is to subtly <wink> push you toward "Hmm.  I wonder whether I could use
dicts to advantage ...".).

keep-it-simple-until-it-gets-too-interesting-to-bear-ly y'rs  - tim