Talk:Heronian triangles: Difference between revisions
Content added Content deleted
(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: | 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). |
::::# 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) |
::::[[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) |