itertools.islice compared to list slice

Question

I've been trying to apply an algorithm to reduce a python list into a smaller one based on a certain criteria. Due to the large volume of the original list, in the order of 100k elements, I tried to itertools for avoiding multiple memory allocations so I came up with this:

reducedVec = [ 'F' if sum( 1 for x in islice(vec, i, i+ratio) if x == 'F' ) 
                         > ratio / 3.0 else 'T'
                for i in xrange(0, len(vec), ratio) ]

Execution time for this takes a worryingly long time in the order of a few minutes, when vec has around 100k elements. When I tried instead:

reducedVec = [ 'F' if sum( 1 for x in vec[i:i+ratio] if x == 'F' ) 
                         > ratio / 3.0 else 'T'
                for i in xrange(0, len(vec), ratio) ]

in essence replace islice with a slice the execution is instantaneous.

Can you think of a plausible explanation for this? I would have thought that avoiding to repeatedly allocate a new list with a substantial number of elements, would actually save me a few computational cycles instead of crippling the whole execution.

Cheers, Themis

Answer 1

My guess would be that using islice() involves a Python function call for each element of vec, while the extended slice notation is understood by the parser and translates directly to CPython calls.

Answer 2

islice works with arbitrary iterables. To do this, rather than jumping straight to the nth element, it has to iterate over the first n-1, throwing them away, then yield the ones you want.

Check out the pure Python implementation from the itertools documentation:

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1))
    nexti = next(it)
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = next(it)

---

Speaking of the itertools documentation, if I was trying to do this operation, I'd probably use the grouper recipe. It won't actually save you any memory, but it could if you rewrote it to be lazier, which wouldn't be tough.

from __future__ import division

from itertools import izip_longest
def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

reducedVec = []
for chunk in grouper(ratio, vec):
    if sum(1 for x in chunk if x == 'F') > ratio / 3:
        reducedVec.append('F')
    else:
        reducedVec.append('T')

I like using grouper to abstract away the consecutive slices and find this code a lot easier to read than the original