python / refactoring

Refactoring in 2 Dimensions

Recently on SO, I stumbled over the algorithm below:

for n in range(2, i):
    for x in range(2, n):
         if not (n % x):
             break
     print("{0} is PRIME".format(n))

The algorithm tests whether a number is a prime number or not. We commonly see nested `for` loops like this, but (for me) it is a very in-elegant style. Conceptually, we would ‘think’ or ‘speak’ this process by saying:

for each column in row:
     do something

PROBLEM:    there is a disconnection between the ‘thought’ to the code. So it got me thinking, how can I refactor this to more closely resemble the ‘thought’?

SOLUTION 1:

Remove the `do something` into a separate function:

def is_prime(n):
     for x in range(2, n):
         if not (n % x):
             return
    print("{0} is PRIME".format(n))
     return

 numbers = (n for n in range(2, n))
 for n in numbers:
     is_prime(n)

Advantages:    Abstracting out the logic here is key! By removing the testing logic, we have a simple statement:

for each number --> test it

I like this, I think it accurately reflects the ‘thought’. But… we are still running two `for` loops, which I would like to avoid.

SOLUTION 2:

So my next thought was to use recursion:

def is_prime(n):
    # base case
    if n < 2:
        return 
    else:
        for I in range(2, n):
            if not (n % i):
                return is_prime(n – 1)
        print(“{0} is PRIME”.format(n))
        return is_prime(n -1)

Advantage:    we all love recursion! To me, this is a far more elegant solution – in the ‘programming’ sense. It is academically pleasant. When I read this, I don’t have to balance a 2-dimensional problem in my head, (for me) it is easier to comprehend.

Disadvantage:    It is disconnected from the thought once again. But I do prefer it to the original algorithm.

SOLUTION 3:

I have one more idea – is it possible to pass the output from one function, as the input to a second function? Something along the lines of:

is_prime( number([testset]) )

Using this idea, can we pass each number in the testset to is_prime() for evaluation? I haven’t got my head around how to implement this – anyone’s thoughts / ideas would be much appreciated!

I think python will also have a list comprehension or a generator solution for this as well, which I should further investigate.

— UPDATE

SOLUTION 4:

A Pythonic generator statement (note it uses the previously defined function, is_prime())

for prime in (n for n in testset if is_prime(n)): print("{} is PRIME".format(prime))

Nicely Pythonic – and reasonably close to the `thought`

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s