Как извлечь элемент из набора, не удаляя его?

Question

Предположим следующее:

>>> s = set([1, 2, 3])

Как получить значение (любое значение) из s без выполнения s.pop()? Я хочу оставить элемент в наборе, пока не буду уверен, что смогу удалить его - в этом я могу быть уверен только после асинхронного вызова другого хоста.

Быстро и грязно:

>>> elem = s.pop()
>>> s.add(elem)

Но знаете ли вы лучший способ? В идеале в постоянное время.

Answer 1

Два варианта, которые не требуют копирования всего набора:

for e in s:
    break
# e is now an element from s

Или ...

e = next(iter(s))

Но в целом наборы не поддерживают индексацию или нарезку.

Answer 2

Наименее код будет:

>>> s = set([1, 2, 3])
>>> list(s)[0]
1

Очевидно, что это создаст новый список, который содержит каждого члена набора, поэтому не очень хорошо, если ваш набор очень большой.

Answer 3

Чтобы предоставить некоторые временные показатели за различными подходами, рассмотрите следующий код. get () - это мое собственное дополнение к setobject.c в Python, представляющее собой просто pop () без удаления элемента.

from timeit import *

stats = ["for i in xrange(1000): iter(s).next()   ",
         "for i in xrange(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in xrange(1000): s.add(s.pop())   ",
         "for i in xrange(1000): s.get()          "]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100))")
    try:
        print "Time for %s:\t %f"%(stat, t.timeit(number=1000))
    except:
        t.print_exc()

Вывод:

$ ./test_get.py
Time for for i in xrange(1000): iter(s).next()   :       0.433080
Time for for i in xrange(1000):
        for x in s:
                break:   0.148695
Time for for i in xrange(1000): s.add(s.pop())   :       0.317418
Time for for i in xrange(1000): s.get()          :       0.146673

Это означает, что решение for / break является самым быстрым (иногда быстрее, чем пользовательское решение get ()).

Answer 4

ТЛ; др

for first_item in muh_set: break остается оптимальным подходом в Python 3.x. ^{Проклинаю тебя, Гвидо.}

вы делаете это

Добро пожаловать в еще один набор времени Python 3.x, экстраполированный из wr. превосходный специфичный для Python 2.x ответ . В отличие от AChampion одинаково полезен специфичный для Python 3.x ответ , временные значения ниже также предложенные выше решения о превышении времени, включая:

• list(s)[0], роман Джона решение на основе последовательностей .
• random.sample(s, 1), dF. эклектика Решение на основе RNG .

Фрагменты кода для большой радости

Включите, настройте время:

from timeit import Timer

stats = [
    "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
    "for i in range(1000): next(iter(s))",
    "for i in range(1000): s.add(s.pop())",
    "for i in range(1000): list(s)[0]",
    "for i in range(1000): random.sample(s, 1)",
]

for stat in stats:
    t = Timer(stat, setup="import random\ns=set(range(100))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Быстро устаревшие временные интервалы

Вот! Упорядочены по самым быстрым и самым медленным фрагментам:

$ ./test_get.py
Time for for i in range(1000): 
    for x in s: 
        break:   0.249871
Time for for i in range(1000): next(iter(s)):    0.526266
Time for for i in range(1000): s.add(s.pop()):   0.658832
Time for for i in range(1000): list(s)[0]:   4.117106
Time for for i in range(1000): random.sample(s, 1):  21.851104

Faceplants для всей семьи

Неудивительно, что ручная итерация остается как минимум вдвое быстрее , чем следующее быстрое решение. Несмотря на то, что разрыв сократился по сравнению с плохим старым Python 2.x днями (в которых ручная итерация была как минимум в четыре раза быстрее), меня разочаровывает фанатик PEP 20 , что самое подробное решение является лучшим , По крайней мере, преобразование набора в список просто для извлечения первого элемента набора так же ужасно, как и ожидалось. Спасибо, Гвидо, пусть его свет продолжает направлять нас.

Удивительно, но решение на основе ГСЧ абсолютно ужасно. Преобразование списка плохое, но random на самом деле принимает ужасный соус. Так много для Бога случайных чисел .

Я просто хочу, чтобы аморфные Они уже использовали метод set.get_first() для нас. Если вы читаете это, Они: «Пожалуйста. Сделайте что-нибудь».

Answer 5

Так как вы хотите случайный элемент, это также будет работать:

>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]

