Wednesday, July 9, 2008

A crawling program

My bot is slow. Too slow. It takes up to 10s to apply 3 rules on a modestly sized fact database. And any bot that wants to have some good strategy needs at least a few hundred rules. And yep, time needed is roughly linear in the amount of rules, so that would take too long.

However, a bit of thinking shows why this is so slow. I can't believe I didn't notice it earlier, but it's very apparent. I'm using a very slow generate-and-test algorithm to find matching facts to my rules. Stupid, stupid: I've had classes every year where constraint propagation, backmarking, backjumping and other speedup techniques are explained and when I need those techniques, I forget all about them.

So, onwards to rethinking the fact matching. I just didn't think of it as a constraint satisfaction problem, but that is indeed what it is, and that is how it should be solved.

I think I should also revisit my database course, as things like join and selection ordering could be important here. Perhaps I could even make the whole constraint store use a (simple) RDMS instead of my own solution. It sounds like overkill (and it probably is), but might be something to keep in mind...

No comments: