On 1 February 2016 at 13:29, Steven D'Aprano <st...@pearwood.info> wrote: >> > although OP's problem doesn't need this, is there a better way achieve >> > this other than >> > using a balanced binary search tree. >> >> You would need to state all of the requirements for your data >> structure. If coinvalues is constant then you can use a list and the >> bisect module: >> >> https://docs.python.org/3.5/library/bisect.html >> >> That gives O(log(len(coinvalues))) lookup. > > There are unlikely to be more than dozen distinct coins. Australia has > $2, $1, 50¢, 20¢, 10¢, 5¢ coins. Even if you include the obsolete 2¢ and > 1¢ coins, that's only eight. I believe the US has $1, 50¢ (half dollar), > 25¢ (quarter), 10¢ (dime), 5¢ (nickel), 1¢ (penny). > > You're unlikely to beat a straight linear search with only a few coins > like this. Binary search has much more overhead. Especially since the > coin change problem doesn't really require a search: just iterate over > each coin in turn.
It was acknowledged that "OP's problem doesn't need this" so I assume the question was to think about it more generally somehow. -- Oscar _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
