how to rewrite this loop in a more efficient way in python

Question

I have a loop of the following type:

a = range(10)
b = [something]
for i in range(len(a)-1):
    b.append(someFunction(b[-1], a[i], a[i+1]))

However the for-loop is killing a lot of performance. I have try to write a windows generator to give me 2 elements everything time but it still require explicit for-loop in the end. Is there a way to make this shorter and more efficient in a pythonic way?

Thanks

edit: I forgot the element in b.. sorry guys. However the solution to my previous problem is very helpful in other problem I have too. Thanks.

Answer 1

For your initially stated problem of mapping a function over pairs of an input sequence the following will work, and is about as efficient as it gets while staying in Python land.

from itertools import tee

a = range(10)
a1, a2 = tee(a)
a2.next()
b = map(someFunction, a1, a2)

As for the expanded problem where you need to access the result of the previous iteration - this kind of inner state is present in the functional concept unfold. But Python doesn't include an unfold construct, and for a good reason for loops are more readable in this case and most likely faster too. As for making it more Pythonic, I suggest lifting the pairwise iteration out to a function and create an explicit loop variable.

def pairwise(seq):
    a, b = tee(seq)
    b.next()
    return izip(a, b)

def unfold_over_pairwise(unfolder, seq, initial):
    state = initial
    for cur_item, next_item in pairwise(seq):
        state = unfolder(state, cur_item, next_item)
        yield state

b = [something]
b.extend(unfold_over_pairwise(someFunction, a, initial=b[-1]))

If the looping overhead really is a problem, then someFunction must be something really simple. In that case it probably is best to write the whole loop in a faster language, such as C.

Answer 2

Consider this

def make_b( a, seed ):
    yield seed
    for a,b in zip( a[:-1], a[1:] ):
        seed= someFunction( seed, a, b )
        yield seed

Which lets you do this

a = xrange(10)
b= list(make_b(a,something))

Note that you can often use this:

b = make_b(a)

Instead of actually creating b as a list. b as a generator function saves you considerable storage (and some time) because you may not really need a list object in the first place. Often, you only need something iterable.

Similarly for a. It does not have to be a list, merely something iterable -- like a generator function with a yield statement.

Answer 3

Some loop or other will always be around, but one possibility that might reduce overhead is:

import itertools

def generate(a, item):
  a1, a2 = itertools.tee(a)
  next(a2)
  for x1, x2 in itertools.izip(a1, a2):
    item = someFunction(item, x1, x2)
    yield item

to be used as:

b.extend(generate(a, b[-1]))

Answer 4

Try something like this:

a = range(10)    
b = [something] 

s = len(b)
b+= [0] * (len(a) - 1)
[ b.__setitem__(i, someFunction(b[i-1], a[i-s], a[i-s+1])) for i in range(s, len(b))]

Also:

• using functions from itertools should be useful also (earlier posts)
• maybe you can rewrite someFunction and use map instead of list comprehension