faster than list.extend()

[Peter Otten]

Gabriel Genellina wrote:

> En Mon, 16 Nov 2009 19:30:27 -0300, Hyunchul Kim
> <hyunchul.mailing at gmail.com> escribió:
> 
>> I want to improve speed of following simple function.
>> Any suggestion?
>>
>> **********
>> def triple(inputlist):
>>   results = []
>>   for x in inputlist:
>>     results.extend([x,x,x])
>>   return results
>> **********
> 
> These are my best attempts:
> 
> def triple3(inputlist):
>         results = []
>         append = results.append
>         for x in inputlist:
>           append(x); append(x); append(x)
>         return results
> 
> def triple4(inputlist, _three=xrange(3)):
>        return [x for x in inputlist for _ in _three]
> 
> For a 400-items list, triple3 is 40% faster and triple4 25% faster than
> yours.

[I didn't see the original post]

If inputlist is actually a list or tuple the following should beat them all:

def triple_repeat(items):
    result = [None] * (3*len(items))
    result[::3] = result[1::3] = result[2::3] = items
    return result

For small n the generalization should still be quite competitive:

def n_repeat(items, n):
    items = tuple(items)
    result = [None]*(len(items) * n)
    for offset in range(n):
        result[offset::n] = items
    return result

Some measurements:

$ cat extend.py
from itertools import *

def triple_repeat(items):
    result = [None] * (3*len(items))
    result[::3] = result[1::3] = result[2::3] = items
    return result

def n_repeat(items, n):
    items = tuple(items)
    result = [None]*(len(items) * n)
    for offset in range(n):
        result[offset::n] = items
    return result

def t1(i):
    for x in i:
        yield x
        yield x
        yield x

def triple3(inputlist, list=list, chain_from_iterable=chain.from_iterable, izip=izip):
    return list(chain_from_iterable(izip(inputlist, inputlist, inputlist)))

data = range(1000)


$ python -m timeit -s 'from extend import triple_repeat, data'  'triple_repeat(data)'
10000 loops, best of 3: 52.4 usec per loop                                           
$ python -m timeit -s 'from extend import n_repeat, data'  'n_repeat(data, 3)'
10000 loops, best of 3: 60.7 usec per loop                                    
$ python -m timeit -s 'from extend import t1, data'  'list(t1(data))'
1000 loops, best of 3: 337 usec per loop
$ python -m timeit -s 'from extend import triple3, data'  'triple3(data)'
1000 loops, best of 3: 231 usec per loop

Peter