Python optimizing code.

Question

Hello, I started to learn python as a hobby a few months ago (meaning I am not an expert).
I started to solve some kata on code wears.
But I am stuck on two for the same reason " time out" meaning the server cannot run my cod in the time frame required and my code need some optimization.
The trouble is I have no idea how to optimize this.

I was asked to write a code, that give you the first pair of prime in a given interval (m and n) who are separated by a value (g) .
For example in the frame (100, 110), 101 and 103 are the first two primes separated by 2.
def step(g, m, n):
r =[]
for x in range(m,n+1):
for k in range(3,x):
if x%k == 0:
break
else:
r.append(x)
for x,y in enumerate(r[0:-1]):
for y in r[x+1:-1]:
if (y - r[x]) == g:
return [r[x],y]

Same with this one where you have to find the prim in an interval, where the reverse number is also a prime ( 9923 is prime and 3299 is also prime)

def backwards_prime(start, stop):
w =[]
for x in range(start,stop+1):
for y in range(2,x):
if x%y == 0:
break

else:
nx = int(str(x)[::-1])

for b in range(2,nx):
if nx%b == 0:
break
else:
w.append(x)

return sorted(w)

I do not see how to optimize those codes, any input appreciated.

Answer 1

See if this helps you.
https://code.sololearn.com/c5aLP3Q2anUF/?ref=app

Answer 2

You are recalculating all the primes in every loop, and in not very efficient manner.
Some techniques when you want to determine if a number is prime:
- 2 is the first prime, so start the loop from 3
- check every odd number only (you can add a third parameter to range()) because even numbers are surely not primes
- when you reach square root of x, no more reason to test any more numbers.
- you have to repeat this test many times, then memoization can be very helpful, that is store all the primes in a list or set, only use the modulo check for numbers that are higher than the last prime you found
- if you know the upper bound of the potential numbers, you can also use the sieve of Eratosthenes to build up a list of primes upfront
- you can write more than one function to solve a problem, if it makes sense
- if you are truly stuck you can reveal the solution of others on codewars, and learn from them
- pythonic memoization example
https://code.sololearn.com/cWpFUu2kmHLZ/?ref=app

Answer 3

nicolas seespan I agree with your mindset towards the coding & agree that it is helpful to be able to write your own code which simulates an import function.
But it is also nice to be able to use the libraries to create quick, simple to read & efficient codes.
The end result is ultimately a reflection of what you wanted to achieve.

Answer 4

🤣 Sometimes disappointing works

Answer 5

Hello I checked the solution yesterday.
Checking the square root was the key apparently.

I tried to import sympy but it did not work and it was feeling a little like cheating. I mean that is a Kyu6 level problem, not really where you are expected to know all the python library :-) .

A little disappointed that the solution was purely mathematical and related to how to calculate prime, I think that they should mention this in the problem. I spend 3 hours trying to optimize my code :
- only calculating the odd value, I did that in fact but I was still timing out.
- breaking the loop as soon as the condition was met on the first problem also did not work
- switching from using enumerate to not use enumerate.

In the end I did not look at optimizing the prime calculation as I was assuming that the issue was on the code...

Well I can of feel better my code was not so bad after all.

Answer 6

I know that knowing the library is part of learning the language.
But for now I want to stick to the basic as much as possible.

For example on this kata, they ask to count the number of charactere in a string that are repeated .
I knew about the Counter function. But what the point of solving this by using it ?
I there not another way to use the basic elements and reach the same results ?
I am just doing small piece of code on my free time, so I invest my time in learning how to use the common elements :-)

v = sorted(list(text.lower()))
n = []
c = 0
i = 0

for x in v:
if x not in n:
n.append(x)
i = 0
elif x in n and i == 0 :
c += 1
i = 1

return c

Answer 7

Well if that's the way to do it, it would be disappointing...

Answer 8

Yeah... 6kyu problems usually are not that sensitive to performance, but as you progress to more complex tasks this can increasingly come into play. Computing power is abundant these days, so some developers fail to make their code efficient.
You definitely have to think about the time complexity of your algorithms. And the efficiency of the data types you use. Set and dict are typically faster by several magnitudes than lists. Using lazy evaluation (generator expressions) can reduce memory requirement.

Don't be afraid to use built-in libraries, when it make sense. Sometimes you can solve things with amazing simplicity using collections, itertools, functools library. It is not cheating, it only shows deeper knowledge of the language.

Answer 9

nicolas seespan that's cool, laying down the fundamentals is important. There are many ways to solve a task like this. And I love codewars because they show what would have been an even better way than what I came up with :)

Some advice I can give you:
- try to aim for pythonicness. Even if we don't talk about libraries, some language constructs are extremely useful. Like: learn to master list comprehensions.
- use the right data type that makes the most sense and is efficient. In your last example n could have been a set, and i could have been a bool (True False)
- name your variables properly, not with single letters but with meaningful words. That way when you read your code again after a few days or months, you will instantly remember the purpose of that variable, even if you don't write comments. (but you can also add comments if a part of the code is confusing or not trivial).

Have fun, cheers!