Returning elements in a list also found in another list I'm trying to write a short function which takes a list (a) and returns another list which only contains the elements (x) such that -x is also in a. I've done that, and it works, but it runs really slowly. I know why it does, and I know the second for loop is unnecessary, but I don't know how to fix it without breaking the function.

def negated(a):
    mark = set()
    add_mark = mark.add
    b = []
    c = []
    for i in a:
        if i not in mark and not add_mark(i):
            b.append(i)
    for i in b:
        if -i in b:
            c.append(i)
    return c
First, let's get this out of the way:

The reason the OP version is slow is that, to decide whether to insert elements into c, it checks each one of them against b—a list, rather than a set. That means it's quadratic when it could be linear.

You could fix that by making another set, call it mark2 = set(b), then using if -i in mark2 instead of if -i in b.

That means your code is no longer quadratic, it's linear. Which is probably all you cared about.

However, it's looping twice as much as it needs to, and it's doing all of the looping in Python rather than finding ways to push it into C. That add_mark = mark.add optimization implies that you might be looking for more such tricks, and you should be able to cut the time to about a third.

But just fixing that isn't good enough once you get the community going, so a number of variations have been suggested both here and on a previous SO question. Which one is actually 
fastest?



Instead of just guessing, let's actually write and test some implementations and see. Of course for real answers we need your real data, but I'll make up some data, and that should be enough to show you how to do it yourself.

# my answer on the earlier question, and my comment above
def negated_0(a):
    a = set(a)
    return [i for i in a if -i in a]

# Peter DeGlopper's comment, and hcwhsa's on the earlier question
def negated_1(a):
    s = set(a)
    return [i for i in a if -i in s]

# one suggestion I made on the earlier question
def negated_2(a):
    return set(a) &amp; {-i for i in a}

# another suggestion I thought my be a little faster but not worth it
def negated_3(a):
    return {-i for i in a}.intersection(a)

# a possibly-improved version of #3 that I just thought of
def negated_4(a):
    a = set(a)
    return a &amp; {-i for i in a}

# kojiro's posted answer
def negated_kojiro(a):
    '''Take a list a and returns another list which only contains the elements x such that -x is also in a'''
    neg, pos = set(), set()
    for i in a:
        if i &lt; 0:
            neg.add(-1*i)
        else:
            pos.add(i)
    return [i for i in a if abs(i) in pos &amp; neg]

import timeit
import random

a = [random.randint(-10000,10000) for _ in range(1000)]
for func in dir(sys.modules('__main__')):
    if func.startswith('negated_'):
        f = getattr(sys.modules('__main__'), func)
        print('{}: {}'.format(func, timeit.timeit(lambda: f(a), number=10000))


Here's the output on one laptop with Apple's Python 2.7.2:

negated_0: 1.50614500046
negated_1: 1.45001101494
negated_2: 1.79172492027
negated_3: 1.29876303673
negated_4: 1.92844605446
negated_kojiro: 84.5585548878


… and with a default-configured local build of Python 3.4 trunk:

negated_0: 1.5246370710083283
negated_1: 1.420855167991249
negated_2: 1.7558801580162253
negated_3: 1.297387560014613
negated_4: 1.8665565319824964
negated_kojiro: 72.18082603899529


… and with PyPy 2.1.0/2.7.3:

negated_0: 0.595048904419
negated_1: 0.405268907547
negated_2: 0.815263032913
negated_3: 0.878368139267
negated_4: 0.910092115402
negated_kojiro: 49.3969540596




Comparing the fixed version of the OP's implementation:

negated_op: 4.76454496384
negated_op: 3.3227077620103955
negated_op: 0.87509393692


(The original, unfixed version took over 79 seconds before I killed it in 2.7.2.)

We've improved it by 3x in CPython 2.7.2, but only 2x in the other implementations. Not quite what I'd hoped, but not bad.



It looks like negated_3 actually is a decent-sized win over the obvious implementation, but nothing else is. (And #4 actually makes things worse.)

Wrapping #2-#4 in list(…) so they return the same type as the others shows virtually no difference:

negated_0: 1.54194092751
negated_1: 1.44428801537
negated_2: 1.78255009651
negated_3: 1.29559803009
negated_4: 1.90534591675




Fixing the most serious problem with kojiro's answer, by evaluating pos &amp; neg once outside the listcomp instead of for each element, gives me:

negated_kojiro_fix: 2.11841907501
negated_kojiro_fix: 3.84713697433
negated_kojiro_1: 0.739408969879


So, it's still significantly slower than negated_1 (which, like it, preserves duplicates and order) everywhere. Why?

It could be that it's doing twice as much setup work and not getting a comparable amount of savings in the actual comprehension. It may be simpler work, but still, adding O(N) loops in Python to speed up an O(N) list comprehension might be costly.

But there's also the fact that the listcomp filter is more complicated: abs(i) in mark instead of the -i in mark. So, if we could make it even simpler, would that make the listcomp even faster? Just keep the negated set around, and do i in mark. Which means you can replace the listcomp with a filter by using mark.__contains__ as the argument:

def negated_3b(a):
    mark = {-i for i in a}
    return filter(mark.__contains__, a)


(For Python 3, you have to make that list(filter(…)) of course, or it'll return almost instantly, having built an iterable but not iterated it.)

The results with the same three Python implementations are:

negated_3b: 1.39607014656
negated_3b: 1.8215457699843682
negated_3b: 0.51006603241


So… it beats all of the other order-and-dups-preserving methods in 2.x, CPython or PyPy, but not the set-returning negated_3 (which is obvious, when you think about it).

However, it's slower in 3.x. Maybe that's just because of the necessity of calling list? If you don't actually need a list, let's see how long it takes to iterate it, by just feeding the iterator into deque(maxlen=0):

negated_3b: 1.6808519120211713


Better, but still not as good as negated_1 in Python 3. Maybe it's just that 3.x's filter hasn't been improved since the original version was written as 2.x's itertools.ifilter, but listcomps have been improved multiple times over the years?



So, conclusions—if your data are very similar to mine (which is very unlikely!):


Unless this is such a bottleneck in your code that a few microseconds one way or the other actually make a difference, use whichever one is most readable.
If you don't need to preserve order and duplicates, use negated_3.
If you're using Python 2.x, use negated_3b.
Otherwise, use negated_1.