PE 75 primitive Pythagorean triples

  • Thread starter Thread starter Arman777
  • Start date Start date
  • Tags Tags
    Primitive
Click For Summary
The discussion focuses on generating primitive Pythagorean triples (a, b, c) where the sum S = a + b + c is less than 15 × 10^5. Participants debate the efficiency of using loops over m and n versus a and b for generating these triples, emphasizing the importance of understanding the mathematical properties behind the generation process. There is also a discussion about the need for profiling code to identify performance bottlenecks, particularly regarding the gcd function. Suggestions are made for improving the algorithm, including filtering out non-primitive triples and optimizing the search process. The conversation highlights the necessity of careful planning and logical thinking before coding solutions.
  • #31
Arman777 said:
We can optimize now

OK. You know my first question: "where is your program spending its time?"
 
Physics news on Phys.org
  • #32
Vanadium 50 said:
OK. You know my first question: "where is your program spending its time?"
:angel:

Sadly I don't know

Code:
         277502 function calls in 110.125 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:103(release)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:143(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:147(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:151(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:176(cb)
        2    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:222(_verbose_message)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:232(_requires_builtin_wrapper)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:307(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:311(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:318(__exit__)
        4    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:321(<genexpr>)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:369(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:416(parent)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:424(has_location)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:433(spec_from_loader)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:504(_init_module_attrs)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:576(module_from_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:58(__init__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:663(_load_unlocked)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:719(find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:740(create_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:748(exec_module)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:765(is_package)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:78(acquire)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:855(__enter__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:859(__exit__)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:882(_find_spec)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:948(_find_and_load_unlocked)
        1    0.000    0.000    0.000    0.000 <frozen importlib._bootstrap>:978(_find_and_load)
        1  109.993  109.993  110.125  110.125 P75.py:1(<module>)
    13388    0.078    0.000    0.078    0.000 P75.py:23(<setcomp>)
        3    0.000    0.000    0.000    0.000 {built-in method _imp.acquire_lock}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.create_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.exec_builtin}
        1    0.000    0.000    0.000    0.000 {built-in method _imp.is_builtin}
        3    0.000    0.000    0.000    0.000 {built-in method _imp.release_lock}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.allocate_lock}
        2    0.000    0.000    0.000    0.000 {built-in method _thread.get_ident}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.any}
        1    0.000    0.000  110.125  110.125 {built-in method builtins.exec}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.getattr}
        4    0.000    0.000    0.000    0.000 {built-in method builtins.hasattr}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        2    0.000    0.000    0.000    0.000 {built-in method builtins.print}
   250000    0.052    0.000    0.052    0.000 {built-in method math.gcd}
        2    0.000    0.000    0.000    0.000 {built-in method time.perf_counter}
    14044    0.002    0.000    0.002    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    0.000    0.000    0.000    0.000 {method 'get' of 'dict' objects}
        1    0.000    0.000    0.000    0.000 {method 'remove' of 'set' objects}
        2    0.000    0.000    0.000    0.000 {method 'rpartition' of 'str' objects}

What is this represents ?

P75.py:1(<module>)---

I guess just running takes the time and using sets which contains large numbers.
 
  • #33
Is there some other way than "set" to keep track of what lengths have been used and how often?
 
  • #34
Vanadium 50 said:
Is there some other way than "set" to keep track of what lengths have been used and how often?

Well without using set I cannot do my operations. So my algorithm fails. So I don't think there's within the current algorithm structure. But I am thinking.
 
  • #35
Arman777 said:
Well without using set I cannot do my operations.

Nonsense.

What's wrong with a plain old array of 1 to maximum length?
 
  • #36
Vanadium 50 said:
Nonsense.

I mean arrays don't support (|) or (&) operations. Of course, array's can be used. But I have to transform these operations into the loops and that's not so good.

I'll do the same thing but using extra loops to create operations.

I can do the same with set's and only using 2 simple operation symbol. I don't see how using arrays would change the run-time, without changing the algorithm itself. (Also I remember that sets are faster then when searching numbers in it. In my previous question about prime numbers I guess)

I think the problem is in the algorithm itself.

I can try to create a method where at some steps I can reset the num_set_0 so that the length of set does not exceed ten thousand
 
  • #37
OK, you're the boss. Your code runs in an hour, mine in milliseconds. What do I have to teach you. Good luck!
 
  • #38
I am not the boss. I just argued that just changing set to arrays would not make any difference without chaging the algorithm itself.

Because lists do not support -, &, | operations.

I created functions for these oprations and turn my code into the list version. At max_sum = 10 000, my code is 33 times faster then list version.

If there's a faster way then doing these logical operations on lists other then creating functions, maybe things could be different. But I don't know how to do that.
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 80 ·
3
Replies
80
Views
10K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 27 ·
Replies
27
Views
5K
  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 18 ·
Replies
18
Views
2K
  • · Replies 39 ·
2
Replies
39
Views
4K