2
\$\begingroup\$

I'm working on a program that generates a maximal geometric progression of at least 3 integers when given a number that the greatest value shouldn't exceed.

My current code works, and it's quick(ish) with small numbers, but anything past 100 takes far longer than I'd like, as I need to calculate numbers in ranges from \$10^7\$ to \$10^{20}\$.

If possible, I'd like to eliminate using Threads, as Python's are known for their lackluster performance.

from itertools import izip,islice,tee,takewhile
from threading import Thread
from Queue import Queue

#initialize the queue
g=Queue()

#checks that all values end with `.0`
def int_check(l):
    for i in l:
        if i-int(i)!=0: return False
    return True

#checks if a generated list fits the criteria
def check(obj):
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None))) and len(obj)>2 and int_check(obj)

#thread target
def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.put(takewhile(lambda i: i<=n,t))

#starts threads, calculates final value, and manages queue
def geo_prog(n):
    #Queue -> list
    def dump_queue(q):
        q.put('EOQ')
        res=[]
        return (i for i in iter(q.get,'EOQ'))

    for s in xrange(int(n/4),int(n*0.8)+1):
        t=Thread(target=calc,args=(s,n,g))
        t.start()
        t.join()

    return max(map(sum,dump_queue(g)))

#ex usage
print geo_prog(100)

Examples

geo_prog(4) -> 7.0
geo_prog(10) -> 15.0
geo_prog(12) -> 21.0
geo_prog(100) -> 240.0
\$\endgroup\$
6
  • \$\begingroup\$ Just out of curiosity, I tried geom_prog(16) which gave me 28 which is 4 + 8 + 16. I was hoping for 37 (9 + 12 + 16 with factor 4/3). \$\endgroup\$ Apr 1, 2016 at 23:54
  • 1
    \$\begingroup\$ I have rolled back the last slew of edits, because they invalidated the given answer. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Vogel612
    Apr 2, 2016 at 0:06
  • 1
    \$\begingroup\$ Also, after posting please don't make any edits to your code. It can mess up review in progress as well as invalidate answers. \$\endgroup\$
    – user95591
    Apr 2, 2016 at 0:09
  • \$\begingroup\$ @EasterlyIrk, Vogel612 already mentioned this \$\endgroup\$
    – Valkyrie
    Apr 2, 2016 at 0:23
  • \$\begingroup\$ @Inori not even if you have answers. Just avoid editing at all. \$\endgroup\$
    – user95591
    Apr 2, 2016 at 0:53

1 Answer 1

5
\$\begingroup\$

No threading, please!!

First of all, get rid of the threads all-together. That should speed things up: Python threads are (sort-of) fine when things are blocking on IO, but in this case everything is CPU-based, and that means the GIL (global interpreter lock) makes sure that only one thread is running.

Also, the following code is a bit curious:

for s in xrange(int(n/4),int(n*0.8)+1):
    t=Thread(target=calc,args=(s,n,g))
    t.start()
    t.join()

I know that threading is a bit of a problem anyway here, but I would just like to comment on this specifically: by writing t.join() you are waiting on the thread to finish before starting the next iteration. This gets read of the threading all together, as there will only be two threads alive at a given time: 1 worker thread, and the main thread waiting on the worker to die.

I'd suggest writing it as:

threads = []
for s in iterable:
    t = Thread(...)
    threads.append(t)
    t.start()

for t in threads:
    t.join()

Naming and describing

Ok, with threading out of the way, I'm having a difficult time finding what the application is supposed to do.

It does something with an n, and each worker with an s and an n. What are those? The code could be a lot clearer in this regard.

Anyway, let us clean things up a bit first, and maybe I can find a pattern to help you improve the algorithm.

Performance

Checking for integer-valued lists.

Let's start looking at int_check.

def int_check(l):
    for i in l:
        if i-int(i)!=0: return False
    return True

You're checking if a number is integral by doing a lengthy calculation. Why not just

if i.is_integer(): return False

? Available since Python 2.6. https://docs.python.org/2/library/stdtypes.html#float.is_integer

Also, looping is expensive! Suggestion, use a comprehension together with the all.

def int_check(l):
    return all(i.is_integer() for i in l)

You should also name it better:

def is_integer_list(l):
    return all(i.is_integer() for i in l)

Useless duplication of lists

Let's look at the following code:

def check(obj):
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None))) and len(obj)>2 and int_check(obj)

First of all, let us do some short-circuiting. You're doing a lot of logic to see if it is a nice geometric progression, and after all the hard work, you check some very easy conditions. Turn that around!

