Multiple subtractions is called division. It's a much more efficient loop.
In this version you have exactly as many iterations as denominations.
It the original, if you wanted to know how many 200 coins are in
1000000000, you would iterate ~5000000 times.
Here's a timing test:
denominations = ( 200, 100, 50, 25, 10, 5, 1 )
def makechange( amount, denominations ):
coins = {}
for d in denominations:
coins[d] = int( amount/d )
amount = amount%d
return coins
def oldmakechange( amount, denominations ):
coins = {}
for d in denominations:
coins[d] = 0
while amount >= d:
coins[d] += 1
amount -= d
return coins
def comparetimings( trials=10000, amount=10000000 ):
from timeit import Timer
global denominations
new = Timer( "makechange( %s, denominations )" % amount, "from __main__
import makechange, denominations" ).timeit( trials )
old = Timer( "oldmakechange( %s, denominations )" % amount, "from __main__
import oldmakechange, denominations" ).timeit( trials )
print old, new, old/new
if __name__ == '__main__':
comparetimings()
Yields: 2.83604502678 0.000821828842163 3450.89498114
i.e. the division version runs about 3500 times faster for $100,000.
It's a minor thing, but you asked how we'd improve the code. Math is a
good thing to know. ;-)
Dick Moores wrote:
> On 8/6/07, *Eric Brunson* <[EMAIL PROTECTED]
> <mailto:[EMAIL PROTECTED]> > wrote:
>
> Try something like:
>
> def makechange( amount, denominations ):
>
> coins = {}
> for d in denominations:
> coins[d] = int( amount/d )
> amount = amount%d
>
> return coins
>
> Sorry, but could you spell out your point?
>
> Dick
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
