I've been tripped up by this before too. The bottleneck here is actually if neighbor in closedlist
.
The in
statement is so easy to use, you forget that it's linear search, and when you're doing linear searches on lists, it can add up fast. What you can do is convert closedlist into a set
object. This keeps hashes of its items so the in
operator is much more efficient than for lists. However, lists aren't hashable items, so you will have to change your configurations into tuples instead of lists.
If the order of closedlist
is crucial to the algorithm, you could use a set for the in
operator and keep an parallel list around for your results.
I tried a simple implementation of this including aaronasterling's namedtuple trick and it performed in 0.2 sec for your first example and 2.1 sec for your second, but I haven't tried verifying the results for the second longer one.