Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Tue, 05 May 2015 17:00:05 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Throw the cat among the pigeons
References: <87h9rvm576.fsf@Equus.decebal.nl> <871tixlmp6.fsf@Equus.decebal.nl> <750db03b-e393-43ff-9ccf-5cc050af7324@googlegroups.com> <87zj5jf15q.fsf@Equus.decebal.nl> <55490FAE.8070501@davea.name> <CALwzidmuhD0HhAZKRGMbgEgVVHf05_3pw=+o2JyAwWdiOtcNNA@mail.gmail.com>
In-Reply-To: <CALwzidmuhD0HhAZKRGMbgEgVVHf05_3pw=+o2JyAwWdiOtcNNA@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.141.1430859619.12865.python-list@python.org>
Lines: 82
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:90001

On 05/05/2015 04:30 PM, Ian Kelly wrote:
> On Tue, May 5, 2015 at 12:45 PM, Dave Angel <davea@davea.name> wrote:
>> When the "simple" is True, the function takes noticeably and consistently
>> longer.  For example, it might take 116 instead of 109 seconds.  For the
>> same counts, your code took 111.
>
> I can't replicate this. What version of Python is it, and what value
> of x are you testing with?
>
>> I've looked at dis.dis(factorial_iterative), and can see no explicit reason
>> for the difference.
>
> My first thought is that maybe it's a result of the branch. Have you
> tried swapping the branches, or reimplementing as separate functions
> and comparing?
>

Logic is quite simple:


def factorial_iterative(x, simple=False):
     assert x >= 0
     result = 1
     j=2
     if not simple:
         for i in range(2, x + 1):
             #print("range value is of type", type(i), "and value", i)
             #print("ordinary value is of type", type(j), "and value", j)
             result *= i
             j += 1
     else:
         for i in range(2, x + 1):
             result *= j
             j += 1

     return result

def loop(func, funcname, arg):
     start = time.time()
     for i in range(repeats):
         func(arg, True)
     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))

     start = time.time()
     for i in range(repeats):
         func(arg)
     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))

repeats = 1

and arg is 10**4
     loop(factorial_iterative,      "factorial_iterative      ", arg)

My actual program does the same thing with other versions of the 
function, including Cecil's factorial_tail_recursion, and my optimized 
version of that.


Python 3.4.0 (default, Apr 11 2014, 13:05:11)
[GCC 4.8.2] on linux

factorial_iterative      (100000) took   3.807
factorial_iterative      (100000) took   3.664

factorial_iterative      (200000) took   17.07
factorial_iterative      (200000) took    15.3

factorial_iterative      (300000) took   38.93
factorial_iterative      (300000) took   36.01


Note that I test them in the opposite order of where they appear in the 
function.  That's because I was originally using the simple flag to test 
an empty loop.  The empty loop is much quicker either way, so it's not 
the issue.  (But if it were, the for-range version is much quicker).

I think I'll take your last suggestion and write separate functions.



-- 
DaveA