Fast python front list extending

Question

What is the fastest way to extend the front of an array in python? Lets say I've got 2 arrays: a and b. I want to make the fastest way of a = b+a (b should not change).

My small benchamarks:

test 1:

a,b = [],[]
for i in range(0,100000):
    a.append(i)
    b.append(i)

def f(a,b):
    for i in range(0,100):
        a=a+b

import cProfile
cProfile.run('f(a,b)')

time: ~12 s

test 2:

a,b = [],[]
for i in range(0,100000):
    a.append(i)
    b.append(i)

def f(a,b):
    for i in range(0,100):
        a[0:0] = b

import cProfile
cProfile.run('f(a,b)')

time: ~1.5s

test3:

a,b = [],[]
for i in range(0,100000):
    a.append(i)
    b.append(i)

lenb = len(b)
def f(a,b):
    for i in range(0,100):
        b.extend(a)
        # do something with b
        b = b[:lenb]

import cProfile
cProfile.run('f(a,b)')

time: ~0.4s

But i think It should be faster, because lists concatenation should be made as change of few underlying pointers. And the following code is the fastest one, but changes b, not a (SO IT IS NOT GOOD FOR OUR PURPOSE): test "WRONG":

a,b = [],[]
for i in range(0,100000):
    a.append(i)
    b.append(i)

def f(a,b):
    for i in range(0,100):
        b.extend(a)

import cProfile
cProfile.run('f(a,b)')

time: ~0.13s

So theoretically there should be a way to extend front of a in time of test "WRONG".

Answer 1

The absolute fastest way would be to use a collections.deque which is optimised for exactly this use, and has methods called .appendleft and .extendleft to make the code nice and readable - appendleft does exactly what it says on the tin (ie, it appends to the left of the deque), and extendleft does the equivalent of:

def extendleft(self, other)
    for item in other:
        self.appendleft(c)

so, a = b+a would be spelled:

a.extendleft(reversed(b))