Dynamically swapping between two algorithms

[Chris Angelico]

On Wed, Sep 24, 2014 at 12:48 AM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> (3) SHORT starts off relatively speedy, significantly faster than LARGE for
> the first few tens of thousands of loops. I'm not talking about trivial
> micro-optimizations here, I'm talking about the difference between 0.1
> second for SHORT versus 10 seconds for LARGE.
>
> (4) But as the size of the argument increases, SHORT suffers catastrophic
> quadratic slowdown, while LARGE slows down only linearly. (Give or take.)
>
> (5) Consequently, by the time I reach a few million loops, the difference is
> now between (say) 5 minutes for LARGE versus 15 hours for SHORT.

Are these figures for a single call to SHORT/LARGE, or for a number of
calls aggregated? How much extra cost would a bit of timing add? If
you're making the decision no more than every 0.1s, you can probably
afford to time every call, but if you're doing a thousand iterations a
second in the early phases, you don't want to add a time-of-day call
every step.

Here's a possibility that won't be perfectly optimal, but it'll sort
itself out over time:

shorttime = -1.0
largetime = 0.0
value = 1
while True:
    t = time.time()
    if shorttime < largetime:
        x = SHORT(value)
        shorttime = time.time() - t
    else:
        x = LARGE(value)
        largetime = time.time() - t
        if largetime < shorttime: break
    process(x)
    value += some_increment()
    if condition: break

# The SHORT algorithm is never going to be better, so
# switch to always using LARGE
while not condition:
    process(x)
   x = LARGE(value)
    value += some_increment()

What it'll do is try one each way, and then use whichever was quicker.
So you waste 10s early on, running the LARGE algorithm when SHORT
would have been better, but then it won't use LARGE again until SHORT
takes at least 10s. At that point, an Achilles/Tortoise race begins:
every time SHORT catches up with LARGE, LARGE takes a leap forward...
until LARGE's leap forward is insufficient for it to "catch up with"
SHORT, at which point we declare SHORT to have won the 'race' and just
run with the LARGE algorithm the whole way.

Downside: Will choose poorly if other things kick in during the timing
tests. Ideally, this should use a "CPU time used by this process"
monitor, but I'm not sure (a) if one is available to Python, and (b)
if it's at all portable, so the above just uses time.time().

(If the code is big and the overhead of merging is insignificant, the
same could be done with a flag instead of breaking out of the loop and
starting another. Take your pick.)

ChrisA