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


Groups > comp.lang.python > #78356

Re: Dynamically swapping between two algorithms

Path csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path <cameron@cskk.homeip.net>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.001
X-Spam-Evidence '*H*': 1.00; '*S*': 0.00; 'algorithm': 0.04; 'dynamically': 0.07; 'subject:two': 0.07; 'comfortably': 0.09; 'linear': 0.09; 'measure': 0.09; 'pretend': 0.09; 'runtime': 0.09; 'suggestions.': 0.09; '>the': 0.16; '>to': 0.16; 'all?': 0.16; 'argument,': 0.16; 'complexity,': 0.16; 'compute': 0.16; 'decisions,': 0.16; 'from:addr:cs': 0.16; 'from:addr:zip.com.au': 0.16; 'from:name:cameron simpson': 0.16; 'inserting': 0.16; 'message-id:@cskk.homeip.net': 0.16; 'received:211.29': 0.16; 'received:211.29.132': 0.16; 'received:cskk.homeip.net': 0.16; 'received:homeip.net': 0.16; 'received:optusnet.com.au': 0.16; 'received:syd.optusnet.com.au': 0.16; 'simpson': 0.16; 'subject:between': 0.16; 'thoughts?': 0.16; 'true:': 0.16; 'wrote:': 0.18; 'bit': 0.19; 'value.': 0.19; 'seems': 0.21; 'input': 0.22; 'import': 0.22; '(in': 0.22; 'header:User-Agent:1': 0.23; 'error': 0.23; 'large,': 0.24; 'cheers,': 0.24; 'looks': 0.24; '(or': 0.24; 'source': 0.25; 'this:': 0.26; 'second': 0.26; 'certain': 0.27; 'values': 0.27; 'gets': 0.27; 'header:In-Reply- To:1': 0.27; 'point': 0.28; 'fixed': 0.29; 'wondering': 0.29; 'chris': 0.29; 'points': 0.29; 'compared': 0.30; 'code': 0.31; 'cool,': 0.31; "d'aprano": 0.31; 'large.': 0.31; 'purely': 0.31; 'steven': 0.31; 'values.': 0.31; 'run': 0.32; 'quite': 0.32; 'running': 0.33; 'becomes': 0.33; 'maybe': 0.34; 'could': 0.34; 'but': 0.35; 'add': 0.35; 'really': 0.36; 'received:com.au': 0.36; 'charset:us-ascii': 0.36; 'should': 0.36; 'wrong': 0.37; 'two': 0.37; 'performance': 0.37; 'received:211': 0.38; 'to:addr:python- list': 0.38; 'short': 0.38; 'to:addr:python.org': 0.39; 'either': 0.39; 'flat': 0.60; 'break': 0.61; 'first': 0.61; 'content- disposition:inline': 0.62; 'total': 0.65; 'different': 0.65; 'determine': 0.67; 'gathering': 0.68; 'past,': 0.68; 'repeat': 0.74; 'other.': 0.75; '(total': 0.84; 'algorithm,': 0.84; 'short,': 0.84; 'stop,': 0.84; 'terrible': 0.84; 'worthwhile.': 0.84
Date Fri, 26 Sep 2014 10:30:42 +1000
From Cameron Simpson <cs@zip.com.au>
To python-list@python.org
Subject Re: Dynamically swapping between two algorithms
MIME-Version 1.0
Content-Type text/plain; charset=us-ascii; format=flowed
Content-Disposition inline
In-Reply-To <54218831$0$29979$c3e8da3$5496439d@news.astraweb.com>
User-Agent Mutt/1.5.21 (2010-09-15)
References <54218831$0$29979$c3e8da3$5496439d@news.astraweb.com>
X-Optus-CM-Score 0
X-Optus-CM-Analysis v=2.1 cv=fvDlOjIf c=1 sm=1 tr=0 a=YuQlxtEQCowy2cfE5kc7TA==:117 a=YuQlxtEQCowy2cfE5kc7TA==:17 a=ZtCCktOnAAAA:8 a=PO7r1zJSAAAA:8 a=LcaDllckn3IA:10 a=r5UFkecV8NkA:10 a=kj9zAlcOel0A:10 a=vrnE16BAAAAA:8 a=kZ7UWmmPAAAA:8 a=RdjPRdLhP2lAbyQa10AA:9 a=CjuIK1q_8ugA:10 a=pyH5b1fOeEsA:10
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.14371.1411691448.18130.python-list@python.org> (permalink)
Lines 73
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1411691448 news.xs4all.nl 2909 [2001:888:2000:d::a6]:50279
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:78356

Show key headers only | View raw


On 24Sep2014 00:48, Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:
>I have a certain calculation which can be performed two radically different
>ways. With the first algorithm, let's call it SHORT, performance is very
>fast for small values of the argument, but terrible for large values. For
>the second algorithm, LARGE, performance is quite poor for small values,
>but excellent for large values.
>
>To add to the complexity, I perform this calculation repeatedly, in a loop:
>
>value = 1
>while True:
>    x = SHORT(value)  # Or should I use LARGE? Decisions, decisions...
>    process(x)
>    value += some_increment()
>    if condition: break
>
>Luckily, the value never gets smaller. So if I could somehow determine a
>cut-over point, CUTOFF, I might write my loop like this:
>
>value = 1
>while True:
>    f = SHORT if value < CUTOFF else LARGE
>    x = f(value)
>    process(x)
>    value += some_increment()
>    if condition: break
>
>alas, the CUTOVER point is likely to be machine-dependent. Take it as a
>given that inserting a fixed CUTOVER point into the source code (say,
>``CUTOVER = 123456``) is not likely to be very effective, and dynamically
>calculating it at import time is impractical.

I have two suggestions. The first suggestion presumes multiple CPUs, and is a 
bit of a brute force hack. If the total runtime domain for SHORT (total runtime 
for when SHORT is better) is small compared to the domain for LARGE it may be 
worthwhile.

FIRST SUGGESTION

Run SHORT and LARGE in subprocesses, flat out. When either stops, kill the 
other. Once LARGE is the first to stop, do not bother with SHORT any more.

FIRST SUGGESTION

Chris Angelico's approach looks pretty cool, but seems unstable (in choices) 
initially.

Are the input values predictable? Or a fixed sequences?

I am wondering if there's any scope for gathering all the values (or all the 
values up to comfortably past the unknown cutover point) before running SHORT 
or LARGE at all?

I was thinking bisecting to find the CUTOFF, but the cost of the wrong 
algorithm for values well over the CUTOFF would be nasty.

Alternatively:

Did you say SHORT becomes quadratic in cost as it grows and LARGE roughtly 
linear? Pretend they really are purely quadratic and linear respectively.

Then you could start with both SHORT and LARGE for your first value.
Run SHORT and LARGE. Measure the elapsed time for each. Compute their ratio.

I think you should be able to estimate the cutover point as the point where the 
two curves intersect. Run the SHORT algorithm until them. Then run both.  
Remeasure. Re-estimate. Repeat until definitely LARGE domain (estimate points 
into the past, maybe with an error margin). Then just use LARGE.

Thoughts?

Cheers,
Cameron Simpson <cs@zip.com.au>

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