Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.002 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'exercise': 0.04; '480': 0.05; 'startup': 0.05; 'python3': 0.07; 'output,': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:string': 0.09; 'runs': 0.10; 'python': 0.11; "'from": 0.16; '0.2': 0.16; 'machine?': 0.16; 'received:80.91.229.3': 0.16; 'received:dip0.t-ipconnect.de': 0.16; 'received:plane.gmane.org': 0.16; 'received:t-ipconnect.de': 0.16; 'sec': 0.16; 'wrote:': 0.18; '>>>': 0.22; 'example': 0.22; 'import': 0.22; 'skip:+ 20': 0.22; 'this?': 0.23; 'header:User-Agent:1': 0.23; 'header:X -Complaints-To:1': 0.27; 'code': 0.31; 'once,': 0.31; 'overhead': 0.31; 'run': 0.32; 'sense': 0.34; 'subject:lists': 0.35; 'seconds': 0.37; 'expected': 0.38; 'minimum': 0.38; 'question,': 0.38; 'to:addr:python-list': 0.38; 'reported': 0.39; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'how': 0.40; 'then,': 0.60; 'took': 0.61; 'times': 0.62; 'more': 0.64; 'total': 0.65; 'skip:+ 10': 0.65; 'repeat': 0.74; '100': 0.79; '"best': 0.84; '"fast"': 0.84; '10.2': 0.84; 'bench': 0.84 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Peter Otten <__peter__@web.de> Subject: Re: generate De Bruijn sequence memory and string vs lists Date: Fri, 24 Jan 2014 09:23:36 +0100 Organization: None References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: 8Bit X-Gmane-NNTP-Posting-Host: p5084ae83.dip0.t-ipconnect.de User-Agent: KNode/4.7.3 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: 40 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1390551780 news.xs4all.nl 2959 [2001:888:2000:d::a6]:33083 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:64667 Vincent Davis wrote: > Excellent Peter! > I have a question, the times reported don't make sense to me, for example > $ python3 -m timeit -s 'from debruijn_compat import debruijn_bytes as d' > 'd(4, 8)' > 100 loops, best of 3: 10.2 msec per loop > This took ~4 secs (stop watch) which is much more that 10*.0102 Why is > this? Look at the output, it's "100 loops" 100 * 10 msec == 1 sec together with "best of 3" you are already at 3 sec, minimum as it is the "best" run. Then, how do you think Python /knows/ that it has to repeat the code 10 times on my "slow" and 100 times on your "fast" machine? It runs the bench once, then 10, then 100, then 1000 times -- until there's a run that takes 0.2 secs or more. The total expected minimum time without startup overhead is then +----calibration------+ +-measurement--+ (1 + 10 + 100) * 10msec + 3 * 100 * 10msec or about 4 secs. > $ python3 -m timeit -s 'from debruijn_compat import debruijn_bytes as d' > 'd(4, 11)' > 10 loops, best of 3: 480 msec per loop​ > This took ~20 secs vs .480*10 >>> .480*(1 + 10 + 3*10) 19.68 > d(4, 14) takes about 24 seconds (one run) This is left as an exercise ;)