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: 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 On 24Sep2014 00:48, Steven D'Aprano 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