On Wednesday 06 May 2015 14:05, Steven D'Aprano wrote:
[...]
Here are those anomalous timing results again:
> code = "fact(50000)"
> t1 = Timer(code, setup="from __main__ import factorial_while as fact")
> t2 = Timer(code, setup="from __main__ import factorial_reduce as fact")
> t3 = Timer(code, setup="from __main__ import factorial_forloop1 as fact")
> t4 = Timer(code, setup="from __main__ import factorial_forloop2 as fact")
> for t in (t1, t2, t3, t4):
> print(min(t.repeat(repeat=3, number=2)))
>
>
> which takes about two minutes on my computer, and prints:
>
> 8.604736926034093 # while loop
> 10.786483339965343 # reduce
> 10.91099695302546 # for loop
> 10.821452282369137 # silly version of the for loop
[...]
> What is surprising is that for very large input like this, the while loop
> is significantly faster than reduce or either of the for-loops. I cannot
> explain that result.
I re-ran the results on a different computer, and got similar results:
7.364120149984956
9.26512472704053
9.141491871327162
9.16900822892785
The while loop is surprisingly faster for calculating fact(50000). A thought
came to mind: the while loop is different from the other three versions, in
that it performs the multiplications from n down to 2, rather than 2 up to
n. Maybe that has something to do with it?
Introducing version five of the factorial:
def factorial_reduce2(n):
assert n >= 0
return reduce(mul, range(n, 1, -1), 1)
t5 = Timer(code, setup="from __main__ import factorial_reduce2 as fact")
for t in (t1, t2, t3, t4, t5):
print(min(t.repeat(repeat=3, number=2)))
And results:
7.36792928725481 # while loop
9.271950023248792 # reduce, counting up
9.14769447594881 # for loop
9.154150342568755 # silly for loop
7.430811045691371 # reduce, counting down
My interpretation of this is that the difference has something to do with
the cost of multiplications. Multiplying upwards seems to be more expensive
than multiplying downwards, a result I never would have predicted, but
that's what I'm seeing. I can only guess that it has something to do with
the way multiplication is implemented, or perhaps the memory management
involved, or something. Who the hell knows?
Just to be sure:
def factorial_forloop3(n):
assert n >= 0
result = 1
for i in range(n, 1, -1):
result *= i
return result
t6 = Timer(code, setup="from __main__ import factorial_forloop3 as fact")
print(min(t6.repeat(repeat=3, number=2)))
which prints 7.36256698705256.
Lesson to be learned: what you think is important may not be, and what you
think is irrelevant may be.
Historical fact: for a period of about 60 years, long after the trick to
curing and preventing scurvy was known, the British navy suffered greatly
from scurvy again (although not to the same degree as they had been in the
17th and 18th centuries). The problem was due to confusion between *lemons*
and *limes*. The navy started by using the term "lime" for both lemons and
sweet limes from the Mediterranean, as well as West Indian limes: three
different citrus fruit. To cut costs and encourage British commerce, the
navy gradually stopping buying lemons from Spain and swapped over almost
entirely to West Indian limes. Unfortunately limes, and especially West
Indian limes, have significantly less Vitamin C than lemons, and the
sailors' daily allowance was about 75% less effective on ships that used
limes than for those that used Spanish lemons. Scurvy, which had practically
be eradicated in the 1850s and 60s, returned, and was a significant factor
in World War One. (Especially for the French and Russian armies.)
This simple confusion wasn't sorted out until the 1920s, long after Vitamin
C was isolated and named. Apparently nobody noticed, or cared, that the two
different fruit tasted different and looked different, or concluded that
perhaps they had different medicinal properties.
But then, for many decades, vinegar and dilute sulphuric acid were
recommended as cures for scurvy *solely* on the basis that they were acidic
just like proven cures oranges, lemons and sauerkraut.
--
Steven
--
https://mail.python.org/mailman/listinfo/python-list
