[Tutor] How inefficient is this code?

[Joe Cortes]

Welcome to the wonderful world of generators!

Looking at your code, you'll notice two things. First, you're
iterating over all the numbers twice: once to calculate them, and then
another time to actually do the sum. What's worse, at any given point
in time, you're only really using fibs[-1] and fibs[-2], and yet
you're still building this huge list with all the numbers. This is bad
in terms of memory efficiency. Luckily, it's such a common problem
that Python offers a really nice, really Pythonic solution. You can
define the following function:

def fib(top):
    first = 1 # As an aside, consider starting the sequence from 0, 1.
    next = 2
    yield first
    while next < top:
         yield next
         # For kicks, try rewriting the following three lines as a
tuple assignment.
         new_next = next + first
         first = next
         next = new_next

Now, how do you use this? This being Python, there is a super simple
way to do this:

sum = 0
for num in fib(4000000):
     if num % 2 == 0:
            sum += num
print sum


So, what's going on here? fib is mostly straightforward, but that
yield keyword might look new.
Here's the deal: when you have a function that uses the yield keyword,
that function becomes usable in the context of a for loop. Every time
it hits a yield it will, well, yield that value out to the for loop.
At the end of an iteration, control will be handed back to the
function, which will do its magic, and yield another value. Again, the
value will be sent out to the for loop, in this case as the "num"
variable, for use in that iteration.
When the function hits a return (or reaches the end of its body), the
for loop ends.

This is called a generator function, and is a really nice way to
simplify and optimize your loops.

You can read more about generators here: https://wiki.python.org/moin/Generators


On Wed, May 7, 2014 at 7:27 PM, C Smith <illusiontechniques at gmail.com> wrote:
> A topic came up on slashdot concerning "intermediate" programming,
> where the poster expressed the feeling that the easy stuff is too easy
> and the hard stuff is too hard.
>
> Someone did point out that 'intermediate' programming would still
> involve actually selling code or at least some professional
> experience, so this would probably fall into the category of 'novice'.
>
> I feel similarly right now and the cs 101 classes from udacity or
> coursera or the opencourseware stuff are very easy and boring. I tried
> the class "design of computer programs" on udacity and made it about
> halfway before being overwhelmed. The class involved making an api for
> a regex-like function to parse text (if I am communicating that
> correctly, it was sort of rewriting regex functionality in Python
> terms), and it seemed to go over a very definite cliff in terms of
> difficulty. Could someone provide a concise example of decorator use?
>
> Someone suggested projecteuler.net and I started blazing through
> things I had done before, when I realized this would be a good time to
> start more efficient practices instead of code that just happens to
> work and may be very inefficient.
>
> #sum all even fib seq integers under 4 million
> fibs = [1,2]
> sum = 0
> while fibs[-1] < 4000000:
>     nexty = fibs[-1] + fibs[-2]
>     fibs.append(nexty)
>
> for xer in fibs:
>     if xer%2 == 0:
>         sum += xer
> print sum
>
> This gets the correct solution, but what would be ways to improve
> speed or use more complicated parts of Python to do the same thing.
> Thanks in advance
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> https://mail.python.org/mailman/listinfo/tutor