def check(obj):
    if len(obj) <= 2 or not int_check(obj):
        return False
    cpy0,cpy1=tee(obj)
    iter0,iter1=tee(float(x)/y for x,y in izip(cpy0,islice(cpy1,1,None)))
    return all(x==y for x,y in izip(iter0,islice(iter1,1,None)))

I'm doubtful of you using tee for this. But I don't see a better builtin for it either. But I see a lot of logic here which I'd like to separate a bit more:

def steps(iterable):  # Needs better name, please help me!
    iterator = iter(iterable)  # Cast iterable to iterator.
    cur = next(iterator)
    for val in iterator:
        yield cur, val
        cur = val

A quick test to see that it does what we want.

>>> list(steps(range(10)))
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)]

Using that, we get

def check(obj):
    if len(obj) <= 2 or not int_check(obj):
        return False
    ratios = (float(x)/y for x, y in steps(obj))
    return all(x == y for x, y in steps(ratios))

Don't know if it's faster, but at least it is more readable! And I expect faster. But the main gain might be in the next section

The main loop

Your code was written as

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.put(takewhile(lambda i: i<=n,t))

Since I want to get rid of the threading, I'll assume q is a list instead of a queue.

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            q.append(takewhile(lambda i: i<=n,t))

(In reality I'd rather yield the results instead of adding to a queue. Anyhow, I'm shelving that for now)

takewhile vs slicing.

In the q.put you write takewhile. By the while loop above, you already know that will be all but the last value.

So, write

q.append(t[:-1])

Or, even

t.pop()
q.append(t)

That should be faster, because now the lambda i: i <= n doesn't have to be executed anymore.

Useless recalculation

Having written the above loop now as

def calc(s,n,q):
    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*((0.0+r)/100)])

        if check(t):
            t.pop()
            q.append(t)

We can turn our focus to the expression t.extend(...) above:

    for r in xrange(125,n*100+1,5):
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*((0.0+r)/100)])

Now in each iteration of the while loop, (0.0+r)/100 gets recalculated. Why not

    for r in xrange(125, n*100+1,5):
        r_ = float(r) / 100
        t=[s]
        while t[-1]<=n:
            t.extend([t[-1]*r_)

Incorrect algorithm

The worst part, I think, is that your code works by trying different ratios, and will miss some geometric sequences.

For instance, the sequence

81, 90, 100  # r == 100.0 / 90.0 == 90.0 / 81.0 (approx 1.1111111)

While your code will only try 1.25, 1.30, 1.35, ... .

Now, maybe there is some high-level mathematical proof that the solution will always involve a ratio which can be expressed as (125 + 5*k)/100, but I don't think so.

I would suggest turning the problem up-side-down. The following is an O(n^2 * log(n)) suggestion (estimated, but I think correct. Maybe even O(n^2)).

for x1 in xrange(1, n):
    for x2 in xrange(x1, n):
        # Using that
        #     x1 == a
        #     x2 == a * r
        # we get that
        #     r == x2 / x1
        ratio = float(x2) / x1
        # Continue as before, starting from t = [x1, x2]

Another point of incorrectness

In check, you check that the length is > 2, but then you filter on <=n. This should be the other way around.

A tiny suggestion.

Floating point arithmetic is challenging for problems like these. Maybe look into the fractions module?

from fractions import Fraction

...
ratio = Fraction(x2, x1)
...

Now, Fraction does not have an is_integer, but you can do the following:

>>> Fraction(5, 1).denominator == 1
True

Hope that all helps.

Corner cases

As an addendum, here are some cases your code flagged incorrectly:

>>> geom_prog(16)
28.0  # 4 + 8 + 16

but it should be at least 37: 9 + 12 + 16.

>>> geom_prog(100)
244.0  # 64 + 80 + 100

but it should be at least 271: 81 + 90 + 100 (maybe even more, but doubt it).

\$\endgroup\$
3
  • \$\begingroup\$ FYI: My review was based on an earlier revision. Most still holds, though, except for the part about when the length-check occurs. \$\endgroup\$ Apr 1, 2016 at 23:57
  • \$\begingroup\$ PEP 8 specifically warns against using l as a variable name because it is so similar to 1. You didn't comment on that in int_check(). One more thing: your solution for that function uses a generator expression, not a comprehension. \$\endgroup\$
    – zondo
    Apr 1, 2016 at 23:59
  • \$\begingroup\$ excellent tips. And yes, I realized that the algorithm in the previous versions was off, which I fixed. As an addition, type juggling via (0.0+r)/100 is faster than casting with float(). For variable names, r is the ratio in use, and n is the maximum number (which I suppose I could replace with m) \$\endgroup\$
    – Valkyrie
    Apr 2, 2016 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.