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
we will be moving to python-forum.io on October 1 2016
more details here
User avatar
metulburr
 
Posts: 2228
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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

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: 1790
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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona

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
New Users, Read This
  • Use code tags when posting code.
  • Include any errors with your post (in code tags).
  • Describe your problem; not your chosen solution.
  • Make examples the minimum length to demonstrate your issue.
User avatar
Mekire
 
Posts: 1711
Joined: Thu Feb 07, 2013 11:33 pm
Location: Tucson, Arizona


Return to General Discussions

Who is online

Users browsing this forum: No registered users and 4 guests