Why is the ThreeSum "map" so slow?

Delivery of the second answer. From various comments it seems that you are primarily concerned about why this particular O (n ** 3) algorithm is slow when porting from java. Let the dive in.

def count(a):
       """ThreeSum: Given N distinct integers, how many triples sum to exactly zero?"""
       N = len(a)
       cnt = 0
       for i in range(N):
         for j in range(i+1, N):
           for k in range(j+1, N):
             if sum([a[i], a[j], a[k]]) == 0:
               cnt += 1
       return cnt

      

        
        
        
      

    

One problem with main that immediately pops up is that you are doing something that your Java code almost certainly doesn't: materializing a 3-item list just lets you add three numbers!

if sum([a[i], a[j], a[k]]) == 0:

      

        
        
        
      

    

Ugh! Just write that

if a[i] + a[j] + a[k] == 0:

      

        
        
        
      

    

Some benchmarking shows that you are adding 50% + overhead just by doing it. Clap.

Another problem is that you are using indexing, in which you have to use iteration. In python, try to avoid writing code like this:

for i in range(len(some_list)):
    do_something(some_list[i])

      

        
        
        
      

    

And instead, just write:

for x in some_list:
    do_something(x)

      

        
        
        
      

    

And if you explicitly need the index you are at (as you do in your code) use enumerate

:

for i,x in enumerate(some_list):
    #etc

      

        
        
        
      

    

This is, in general, a stylish thing (although it goes deeper than with duck typing and iterator protocol), but it is also a matter of performance. To see the value a[i]

, this call is converted to a.__getitem__(i)

, then python has to dynamically resolve the method lookup __getitem__

, call it and return the value. Everytime. It's not a crazy amount of overhead - at least on built-in types - but it adds up if you do it a lot in a loop. On the other hand, referring to it a

as iterable wraps around a lot of this overhead.

So, with this change in mind, you can rewrite your function again:

def count_enumerate(a):
    cnt = 0
    for i, x in enumerate(a):
        for j, y in enumerate(a[i+1:], i+1):
            for z in a[j+1:]:
                if x + y + z == 0:
                    cnt += 1
    return cnt

      

        
        
        
      

    

Let's take a look at some timings:

%timeit count(range(-100,100))
1 loops, best of 3: 394 ms per loop

%timeit count_fixed(range(-100,100)) #just fixing your sum() line
10 loops, best of 3: 158 ms per loop

%timeit count_enumerate(range(-100,100))
10 loops, best of 3: 88.9 ms per loop

      

        
        
        
      

    

And it's about as fast as it gets. You can shave off a percentage or so by wrapping everything in understanding instead of doing cnt += 1

, but this is pretty minor.

I've played itertools

around with several implementations , but I really can't get them to run faster than this explicit version of the loop. This makes sense if you think about it - for each iteration, the version has itertools.combinations

to repeat which one all three variables belong to, whereas explicit loops become "spoofing" and relaying variables in outer loops much less frequently.

Reality check time though: after all is said and done, you can still expect cPython to run this algorithm an order of magnitude slower than a modern JVM. There is too much abstraction built into python that gets in the way quickly. If you want speed (and you can't fix your algorithm - see my other answer), either use something like numpy

to spend all your time in C or use a different python implementation.

postscript: pypy

For fun, I ran count_fixed

into a list of 1000 items, both in cPython and pypy.

CPython:

In [81]: timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
Out[81]: 19.230753898620605

      

        
        
        
      

    

PyPy:

>>>> timeit.timeit('count_fixed(range(-500,500))', setup='from __main__ import count_fixed', number = 1)
0.6961538791656494

      

        
        
        
      

    

Speedy!

I can add some java testing later to compare :-)