Here's a response I sent to Srinivas yesterday to further explain why
a balanced binary tree is probably overkill for the "largest
denomination" selection problem. (I didn't realize that I had not
sent the following to the list.)
---------- Forwarded message ----------
From: Danny Yoo <d...@hashcollision.org>
Date: Sun, Jan 31, 2016 at 12:02 AM
Subject: Re: [Tutor] Finding the max value from a dictionary that does
not exceed a variable's value.
To: srinivas devaki <mr.eightnotei...@gmail.com>
On Sat, Jan 30, 2016 at 9:50 PM, srinivas devaki
<mr.eightnotei...@gmail.com> wrote:
> On Sun, Jan 31, 2016 at 3:54 AM, Danny Yoo <d...@hashcollision.org> wrote:
>> ---
>> I want to take the max value in the dictionary 'coinvalues' that is the
>> same as or lower than the variable 'change'. I have no idea how to search
>> through the 'coinvalues' dictionary and find the value that is highest but
>> does not exceed the value held in the variable 'change'.
>> ---
>
> although OP's problem doesn't need this, is there a better way achieve
> this other than using a balanced binary search tree.
Hi Srinivas,
Given that we're only talking about a few choices here, we likely
don't even need any kind of special data structure here. The data is
small, and simply considering each coin in turn is probably good
enough. That is, just do a linear scan. :P
---
If we really want to over-optimize, look into the bisect library.
That is, binary search is one way to make the search fast.
https://docs.python.org/3.5/library/bisect.html
You mentioned balanced binary search tree. I'm assuming that we might
pick a particular implementation, like red-black trees, or AVL trees,
or other structures. In one sense, they might be good because they
would certainly let us pick the largest appropriate denomination
quickly. But I'd argue that they would be vastly overkill, precisely
because they support operations that we just don't need for this
problem.
To be specific, a balanced binary tree supports changes over time,
such as insertions and deletions. But note that the denominations in
the problem statement don't change! Because we're not dealing with
with a collection that needs to change over time, we're not going to
do any dynamic editing operations.
All the machinery behind a balanced binary tree is there to support
dynamic insertions and deletions: if we're not doing any dynamic
insertions, all that machinery is superfluous.
... But if we really wanted to over-optimize, an alternative approach
to implement this "find the biggest appropriate denomination" question
might be to prepare, in advance, a table to help answer questions
fast. For US denominations, the table might look something like this:
LOOKUP_TABLE = [0, 1, 1, 1, 1, 5, 5, ...]
where I'll elicit the details since I don't want to just give a away
an answer to a homework question. But if we understand the binary
search approach, we should understand the lookup table approach too,
as it's fundamentally even simpler. It's just an array lookup!
Hilariously, though, the cost of setting up the lookup table is
probably a lot larger than the amount of work needed to solve the
problem with the direct manner. The lookup table approach makes sense
only if it's used a lot.
So there are several crazy avenues we can take to over-optimize this
problem. Just to make it clear: I think sticking to a simple linear
scan makes the most sense. Everything else just seems to try to make
the problem harder than it deserves to be, akin to trying to take the
size of a rectangle via integration.
http://homepage.usask.ca/~blb230/Math_Comics/Calculus_Comic_files/image001.gif
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
