Разница в скорости между intersection () и «объект для объекта в наборе, если объект в другом_сете» - PullRequest
Новая
       24

Разница в скорости между intersection () и «объект для объекта в наборе, если объект в другом_сете»

6 голосов
/ 25 июля 2011

Какой из них быстрее? Один "лучше"? По сути, у меня будет два набора, и я хочу в итоге получить один совпадение между двумя списками. Так что на самом деле я предполагаю, что цикл for больше похож на: 

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

Как я уже сказал - мне нужен только один матч, но я не уверен, как обрабатывается intersection(), поэтому я не знаю, лучше ли это. Кроме того, если это поможет, other_set - это список из 100 000 компонентов, а set - это, возможно, несколько сотен, макс. несколько тысяч.

Ответы [ 3 ]

8 голосов
/ 25 июля 2011 
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)

Время: 

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

Создание их в наборах в настройке и запуск 10000 прогонов вместо 100 выходов 

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

Так что ваша версия намного быстрее, независимо от тогоимеет смысл преобразовать их в наборы.

2 голосов
/ 25 июля 2011

Ваш код в порядке.Поиск предметов if object in other_set для наборов довольно эффективен.

0 голосов
/ 14 июля 2014

Я написал простую утилиту, которая проверяет, имеют ли два набора хотя бы один общий элемент.У меня была та же проблема с оптимизацией сегодня, и ваш пост спас мой день.Это просто способ поблагодарить вас за указание на это, надеюсь, это поможет и другим людям:)

Обратите вниманиеУтилита НЕ возвращает первый общий элемент, а возвращает true, если у них есть хотя бы один общий элемент, в противном случае - false.Конечно, это может быть легко взломано для достижения вашей цели. 

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
...