Hacker News Reader

Comment by scroyston | Hacker News Reader

I'm all for data over code, but I'd use a Rete network so my program didn't run in O(DISTRIBUTIONS * RULES) time. Yes data design is important, but you need to be algorithm savvy in order to know the best way to design your data structures.

View on HN

I think that in this case you get a non-trivial performance gain with some basic implementation improvements. You can replace the row-by-row round trip with a single SQL UPDATE with a LIMIT (or a LIMITed subquery if the server does it that way).

Also, the performance of the algorithm in the essay would be linear to the number of rows requiring update, can you elaborate on whether the RETE alogorithm can do any better in this case.

And finally, thanks for the note on RETE, I will have to investigate that.

Comment space is a bit limited to do an adequate explanation. For rules that have straightforward (but possibly compound) predicates, Rete will give you O(1) lookup. From wikipedia: "In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system)."

http://en.wikipedia.org/wiki/Rete_algorithm

My favorite reference on the subject is at the bottom of the wikipedia page: "Production Matching for Large Learning Systems - R Doorenbos"

Sadly (and strangely) many of the "Rete Engines" today do it wrong and will not give you effecient lookups.

Reply on news.ycombinator.com