Why Is This Slicing Code Faster Than More Procedural Code?

I have a Python function that takes a list and returns a generator yielding 2-tuples of each adjacent pair, e.g. >>> list(pairs([1, 2, 3, 4])) [(1, 2), (2, 3), (3, 4)] I'

Solution 1:

Lots of interesting discussion elsewhere in this thread. Basically, we started out comparing two versions of this function, which I'm going to describe with the following dumb names:

1. The "zip-py" version:

   defpairs(xs):
       for p inzip(xs[:-1], xs[1:]): 
           yield p
   

2. The "loopy" version:

   def pairs(xs):
       last = object()
       dummy = lastforx in xs:
           iflast is not dummy:
               yield last,xlast = x

So why does the loopy version turn out to be slower? Basically, I think it comes down to a couple things:

1. The loopy version explicitly does extra work: it compares two objects' identities (if last is not dummy: ...) on every pair-generating iteration of the inner loop.

   • @mambocab's edit shows that not doing this comparison does make the loopy version slightly faster, but doesn't fully close the gap.

2. The zippy version does more stuff in compiled C code that the loopy version does in Python code:

   • Combining two objects into a tuple. The loopy version does yield last,x, while in the zippy version the tuple p comes straight from zip, so it just does yield p.

   • Binding variable names to object: the loopy version does this twice in every loop, assigning x in the for loop and last=x. The zippy version does this just once, in the for loop.

3. Interestingly, there is one way in which the zippy version is actually doing more work: it uses twolistiterators, iter(xs[:-1]) and iter(xs[1:]), which get passed to zip. The loopy version only uses onelistiterator (for x in xs).

   • Creating a listiterator object (the output of iter([])) is likely a very highly optimized operation since Python programmers use it so frequently.
   • Iterating over list slices, xs[:-1] and xs[1:], is a very lightweight operation which adds almost no overhead compared to iterating over the whole list. Essentially, it just means moving the starting or ending point of the iterator, but not changing what happens on each iteration.

Solution 2:

This i the result for the iZip which is actually closer to your implementation. Looks like what you would expect. The zip version is creating the entire list in memory within the function so it is the fastest. The loop version just los through the list, so it is a little slower. The izipis the closest in resemblance to the code, but I am guessing there is some memory-management backend processes which increase the time of execution.

In [11]: %timeit pairsLoop([1,2,3,4,5])
1000000 loops, best of 3: 651 ns per loop

In [12]: %timeit pairsZip([1,2,3,4,5])
1000000 loops, best of 3: 637 ns per loop

In [13]: %timeit pairsIzip([1,2,3,4,5])
1000000 loops, best of 3: 655 ns per loop

The version of code is shown below as requested:

from itertools import izip


defpairsIzip(xs):
    for p in izip(xs[:-1], xs[1:]): 
        yield p

defpairsZip(xs):
    for p inzip(xs[:-1], xs[1:]): 
        yield p

defpairsLoop(xs):
    last = object()
    dummy = last
    for x in xs:
        if last isnot dummy:
            yield last,x
        last = x

Solution 3:

I suspect the main reason that the second version is slower is because it does a comparison operation for every single pair that it yields:

# pair-generating loopforx in xs:
    iflast is not dummy:
       yield last,xlast = x

The first version does not do anything but spit out values. With the loop variables renamed, it's equivalent to this:

# pair-generating loopforlast,x in zip(xs[:-1], xs[1:]):
    yield last,x

It's not especially pretty or Pythonic, but you could write a procedural version without a comparison in the inner loop. How fast does this one run?

defpairs(xs):
    for ii inrange(1,len(xs)):
        yield xs[ii-1], xs[ii]