November 10, 2009
Python is a programming language that I learnt somewhat recently (something like 2, 3 years ago) and that I like very much. It is simple, to the point, and has several functional-like constructs that I am already familiar with. But Python is slow compared to other programming languages. But it was unclear to me just how slow Python was compared to other languages. It just felt slow.
So I have decided to investigate by comparing the implementation of a simple, compute-bound problem, the eight queens puzzle generalized to any board dimensions. This puzzle is most easily solved using, as Dijkstra did, a depth-first backtracking program, using bitmaps to test rapidly whether or not a square is free of attack1. I implemented the same program in C++, Python, and Bash, and got help from friends for the C# and Java versions2. I then compared the resulting speeds.
Read the rest of this entry »
77 Comments | 
algorithms, Artificial Intelligence, Bash (Shell), bit twiddling, C, data structures, hacks, programming, Python | Tagged: Artificial Intelligence, backtracking, bash, C, Chess, chess problem, chess puzzle, constant propagation, constant-folding, eight queens, eight queens problem, eight queens puzzle, g++, gcj, gmcs, java, puzzle, pygame, Python, python 2.6, recursion, recursive algorithm | 
Permalink
Posted by Steven Pigeon
December 23, 2008
In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?
I made a “top ten” list of algorithms and data structures every programmer must know about.
Read the rest of this entry »
9 Comments | algorithms, data compression, database, embedded programming, programming, Uncategorized | Tagged: array, Artificial Intelligence, Binary Search Tree, Binary Tree, Chess, disjoint set, Dynamic Programming, genetic algorithms, graph, graph algorithms, hash function, hash table, hashing, list, lookup table, memoization, one way function, QuickSort, Radix Sort, search, sorting, state space, state space search | Permalink
Posted by Steven Pigeon