В документации не упоминается производительность random.sample. Из очень быстрого эмпирического теста с огромным списком и огромным набором, кажется, что постоянное время для списка, но не для набора. Кроме того, итерация по набору не случайна; порядок не определен, но предсказуем:

>>> list(set(range(10))) == range(10)
True 

Если важна случайность и вам нужно множество элементов в постоянном времени (большие наборы), я бы использовал random.sample и сначала преобразовал бы в список:

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time

Answer 6

Мне было интересно, как функции будут работать для разных наборов, поэтому я сделал тест:

from random import sample

def ForLoop(s):
    for e in s:
        break
    return e

def IterNext(s):
    return next(iter(s))

def ListIndex(s):
    return list(s)[0]

def PopAdd(s):
    e = s.pop()
    s.add(e)
    return e

def RandomSample(s):
    return sample(s, 1)

def SetUnpacking(s):
    e, *_ = s
    return e

from simple_benchmark import benchmark

b = benchmark([ForLoop, IterNext, ListIndex, PopAdd, RandomSample, SetUnpacking],
              {2**i: set(range(2**i)) for i in range(1, 20)},
              argument_name='set size',
              function_aliases={first: 'First'})

b.plot()

Этот график ясно показывает, что некоторые подходы (RandomSample, SetUnpacking и ListIndex) зависят от размера набора и их следует избегать в общем случае (по крайней мере, если производительность может быть важным). Как уже показали другие ответы, самый быстрый способ - ForLoop.

Однако, если используется один из подходов с постоянным временем, разница в производительности будет незначительной.

---

iteration_utilities (Отказ от ответственности: я автор) содержит вспомогательную функцию для этого варианта использования: first:

>>> from iteration_utilities import first
>>> first({1,2,3,4})
1

Я также включил его в бенчмарк выше. Он может конкурировать с двумя другими «быстрыми» решениями, но разница не так уж и велика.

Answer 7

Я использую функцию полезности, которую я написал. Его название несколько вводит в заблуждение, поскольку подразумевает, что это может быть случайный предмет или что-то в этом роде.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None

Answer 8

По-видимому, самый компактный (6 символов), хотя очень медленный способ получить элемент набора (возможно благодаря PEP 3132 ):

e,*_=s

В Python 3.5+ вы также можете использовать это 7-символьное выражение (благодаря PEP 448 ):

[*s][0]

Обе опции в моей машине примерно в 1000 раз медленнее, чем метод for-loop.

Answer 9

После @wr. пост, я получаю аналогичные результаты (для Python3.5)

from timeit import *

stats = ["for i in range(1000): next(iter(s))",
         "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in range(1000): s.add(s.pop())"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Выход:

Time for for i in range(1000): next(iter(s)):    0.205888
Time for for i in range(1000): 
    for x in s: 
        break:                                   0.083397
Time for for i in range(1000): s.add(s.pop()):   0.226570

Однако при изменении базового набора (например, вызов remove()) дела обстоят плохо для повторяющихся примеров (for, iter):

from timeit import *

stats = ["while s:\n\ta = next(iter(s))\n\ts.remove(a)",
         "while s:\n\tfor x in s: break\n\ts.remove(x)",
         "while s:\n\tx=s.pop()\n\ts.add(x)\n\ts.remove(x)"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

Результаты:

Time for while s:
    a = next(iter(s))
    s.remove(a):             2.938494
Time for while s:
    for x in s: break
    s.remove(x):             2.728367
Time for while s:
    x=s.pop()
    s.add(x)
    s.remove(x):             0.030272

Answer 10

Как насчет s.copy().pop()? Я не рассчитал это, но это должно работать, и это просто. Однако лучше всего подходит для небольших наборов, поскольку копирует весь набор.