davea at ieee
Jul 7, 2009, 12:04 PM
Post #59 of 85
(883 views)
Permalink
|
pdpi wrote:
> On Jul 7, 2:16 am, Steven D'Aprano <st...@REMOVE-THIS-
> cybersource.com.au> wrote:
>
>> On Mon, 06 Jul 2009 16:43:43 +0100, Tim Rowe wrote:
>>
>>> 2009/7/4 kj <no.em...@please.post>:
>>>
>>>> Precisely. As I've stated elsewhere, this is an internal helper
>>>> function, to be called only a few times under very well-specified
>>>> conditions. The assert statements checks that these conditions are as
>>>> intended. I.e. they are checks against the module writer's programming
>>>> errors.
>>>>
>>> Good for you. I'm convinced that you have used the assertion
>>> appropriately, and the fact that so many here are unable to see that
>>> looks to me like a good case for teaching the right use of assertions.
>>> For what it's worth, I read assertions at the beginning of a procedure
>>> as part of the specification of the procedure, and I use them there in
>>> order to document the procedure. An assertion in that position is for me
>>> a statement to the user of the procedure "it's your responsibility to
>>> make sure that you never call this procedure in such a way as to violate
>>> these conditions". They're part of a contract, as somebody (maybe you)
>>> pointed out.
>>>
>>> As somebody who works in the safety-critical domain, it's refreshing to
>>> see somebody teaching students to think about the circumstances in which
>>> a procedure can legitimately be called. The hostility you've received to
>>> that idea is saddening, and indicative of why there's so much buggy
>>> software out there.
>>>
>> LOL.
>>
>> Maybe the reason for "so much buggy software" is that people
>> inappropriately use assert, thus changing the behaviour of code depending
>> on whether it is run with the -O flag or not.
>>
>> I don't know what "hostility" you're seeing. The only hostility I'm
>> seeing is from the OP, which is bizarre considering that he asked for
>> advice and we gave it. What I see is a bunch of people concerned that the
>> OP is teaching novices a bad habit, namely, using assert for error
>> checking. He claims -- angrily and over and over again -- that in his
>> code, the assertions should never fail. Great. Good for him for knowing
>> when to use assert. (...)
>>
>
> But he doesn't.
>
> He asserts:
> assert lo < hi
> but then compares:
> sense =mp(func(hi), func(lo))
>
> sense can't ever be anything other than 1. I actually find it amusing
> that this threat got to 50 posts of raving discussion about assertions
> without anyone spotting that.
>
>
That's because the assert and the comparison are unrelated to each
other. If the function is monotonically decreasing, then by definition
lo<hi would guarantee that func(lo)>= func(hi), which would yield a
sense of 0 or -1.
Trivial example of monotonically decreasing:
def func(inp):
return 53.0 - inp
> Personally, I think the code is an unreadable mess, but that's mostly
> because of all the micro optimizations, not the generality of it.
> Here's my unoptimized, but still equally generic, version:
>
> def _binary_search(lo, hi, func, target, epsilon):
> sense =mp(func(hi), func(lo))
> if sense =0:
> return None
> guess =lo + hi) / 2.
> while abs(func(guess) - target) > epsilon:
> guess =lo + hi) / 2.
> if func(guess) > target:
> hi =uess
> elif func(guess) < target:
> lo =uess
> elif lo =hi:
> return None
> return guess
>
>
And of course your clarified function will fail if the func is
monotonically decreasing.
I still think that rather than using sense in the loop, one should
simply swap lo and hi, and continue.
> This is a newbie course, right? A while True loop might be faster, but
> it's all sorts of wrong for teaching newbies. Likewise, calculating a
> midpoint as mid =hi + lo) * .5 is an aberration in a beginner
> environment. You want your students asking why you're calculating an
> average, not asking why you're multiplying by 0.5. In the same vein, I
> have no words for your target_plus/target_minus cleverness.
>
> The right way to go about it, IMO, is to give them my version, let
> them digest it, make all the necessary changes to it to turn it into
> your (faster) version. Present benchmarks for both, then let the
> readability/performance trade-off sink in. What you achieve with this
> exercise is that, instead of making your students think "I have to
> read that crud!?", they'll respect that ugly code is often the result
> of eking out every last drop of performance from a program as you
> possibly can.
>
>
(untested)
def _binary_search(lo, hi, func, target, epsilon):
""" lo, hi are floats representing the desired range of input values to func()
func() is a function that takes a float argument, and returns a float result
target is the desired result value of func()
epsilon is the allowable error compared to target. If set too small, this function will fail by returning None
precondition: func is monotonic over the range of floating point inputs from lo to hi """
return a float value between lo and hi (inclusive) which yields approximately target
if func(lo) > func(hi):
lo, hi = hi, lo
if not (func(lo) <= target <= func(hi)):
return None #function doesn't have target value within the input range
guess = lo
while abs(func(guess) - target) > epsilon:
guess = (lo + hi) / 2.
if func(guess) > target:
hi = guess
elif func(guess) < target:
lo = guess
elif lo == hi:
return None #function is too steep to have a value within epsilon
return guess
The reason for the "too steep" condition is that with a finite
resolution for 'guess' epsilon could be enough smaller than target as
to make a result impossible. For example, if the slope is 45 degrees,
this happens when epsilon is about 2**51 smaller.
--
http://mail.python.org/mailman/listinfo/python-list
|
