Anonymous user
Talk:Heronian triangles: Difference between revisions
Another alternative + timing tests
(Dropping the product function and the a <= b <= c test (letting the generator component of the comprehension do that work)) |
(Another alternative + timing tests) |
||
Line 15:
::::# Apart from the probable space improvement, there seems (as it happens) to be a time improvement in the range of 50% (at least on this system with Python 2.7).
::::[[User:Hout|Hout]] ([[User talk:Hout|talk]]) 10:11, 25 October 2015 (UTC)
:::::Well, I personally don't care about the pedagogical value of using a list comprehension unassisted instead of <code>itertools.product</code>. But I agree that generating the full cartesian product isn't necessary. There is also <code>itertools.combinations_with_replacement</code> which also generates the filtered sequence. Using the following timing tests (where <code>heronian</code> contains the code for the task)
:::::<lang python>import timeit
setup = "import heronian, itertools; last = 201"
prod = """[(a, b, c) for a,b,c in itertools.product(range(1, last), repeat=3)
if a <= b <= c and a + b > c and heronian.gcd3(a, b, c) == 1 and
heronian.is_heronian(a, b, c)]"""
list_comp = """[(a, b, c) for a in range(1, last) for b in range(a, last) for c in range(b, last)
if a + b > c and heronian.gcd3(a, b, c) == 1 and
heronian.is_heronian(a, b, c)]"""
comb = """[(a, b, c) for a,b,c in itertools.combinations_with_replacement(range(1, last), 3)
if a + b > c and heronian.gcd3(a, b, c) == 1 and
heronian.is_heronian(a, b, c)]"""
print(timeit.timeit(stmt=prod, setup=setup, number=3))
print(timeit.timeit(stmt=list_comp, setup=setup, number=3))
print(timeit.timeit(stmt=comb, setup=setup, number=3))</lang>
:::::I get the following results:
:::::<lang bash>$ uname -a
Linux arch 4.2.3-1-ARCH #1 SMP PREEMPT Sat Oct 3 18:52:50 CEST 2015 x86_64 GNU/Linux
$ python2 -V
Python 2.7.10
$ python2 timetest.py
9.67713499069
6.35034918785
6.6238899231
$ python3 -V
Python 3.5.0
$ python3 timetest.py
26.007190777992946
22.86392442500801
22.943329881993122</lang>
:::::IMHO <code>itertools.combinations_with_replacement</code> is on a par with your solution. (And the functions in the <code>itertools</code> module won't waste any space because the return the items of the return sequence successively.)
:::::PS: If you wonder, why running the timing code with Python 3 is so much slower: It looks like <code>fractions.gcd</code> performs really bad on Python 3. Using <code>math.gcd</code> instead (new in Python 3.5) I get the following results:
:::::<lang bash>$ head -n 4 heronian.py
from __future__ import division, print_function
from math import sqrt, gcd
from itertools import product
$ python3 timetest.py
7.764596431006794
4.7238479950028704
4.8884705100063</lang>--[[User:AndiPersti|Andreas Perstinger]] ([[User talk:AndiPersti|talk]]) 12:39, 26 October 2015 (UTC)
| |||