7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Python is open source; have you considered looking at the library code to see what the differences are (it's written in C, for a start)? \$\endgroup\$ – jonrsharpe Oct 13 '15 at 7:30
  • \$\begingroup\$ Your only hope to make it faster is to write it in C, like stdlib, or Cythonize your code. \$\endgroup\$ – Davidmh Oct 13 '15 at 12:14
  • \$\begingroup\$ @Davidmh, fine, Then I think this code is fine as a quick hard coded way to write combinations. \$\endgroup\$ – CodeYogi Oct 13 '15 at 12:22
6
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ You do not really want to reinvent standard library functions because they are pretty nice optimized by c compiler -> Well said \$\endgroup\$ – bhathiya-perera Oct 13 '15 at 9:07
  • \$\begingroup\$ @JaDogg, reinventing and understanding is quite different things I think. In that manner you shouldn't write any sorting algorithm at all, right? because they are already implemented out there. \$\endgroup\$ – CodeYogi Oct 13 '15 at 9:31
  • \$\begingroup\$ In fact these approach are quite useful when your coding environment doesn't allow external libraries or your use case is quite restricted. \$\endgroup\$ – CodeYogi Oct 13 '15 at 9:32
  • \$\begingroup\$ I'd like to join discussion with title "std:: or not std::" but we are talking about python, not c++. \$\endgroup\$ – outoftime Oct 13 '15 at 9:36
  • 1
    \$\begingroup\$ I never wanted to emphasize on it. My bad if that point got highlighted. I wanted if I can improve performance any further. \$\endgroup\$ – CodeYogi Oct 13 '15 at 10:08
4
\$\begingroup\$

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(n2), where n is the size of ary.

\$\endgroup\$
  • \$\begingroup\$ Do these optimizations affects the Big-O complexity of the algorithm? \$\endgroup\$ – CodeYogi Oct 13 '15 at 16:48
  • \$\begingroup\$ @CodeYogi Space complexity increases from O(1) to O(n) and to O(n^2) in the second version. Time complexity remains O(n^3). \$\endgroup\$ – Janne Karila Oct 13 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.