Not to be outdone ...
An even greater performance boost can be achieved not only by Ernest's reordering-the-tests + pennies-are-0-modulo-5-test approach, but also by adding summation at each denomination:
(defrule find-solution
(coin (denomination penny) (count ?cp) (amount ?ap))
(test (= 0 (mod ?cp 5)))
(coin (denomination nickel) (count ?cn) (amount ?an))
(test (< (+ ?ap ?an) ?*totalAmt*))
(coin (denomination dime) (count ?cd) (amount ?ad))
(test (< (+ ?ap ?an ?ad) ?*totalAmt*))
(coin (denomination quarter) (count ?cq) (amount ?aq))
(test (< (+ ?ap ?an ?ad ?aq) ?*totalAmt*))
(coin (denomination half-dollar) (count ?ch) (amount ?ah))
(test (= (+ ?ch ?cq ?cd ?cn ?cp) ?*coinCount*))
(test (= (+ ?ah ?aq ?ad ?an ?ap) ?*totalAmt*))
=>
(printout t "Solution : " ?cp " pennies, " ?cn " nickels, " ?cd " dimes, " ?cq " quarters, " ?ch " half-dollars" crlf))
On my machine:
For ?*coinCountt* = 50 and ?*totalAmt = 100
real 0m0.963s user 0m0.750s sys 0m0.030s
For ?*coinCountt* = 50 and ?*totalAmt = 200
real 0m1.342s user 0m1.300s sys 0m0.020s
For ?*coinCountt* = 50 and ?*totalAmt = 300
real 0m2.887s user 0m2.790s sys 0m0.060s
The performance is now approximately linear in ?*totalAmt.
Win
[EMAIL PROTECTED] wrote:
I think Mitch Christensen wrote:
FYI, Making $10.00 in 100 coins took over an hour, and consumed >125meg RAM, but suceeded just fine.
Just as in any language, you can optimize programs written in the Jess language. Two simple, obvious, but powerful optimizations for this program:
1) All possible solutions must have the number of pennies divisible by 5; therefore, the (coin) facts that denote other quantities aren't needed. If you modify the setup code to not emit them, the program goes from a hour's runtime down to (on my machine) about 3:40, and it fits into the default 64M heap. But we're not through...
2) This one's a little harder to explain. We originally wrote the rule with the "pennies" pattern at the top; if you think of a sort of decision tree of possiblities, this makes the tree very bushy at the root. If instead, we make it bushier at the leaves, there's more commonality in the matches along those thick lower branches; this represents sharing of Java objects, hence lower memory consumption, hence better performance. By flipping the rule upside down so the half-dollar pattern is first, followed by quarter, etc, the time drops in half again, down to 1:46, for a total improvement of well over 30:1.
(Talking about this problem has been fun!)
---------------------------------------------------------
Ernest Friedman-Hill Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
PO Box 969, MS 9012 [EMAIL PROTECTED]
Livermore, CA 94550 http://herzberg.ca.sandia.gov
-------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]' in the BODY of a message to [EMAIL PROTECTED], NOT to the list (use your own address!) List problems? Notify [EMAIL PROTECTED] --------------------------------------------------------------------
-------------------------------------------------------------------- To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]' in the BODY of a message to [EMAIL PROTECTED], NOT to the list (use your own address!) List problems? Notify [EMAIL PROTECTED] --------------------------------------------------------------------
