Generating 3 combinations in Python

Question

I have been experimenting around with generating all the n-combinations of an array. This code quickly generates all \$\text{k-combinations}\$ of a given array. I am testing my own implementation because of some restrictions in coding competitions (also, knowing the basics never hurts).

"""
Generates 3-combinations of an array.

A B C D E F G H
^ ^ ^
i j k

A B C D E F G H
^ ^   ^
i j   k

A B C D E F G H
^   ^   ^
i   j   k
"""
from itertools import combinations
import time

def combinations_3(ary):
    l = len(ary)
    for i in xrange(l-2):
        for j in xrange(i+1, l-1):
            for k in xrange(j+1, l):
                yield (ary[i], ary[j], ary[k])


start = time.time()      
for combination in combinations_3([1, 2, 3, 4]):
    print combination
print time.time() - start

print("===========Library Implementation============")
start = time.time()
for combination in combinations([1, 2, 3, 4], 3):
    print combination
print time.time() -start

Output

(1, 2, 3)                                                                                                                                                                                                                  
(1, 2, 4)                                                                                                                                                                                                                  
(1, 3, 4)                                                                                                                                                                                                                  
(2, 3, 4)                                                                                                                                                                                                                  
0.00043797492981                                                                                                                                                                                                           
===========Library Implementation============                                                                                                                                                                              
(1, 2, 3)                                                                                                                                                                                                                  
(1, 2, 4)                                                                                                                                                                                                                  
(1, 3, 4)                                                                                                                                                                                                                  
(2, 3, 4)                                                                                                                                                                                                                  
6.19888305664e-05

It seems that my implementation is a lot slower than the library code. How can I improve performance of my code.

Answer 1

You probably want to use timeit module with similar setup:

run.py

from itertools import combinations


def combinations_3(ary):
    l = len(ary)
    for i in xrange(l-2):
        for j in xrange(i+1, l-1):
            for k in xrange(j+1, l):
                yield (ary[i], ary[j], ary[k])


def _test(generator):
    for combination in generator:
        #: To meger time of sequence generation we should ommit IO operations.
        pass


def test_lib(lenght=10000):
    _test(combinations(list(range(1, lenght)), 3))


def test_self_written(lenght=10000):
    _test(combinations_3(list(range(1, lenght))))

test.py

import timeit

#: Print title
print('                library time   self written time')

#: Counter of sequence number.
for i in list(range(10, 100, 10)):
    #: Meger execution time for self written combinations implementation.
    self_written = timeit.Timer(
        #: Tested expression.
        'test_lib({})'.format(i),
        #: Test setup, here we just import tested function.
        'from run import test_self_written as test_lib'
    ).timeit(1000)  #: And here we just set number of testing iterations.

    lib = timeit.Timer(
        'test_lib({})'.format(i),
        'from run import test_lib'
    ).timeit(1000)

    #: Print output in format "<number of elements>: library time, self written time"
    print('{:03} elements: {:10.6f}     {:10.6f}'.format(i, lib, self_written))

And here is my output:

$ python2 test.py 
                library time   self written time
010 elements:   0.007060       0.030495
020 elements:   0.058317       0.239376
030 elements:   0.211884       0.817189
040 elements:   0.522477       1.903142
050 elements:   1.047018       3.803112
060 elements:   1.969069       6.590189
070 elements:   2.960615      10.500072
080 elements:   4.468489      15.176092
090 elements:   6.402755      21.669669
$ python3 test.py 
                library time   self written time
010 elements:   0.009168       0.038298
020 elements:   0.058049       0.285885
030 elements:   0.208938       1.031432
040 elements:   0.523407       2.450311
050 elements:   1.048463       4.796328
060 elements:   1.828277       7.832434
070 elements:   2.970929      13.067557
080 elements:   4.481792      18.496334
090 elements:   6.353836      26.277946
$ pypy test.py 
                library time   self written time
010 elements:   0.011924       0.040272
020 elements:   0.056972       0.046638
030 elements:   0.185858       0.083793
040 elements:   0.456202       0.188640
050 elements:   0.913935       0.338211
060 elements:   1.588666       0.542124
070 elements:   2.537772       0.846942
080 elements:   3.816353       1.232982
090 elements:   5.471375       1.707760

And python versions

$ python2 -V && python3 -V && pypy -V
Python 2.7.6
Python 3.4.3
[PyPy 2.2.1 with GCC 4.8.2]

As you can see, pypy is much faster than cpython implementation.

Actually, if you are using cpython you do not really want to reinvent standard library functions because they are pretty nice optimized by c compiler and you code will be interpreted instead of compiling. In case of pypy you probably want to make some research, because JIT interpreter have a lot of different corner cases.

Answer 2

I was able to shave off 20 % of time in outoftime's test by avoiding the indexed lookups in (ary[i], ary[j], ary[k]) and doing this instead:

def combinations_3(ary):
    enumerated = list(enumerate(ary))
    for i, x in enumerated[:-2]:
        for j, y in enumerated[i+1:-1]:
            for z in ary[j+1:]:
                yield (x, y, z)

Precomputing the slice of the innermost loop for each j takes another 10 % off:

def combinations_3(ary):
    enumerated = [(i, value, ary[i+1:]) for i, value in enumerate(ary)]
    for i, x, _ in enumerated[:-2]:
        for _, y, tail in enumerated[i+1:-1]:
            for z in tail:
                yield (x, y, z)

It is worth noting that the first version requires O(n) additional space for the list slices, and the second version ups the requirement to O(n²), where n is the size of ary.