7

Which one of these is faster? Is one "better"? Basically I'll have two sets and I want to eventually get one match from between the two lists. So really I suppose the for loop is more like:

for object in set:
    if object in other_set:
        return object

Like I said - I only need one match, but I'm not sure how intersection() is handled, so I don't know if its any better. Also, if it helps, the other_set is a list near 100,000 components and the set is maybe a few hundred, max few thousand.

3
  • 1
    It probably depends how many matches are likely to be there. intersection will keep going until it's found them all, but on the other hand, intersection is implemented in C, so the actual code will run faster.
    – Thomas K
    Jul 25, 2011 at 19:43
  • ...and for those who prefer a one liner: filter(other_set.__contains__, some_set) and the difference filter(lambda x: other_set.__contains__(x), some_set).
    – 0 _
    Apr 28, 2015 at 1:26
  • Is there any known relationship between them? Is one a subset of the other (as is tested in the accepted solution)? Feb 14, 2018 at 0:50

4 Answers 4

8
from timeit import timeit

setup = """
from random import sample, shuffle
a = range(100000)
b = sample(a, 1000)
a.reverse()
"""

forin = setup + """
def forin():
    # a = set(a)
    for obj in b:
        if obj in a:
            return obj
"""

setin = setup + """
def setin():
    # original method:
    # return tuple(set(a) & set(b))[0]
    # suggested in comment, doesn't change conclusion:
    return next(iter(set(a) & set(b)))
"""

print timeit("forin()", forin, number = 100)
print timeit("setin()", setin, number = 100)

Times:

>>>
0.0929054012768
0.637904308732
>>>
0.160845057616
1.08630760484
>>>
0.322059185123
1.10931801261
>>>
0.0758695262169
1.08920981403
>>>
0.247866360526
1.07724461708
>>>
0.301856152688
1.07903130641

Making them into sets in the setup and running 10000 runs instead of 100 yields

>>>
0.000413064976328
0.152831597075
>>>
0.00402408388788
1.49093627898
>>>
0.00394538156695
1.51841512101
>>>
0.00397715579584
1.52581949403
>>>
0.00421472926155
1.53156769646

So your version is much faster whether or not it makes sense to convert them to sets.

6
  • Thanks for the great breakdown - should need set conversion really, since most of the stuff I'm doing with sets is a set in the first place, but I see what you mean. Once again I realize how much I should really have a look at timeit - should've thought of that. Thanks again!
    – Jon Phenow
    Jul 25, 2011 at 20:08
  • 1
    try next(x for x in the_list if x in the_set) Jul 25, 2011 at 20:59
  • your second results don't match mine in that I am getting lots of variability (especially between the next and for / if in tests. but in all my tests, converting to a set before the function call is a better choice; giving a huge speed increase. Jan 27, 2013 at 14:21
  • I suspect that you can skip the expense of creating the big tuple in tuple(set(a) & set(b))[0] if instead you do next(iter(set(a) & set(b))). Feb 3, 2017 at 18:26
  • 1
    I'd like to note for future folks that this returns AN object that is in both sets. Finding the first one will most likely do better than running a full intersection() which returns ALL objects that are in both Jul 16, 2017 at 0:17
5

I realize this is a older post. But, I arrived here looking for performance speeds comparing using intersection vs in and thought it'd be worth adding more info. The answers above were great, but left me unclear as to the actual best path forward.

The "first result" solution doesn't solve for my use case specifically.

Instead, I wanted to know how the different implementations would perform, producing identical results sets, using discrete approaches. Not just the first single intersected value. As such, below I've included code to perform an evaluation of the options with a 1000 loop test. Contrary to what @agf posted, using sets is far faster when the desired output is a list of matches.

My results were:

runForin took 132851.600ms
runForinBlist took 37700.916ms
True
runForInListComp took 132783.147ms
True
runForinSet took 780.919ms
True
runSetIntersection took 760.980ms (WINNER)
True
runSetin took 771.921ms
True

Here's the code. Hope it helps someone. Note: I also evaluated the blist (http://stutzbachenterprises.com/blist/blist.html) library as it performs quite well in other use cases.

import time
from random import sample, shuffle
from blist import blist

a = range(100000)
aBlist = blist([i for i in a])

b = sample(a, 1000)
a.reverse()

def print_timing(func):
    def wrapper(*arg):
        t1 = time.time()
        res = func(*arg)
        t2 = time.time()
        print '%s took %0.3fms' % (func.func_name, (t2-t1)*1000.0)
        return res
    return wrapper


def forIn():
    ret = []
    for obj in b:
        if obj in a:
            ret.append(obj)
    return ret

def forInBlist():
    ret = []
    for obj in b:
        if obj in aBlist:
            ret.append(obj)
    return ret


def forInListComp():
    return [value for value in b if value in a] 


def forInSet():
    ret = []
    for obj in b:
        if obj in set(a):
            ret.append(obj)
    return ret


def setIntersection(): 
    return set(a).intersection(b) 


def setIn():
    return list(set(a) & set(b))


@print_timing
def runForIn(times):
    for i in range(times):
        ret = forIn()
    return ret
        
@print_timing
def runForInBlist(times):
    for i in range(times):
        ret = forInBlist()
    return ret

@print_timing
def runForInListComp(times):
    for i in range(times):
        ret = forInListComp()
    return ret

@print_timing
def runForInSet(times):
    for i in range(times):
        ret = forInSet()
    return ret

@print_timing
def runSetIntersection(times):
    for i in range(times):
        ret = setIntersection()
    return ret

@print_timing
def runSetIn(times):
    for i in range(times):
        ret = setIn()
    return ret

def checkResults(results):
    master = None
    for resultSet in results:
        if not master:
            master = sorted(list(resultSet))
            continue
        try:
            if master != sorted(list(resultSet)):
                return False, master, sorted(list(resultSet))
        except:
            print resultSet
            return False
    return True

iterations = 5
results = []
runForInResults = runForIn(iterations)
results.append(runForInResults)

runForInBlistResults = runForInBlist(iterations)
results.append(runForInBlistResults)
print checkResults(results)

runForInListCompResults = runForInListComp(iterations)
results.append(runForInListCompResults)
print checkResults(results)

runForInSetResults = runForInSet(iterations)
results.append(runForInSetResults)
print checkResults(results)

runSetIntersectionResults = runSetIntersection(iterations)
results.append(runSetIntersectionResults)
print checkResults(results)

runSetInResults = runSetIn(iterations)
results.append(runSetInResults)
print checkResults(results)
2

Your code is fine. Item lookup if object in other_set for sets is quite efficient.

0

I wrote a simple utility that checks if two sets have at least one element in common. I had the same optimization problem today and your post saved my day. This is just a way to thank you for pointing this out, hope this will help other people too :)

Notice. The utility does NOT return the first element in common but rather returns true if they have at least one element in common, false otherwise. Of course it can be easily hacked to meet your goal.

def nonEmptyIntersection(A, B):
    """
    Returns true if set A intersects set B.
    """
    smaller, bigger = A, B
    if len(B) < len(A):
        smaller, bigger = bigger, smaller
    for e in smaller:
        if e in bigger:
            return True
    return False

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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