Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.python > #78220

Re: Dynamically swapping between two algorithms

Path csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path <rosuav@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.006
X-Spam-Evidence '*H*': 0.99; '*S*': 0.00; 'python,': 0.02; 'else:': 0.03; 'algorithm': 0.04; 'argument': 0.05; '(b)': 0.07; 'subject:two': 0.07; 'tests.': 0.07; '0.1': 0.09; 'merging': 0.09; 'whichever': 0.09; 'cc:addr:python-list': 0.11; '-1.0': 0.16; '24,': 0.16; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'ideally,': 0.16; 'portable,': 0.16; 'subject:between': 0.16; 'time.time()': 0.16; 'true:': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'bit': 0.19; 'figures': 0.19; 'starts': 0.20; 'cc:addr:python.org': 0.22; '(a)': 0.24; 'large,': 0.24; 'cc:2**0': 0.24; 'sort': 0.25; 'switch': 0.26; 'second': 0.26; 'least': 0.26; 'header:In-Reply-To:1': 0.27; 'point': 0.28; 'on,': 0.29; 'am,': 0.29; 'possibility': 0.29; 'waste': 0.30; 'message- id:@mail.gmail.com': 0.30; "i'm": 0.30; 'code': 0.31; 'another.': 0.31; 'breaking': 0.31; "d'aprano": 0.31; 'large.': 0.31; 'overhead': 0.31; 'sep': 0.31; 'steven': 0.31; 'time:': 0.31; 'trivial': 0.31; 'probably': 0.32; 'run': 0.32; 'running': 0.33; 'could': 0.34; 'but': 0.35; 'received:google.com': 0.35; 'add': 0.35; 'done': 0.36; 'doing': 0.36; 'should': 0.36; 'seconds': 0.37; 'starting': 0.37; '(3)': 0.38; 'short': 0.38; 'itself': 0.39; 'sure': 0.39; 'how': 0.40; 'break': 0.61; "you're": 0.61; 'first': 0.61; 'making': 0.63; 'reach': 0.63; 'choose': 0.64; 'more': 0.64; 'forward': 0.65; 'relatively': 0.65; 'talking': 0.65; 'hours': 0.66; 'minutes': 0.67; 'between': 0.67; '(5)': 0.74; 'million': 0.74; 'catastrophic': 0.84; 'short,': 0.84; 'afford': 0.91; 'step.': 0.91; 'to:none': 0.92; 'poorly': 0.93; 'race': 0.95; 'won': 0.96
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:cc :content-type; bh=6eEVnRLMExNXTVOSbOF0UXFAO6FDv+B1giRgl28CwN4=; b=wSvsVAiknKnIhAu5FOISMiF8rTM6pLZfZt8lXHiluhU+nCyFtDHmtHc1Vr8hHn0hIW VoKC3HDevuu8x5EX9HhmFWsBBXXbgFEXKQiw6mj9qJ3/97kufslGcOO+J0BHHr/+oo9D aMMO1BHoO7eaufu4PwI+FpXGFIlDeE/+Jr/fEWGYOYhXCGwgwPNZZvAQ6vgrwEnwlXKG OtlfrAZ8vsVDgNR4Dfa9Uie/iO2XDH3WQi0LSMX6GTwowqtbRKRCm/6eEKBqMcd4CEcV cgTmZKXNi8aT+JUciAXWYFfLuZqTQ8ps4YBdIOl02wqbS/TRGXiZ4M2BiUBMRLtfJE4+ wr2g==
MIME-Version 1.0
X-Received by 10.50.66.234 with SMTP id i10mr22511165igt.34.1411485850874; Tue, 23 Sep 2014 08:24:10 -0700 (PDT)
In-Reply-To <54218831$0$29979$c3e8da3$5496439d@news.astraweb.com>
References <54218831$0$29979$c3e8da3$5496439d@news.astraweb.com>
Date Wed, 24 Sep 2014 01:24:10 +1000
Subject Re: Dynamically swapping between two algorithms
From Chris Angelico <rosuav@gmail.com>
Cc "python-list@python.org" <python-list@python.org>
Content-Type text/plain; charset=UTF-8
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.15
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.14267.1411485859.18130.python-list@python.org> (permalink)
Lines 65
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1411485859 news.xs4all.nl 2957 [2001:888:2000:d::a6]:38285
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:78220

Show key headers only | View raw


On Wed, Sep 24, 2014 at 12:48 AM, Steven D'Aprano
<steve+comp.lang.python@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Dynamically swapping between two algorithms Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-24 00:48 +1000
  Re: Dynamically swapping between two algorithms Chris Angelico <rosuav@gmail.com> - 2014-09-24 01:24 +1000
  Re: Dynamically swapping between two algorithms emile <emile@fenx.com> - 2014-09-23 08:33 -0700
  Re: Dynamically swapping between two algorithms MRAB <python@mrabarnett.plus.com> - 2014-09-23 16:42 +0100
  Re: Dynamically swapping between two algorithms Terry Reedy <tjreedy@udel.edu> - 2014-09-23 15:21 -0400
  Re: Dynamically swapping between two algorithms C Smith <illusiontechniques@gmail.com> - 2014-09-23 13:54 -0700
  Re: Dynamically swapping between two algorithms dieter <dieter@handshake.de> - 2014-09-24 09:44 +0200
  Re: Dynamically swapping between two algorithms Cameron Simpson <cs@zip.com.au> - 2014-09-26 10:30 +1000
  Re: Dynamically swapping between two algorithms Ethan Furman <ethan@stoneleaf.us> - 2014-09-25 20:11 -0700

csiph-web