Каков алгоритм set.intersection() в python?

Прежде всего, моя цель состоит в том, чтобы случайным образом получить только один элемент в обоих известных множествах. Итак, мой оригинальный метод - сначала пересечь два множества. А затем случайным образом подобрать элемент из пересекаемого набора. Но это глупо, потому что мне нужны только элементы, а набор пересечений.

Поэтому мне нужно найти алгоритм set.intersection().

Я сравниваю затраты времени между методами set.intersection() и for{for{}}. Set.intersection() работает быстрее, чем другие (в 100 раз). Поэтому использование for{for{}} для выбора случайных элементов не является разумной идеей.

Каков алгоритм set.intersection() в python?


python set algorithm intersection set-intersection
person Ding Ding    schedule 20.11.2013    source источник
comment
CPython, Jython, IronPython или pypy? :p... Пока при вызове set.intersection возвращается правильный результат, любая реализация может делать это по своему усмотрению. Вы можете бесплатно скачать/просмотреть исходный код любой из реализаций, чтобы увидеть, как они это делают...   -  person Jon Clements♦    schedule 20.11.2013
comment
какова ваша модель реального использования? реальный вопрос: «Какой самый быстрый способ получить случайный элемент из пересечения двух наборов?» и это, вероятно, зависит от того, являются ли ваши данные изначально набором или нет.   -  person Corley Brigman    schedule 20.11.2013

Ответы (1)


arrow_upward
12
arrow_downward

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

def intersect(a, b):
    if len(a) > len(b):
        a, b = b, a

    c = set()
    for x in a:
        if x in b:
            c.add(x)
    return c

(Or: return set(x for x in a if x in b).)

person Fred Foo    schedule 20.11.2013
comment
Это несколько отличается, когда set.intersection предоставляется с неустановленными итерациями (и где есть более одной итерации) - person Jon Clements♦; 20.11.2013
comment
@JonClements: в этом случае он пропускает только обмен. Первый аргумент должен быть set. - person Fred Foo; 20.11.2013
comment
Интересно. Есть ли способ гарантировать, что x происходит из определенного набора или он всегда больше? - person mjacksonw; 22.11.2013
comment
@M.JacksonWilkinson: это всегда меньший, потому что, когда вы перебираете больший набор, вы гарантированно обрабатываете некоторые элементы, которых нет в меньшем наборе. - person Fred Foo; 22.11.2013