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

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

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

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

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

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

Но знаете ли вы, что лучше? Идеально в постоянное время.

Ответы

Ответ 1

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

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

Или...

e = next(iter(s))

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

Ответ 2

Наименьший код:

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

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

Ответ 3

Чтобы предоставить некоторые временные диаграммы за разными подходами, рассмотрите следующий код. Get() - это мое пользовательское дополнение к Python setobject.c, являющееся просто 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

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

Ответ 4

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

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

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

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

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

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

Ответ 5

TL;DR

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

y u делаем это

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

list(s)[0], John новое последовательное решение.
random.sample(s, 1), dF. eclectic 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()

Быстрое устаревание Timeless Timings

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

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

Лицевые панели для всей семьи

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

Удивительно, что решение на основе RNG абсолютно ужасно. Преобразование списков неверно, но random действительно принимает пирог с ужасным соусом. Так много для Random Number God.

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

Ответ 6

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

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

Ответ 7

Следуя @wr. post, я получаю аналогичные результаты (для 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

Ответ 8

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

e,*_=s

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

[*s][0]

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

Ответ 9

Другой вариант - использовать словарь со значениями, которые вам не нужны. Например.


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...

Вы можете рассматривать ключи как набор, за исключением того, что они всего лишь массив:


keys = poor_man_set.keys()
print "Some key = %s" % keys[0]

Побочным эффектом этого выбора является то, что ваш код будет обратно совместим со старыми версиями Python до set. Возможно, это не лучший ответ, но это еще один вариант.

Edit: вы можете даже сделать что-то подобное, чтобы скрыть тот факт, что вы использовали dict вместо массива или set:


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
poor_man_set = poor_man_set.keys()