2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ How big are your lists? How fast is this code? Can you provide some more details? \$\endgroup\$ – templatetypedef Oct 9 '13 at 23:29
  • 2
    \$\begingroup\$ Add the whole of a to your set, then do all of your membership checks against that. Set lookups are O(1) time. \$\endgroup\$ – roippi Oct 9 '13 at 23:32
  • \$\begingroup\$ One thing you could do is split the list into positive and negative number lists beforehand, and iterate through only one of them, checking whether the corresponding value is present in the other list. \$\endgroup\$ – Asad Oct 9 '13 at 23:33
  • 2
    \$\begingroup\$ This is a two-liner if you just build the set directly from the list. mark = set(a); return [x for x in a if -x in mark]. \$\endgroup\$ – Peter DeGlopper Oct 9 '13 at 23:34
  • 1
    \$\begingroup\$ Are you answering the same assignment that Nolan Hodge had a few hours ago? \$\endgroup\$ – abarnert Oct 9 '13 at 23:37
5
\$\begingroup\$

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) & {-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 & {-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 < 0:
            neg.add(-1*i)
        else:
            pos.add(i)
    return [i for i in a if abs(i) in pos & 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 & 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.
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I contend that answers that eliminate duplicate values or return a non-list are illegitimate. \$\endgroup\$ – kojiro Oct 9 '13 at 23:53
  • \$\begingroup\$ @kojiro: On what basis? A previous user with exactly the same assignment said there were no duplicate values; this user hasn't said otherwise. Meanwhile, tossing on a list(…) isn't going to make up the 50x slowdown, but I'll do it if you insist. \$\endgroup\$ – abarnert Oct 9 '13 at 23:56
  • \$\begingroup\$ It also matters whether or not maintaining order is required. I think all the ones with reasonable performance except negated_1 don't necessarily maintain order even if you put a list() around them. \$\endgroup\$ – Peter DeGlopper Oct 9 '13 at 23:57
  • \$\begingroup\$ @PeterDeGlopper: Please see the original question, where the OP's desired output is not in the same order as the original input. So, I doubt maintaining order is important. (If so, then we have to figure out what order is important, because it's not the input order, which is what negated_1 maintains…) \$\endgroup\$ – abarnert Oct 9 '13 at 23:59
  • \$\begingroup\$ @abarnert - thanks for the link. The OP for this question didn't specify. I generally assume that when the input and output are stated to be lists, the output should maintain the input order, but it's certainly not specified one way or the other here. \$\endgroup\$ – Peter DeGlopper Oct 10 '13 at 0:01
1
\$\begingroup\$

For the sake of clarity, here is a solution that keeps duplicates and retains the original order of elements in a.

def negated_stable(a):
    '''Take a list a and returns another list which only contains the elements x such that -x is also in a'''
    b = set(a)
    return [i for i in a if -i in b]

This was my original solution, which is a little slower than other solutions here, but I'll keep it around for posterity.

def negated_posterity(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 < 0:
            neg.add(-1*i)
        else:
            pos.add(i)
    mark = pos & neg
    return [i for i in a if abs(i) in mark]

If you can sacrifice order and/or duplication this becomes a trivial problem, as demonstrated by the five or so set solutions in abarnert's answer.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This takes almost two orders of magnitude longer than Peter DeGlopper's one-liner (aka hcwhsa's answer on the earlier question). \$\endgroup\$ – abarnert Oct 9 '13 at 23:49
  • \$\begingroup\$ I think you want return list(pos & neg) \$\endgroup\$ – Bi Rico Oct 9 '13 at 23:50
  • \$\begingroup\$ @BiRico I thought of that, but OP may not want to eliminate dupes. \$\endgroup\$ – kojiro Oct 9 '13 at 23:51
  • \$\begingroup\$ The first problem with this solution is that it's evaluating pos&neg N times instead of once outside the loop. Fix that, and it becomes competitive with the others. But still not as fast, because making a set all at once, and a negated set with a comprehension, is so much faster than looping explicitly in Python that it swamps the cost of the repeated elements that you're trying to save. \$\endgroup\$ – abarnert Oct 10 '13 at 0:04
  • \$\begingroup\$ @abarnert I wondered if that was it. Thanks, fixed. \$\endgroup\$ – kojiro Oct 10 '13 at 0:10

Your Answer

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