Big O (for all problems)

For questions about problems on the Project Euler web site. No spoilers. Please include the question number in the subject line of your post.

Big O (for all problems)

Postby Explorador » Sun Aug 31, 2014 11:33 am

Hi again,

We have talked several times about Big O, but it stills difficult sometimes to find a suitable function for what we are looking for. I thought about using this post for puting the codes we need to improve with a Big O, and the other users can help us to make them better. Looking at our and the rest of users' problems we can really improve our skills at using Big O.

I will start puting the code I am working at now (Problem 12). Notice that you should not continue reading if you have not completed this problem (in order to avoid code-spoilers):

Code: Select all
triangulos = []
for x in xrange(1,9999):
   y = sum(i for i in xrange(1,x+1))
   triangulos.append(y)
lista = []
factores = []
for x in triangulos:
   for i in xrange(1,x+1):
      if x%i == 0:
         factores.append(i)
   if len(factores) >= 500:
      result = x,factores
      del(factores)
      factores = []
      lista.append(result)
      del(result)
      break
   elif len(factores) < 500:
      del(factores)
      factores = []


I put the whole code because as a beginner I am at Big O, I do not really know where should I improve it.

According to other posts, I tried something like using sqrt(), and although it run really fast, it did not give me a suitable result. So I would be pleased if you can help me to "open my mind" to new ways of using Big O.

Thank you very much.
Explorador
 
Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

Re: Big O (for all problems)

Postby micseydel » Sun Aug 31, 2014 7:58 pm

I think it would be best if you refactored your code to use functions, and then put doc strings on those functions indicating their Big O and then we give you feedback from there. How does that sound?
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1356
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Big O (for all problems)

Postby Explorador » Sun Aug 31, 2014 9:13 pm

Alright.

Code: Select all
triangulos = []
def triangulos(z):
   for x in xrange(1,z): """O(x)"""
      y = sum(i for i in xrange(1,x+1)) """O(sum(1 until x)) < O(x**2)"""
      triangulos.append(y)
lista = []
factores = []


And now I have a problem, because if I put this:

Code: Select all
def getfactors(x):
   for i in xrange(1,x+1): """O(x)"""
      if x%i == 0:
         factores.append(i)


inside here:

Code: Select all
for x in triangulos:
   getfactors(x)
   if len(factores) >= 500:
      result = x,factores
      del(factores)
      factores = []
      lista.append(result)
      del(result)
      break
   elif len(factores) < 500:
      del(factores)
      factores = []


it gives me this error:

Traceback (most recent call last):
File "<pyshell#26>", line 1, in <module>
for x in triangulos:
TypeError: 'function' object is not iterable


But I also can't put it out of there. Otherwise, if I loop without adding-checking-deleting, the factores list would grow and grow.

So I see my first problem would be to make the suitable definitions, but also how to improve these Big O.
Explorador
 
Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

Re: Big O (for all problems)

Postby Kebap » Mon Sep 01, 2014 11:34 am

Explorador wrote:
Code: Select all
triangulos = []
def triangulos(z):

See how triangulos is first just an empty list, but then a function is defined with the same name? This error has nothing to do with big O. Give them a different name. :mrgreen:
Learn: How To Ask Questions The Smart Way
Join the #python-forum IRC channel on irc.freenode.net and chat with uns directly!
Kebap
 
Posts: 396
Joined: Thu Apr 04, 2013 1:17 pm
Location: Germany, Europe

Re: Big O (for all problems)

Postby Explorador » Mon Sep 01, 2014 2:29 pm

Well, it is true, sorry. But I did it just because micseydel ask me to def them. But you can check at my first post that my problem is with Big O :P I think we can assume that def is a minor problem.

So I would really thank you if you can help improving the Big O(s) of the first code I posted :)

Edit: The first code I copied works 100% perfect for smaller numbers (as 100 instead of 500). So according to what I learnt until now, what we should do is to improve the Big O in order to make it faster.
Explorador
 
Posts: 14
Joined: Mon Aug 25, 2014 9:32 am
Location: Spain

Re: Big O (for all problems)

Postby micseydel » Mon Sep 01, 2014 10:53 pm

I think it'd be easier for you to understand Big O if you're able to analyze your own code, which will be easier if you can make your code more readable, namely with functions. But you don't want to use global variables, which defeats the purpose of trying to clean up code. If you're not familiar with functions, you should probably try a tutorial since you'll find the effort will pay off quickly and help a great deal in the future.
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1356
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA


Return to Project Euler

Who is online

Users browsing this forum: No registered users and 1 guest