Help Pls!!!How to make this code efficient?

A forum for general discussion of the Python programming language.

Help Pls!!!How to make this code efficient?

Postby KillerCode » Sat Oct 26, 2013 9:48 am

Here is my code.This is a solution for one of my sums.But the issue is the running time of this code.

Code: Select all
def o(s):
    l=len(s)
    return len(set([a+b+c for a in s for b in s for c in s]))==l*(l+1)*(l+2)//6

M=int(input())
N=3**M
i=1
s=M*[i]
while i:
    if s[i]-N:
        s[i]=s[i]+1
        if o(s[:i+1]):
            if i<M-1:
                i=i+1
                s[i]=s[i-1]
            else:
                N=s[-1]
    else:
        i=i-1
print(N)



1<input<12

When I give inputs such as 2,3,4, the running time is ok.But when we use inputs like 6,7 it is taking too much time.So how can I improve this?
Last edited by Mekire on Sat Oct 26, 2013 10:22 am, edited 1 time in total.
Reason: Locked. Fixed indentation. Please describe the goal.
KillerCode
 
Posts: 3
Joined: Sat Oct 26, 2013 9:32 am

Re: Help Pls!!!How to make this code efficient?

Postby metulburr » Sat Oct 26, 2013 10:10 am

i have no idea what your code does. I also see code that looks just plain old odd to me:
Code: Select all
        return len(set([a+b+c
                        for a in s for b in s for c in s])
                   )==l*(l+1)*(l+2)//6

Your code is so convoluted, i am not even going to trry to make sense of it. The fact that you put unmeaningful variable names makes it that much harder.

However, have you made a counter for your while loop and seen how many loops it goes for each number?
for my computer:
for 4:
it loops 200+ times

for 5:
it loops 5000+ times

for 6:
it loops 211,611 times

for 7:
i stopped it at 4+ million loops, as i figured i am not going to wait for the pattern to end what sure is awhile.

I would bet its safe to assume if you trace this back to its source problem that you would find the culprit
New Users, Read This
OS Ubuntu 14.04, Arch Linux, Gentoo, Windows 7/8
https://github.com/metulburr
steam
User avatar
metulburr
 
Posts: 1501
Joined: Thu Feb 07, 2013 4:47 pm
Location: Elmira, NY

Re: Help Pls!!!How to make this code efficient?

Postby Mekire » Sat Oct 26, 2013 10:16 am

Would you mind explaining what the program is supposed to do? Explain your end goal; not the method you have chosen.

-Mek
User avatar
Mekire
 
Posts: 1012
Joined: Thu Feb 07, 2013 11:33 pm
Location: Amakusa, Japan

Re: Help Pls!!!How to make this code efficient?

Postby stranac » Sat Oct 26, 2013 11:24 am

Looks like he's trying to brute-force a project euler problem(or something similar).
That's not likely to work.
Friendship is magic!

R.I.P. Tracy M. You will be missed.
User avatar
stranac
 
Posts: 1209
Joined: Thu Feb 07, 2013 3:42 pm

Re: Help Pls!!!How to make this code efficient?

Postby KillerCode » Sat Oct 26, 2013 11:42 am

Here is how it works.


For example, consider the function o. It takes a collection of numbers, s (with length l), iterates over all triples a, b, c of three elements from s (with repetition), counts the number of distinct sums a + b + c, and returns True if the number of distinct sums is equal to (l+2)-choose-3.

So for example, if you call o([2, 3, 4]) then the set of distinct sums will be

{2+2+2 = 6, 2+2+3 = 7, 2+2+4 = 8, 2+3+4 = 9, 2+4+4 = 10, 3+4+4 = 11, 4+4+4 = 12}

which has length 7, but (l+2)-choose-3 is 10, so o([2, 3, 4]) returns False.

So can you help me now?
KillerCode
 
Posts: 3
Joined: Sat Oct 26, 2013 9:32 am

Re: Help Pls!!!How to make this code efficient?

Postby Mekire » Sat Oct 26, 2013 12:04 pm

You still seem to be describing your chosen implementation. What exactly is the original problem?

-Mek
User avatar
Mekire
 
Posts: 1012
Joined: Thu Feb 07, 2013 11:33 pm
Location: Amakusa, Japan

Re: Help Pls!!!How to make this code efficient?

Postby hrs » Sat Oct 26, 2013 2:01 pm

I don't get what (l+2)-choose-3 means, but you can do something along these lines
Code: Select all
>>> import itertools
>>> my_list = [2,3,4,5,6,7,8,9,10,12]
>>> distinct_sums = set(sum(perm) for perm in itertools.permutations(my_list, 5))
>>> len(distinct_sums), distinct_sums
(27, set([20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46]))
hrs
 
Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

Re: Help Pls!!!How to make this code efficient?

Postby hrs » Sat Oct 26, 2013 2:08 pm

Except that itertools.permutations lacks repetition. Instead you could use itertools.product(my_list, repeat=3).
hrs
 
Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

Re: Help Pls!!!How to make this code efficient?

Postby Mekire » Sat Oct 26, 2013 2:16 pm

Code: Select all
itertools.combinations_with_replacement(s,3)

-Mek
User avatar
Mekire
 
Posts: 1012
Joined: Thu Feb 07, 2013 11:33 pm
Location: Amakusa, Japan


Return to General Discussions

Who is online

Users browsing this forum: Bing [Bot] and 3 guests