[Tutor] Ingenious script (IMO)

Eric Brunson brunson at brunson.com
Mon Aug 6 19:16:23 CEST 2007


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* <brunson at brunson.com 
> <mailto:brunson at brunson.com> > 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



More information about the Tutor mailing list