Clarity vs. code reuse/generality

[Dave Angel]

pdpi wrote:
> On Jul 7, 2:16 am, Steven D'Aprano <st... at REMOVE-THIS-
> cybersource.com.au> wrote:
>   
>> On Mon, 06 Jul 2009 16:43:43 +0100, Tim Rowe wrote:
>>     
>>> 2009/7/4 kj <no.em... at 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.