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

429

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

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

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

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

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

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

Дарен Томас
источник
8
Кто-нибудь знает, почему в python эта функция еще не реализована?
hlin117
Какой вариант использования? Сет не имеет этой способности по причине. Вы должны выполнять итерацию по нему и выполнять связанные с множеством операции, например, и unionт.д., не беря из него элементы. Например, next(iter({3,2,1}))всегда возвращает, 1поэтому, если вы думали, что это вернет случайный элемент - это не так. Так, может быть, вы просто используете неправильную структуру данных? Какой вариант использования?
user1685095
1
Связанный: stackoverflow.com/questions/20625579/… (я знаю, это не тот же самый вопрос, но есть стоящие альтернативы и идеи там.)
Джон Y
@ hlin117 Потому что набор - неупорядоченная коллекция . Поскольку порядок не ожидается, нет смысла извлекать элемент в заданной позиции - ожидается, что он будет случайным.
Jeyekomon

Ответы:

548

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

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

Или...

e = next(iter(s))

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

Блэр Конрад
источник
4
Это отвечает на мой вопрос. Увы, я думаю, что я все еще буду использовать pop (), так как итерация, кажется, сортирует элементы. Я бы предпочел их в случайном порядке ...
Дарен Томас,
9
Я не думаю, что iter () сортирует элементы - когда я создаю set и pop (), пока он не становится пустым, я получаю согласованное (отсортированное, в моем примере) упорядочение, и оно совпадает с итератором - pop ( ) не обещает случайный порядок, просто произвольный, как в «Я ничего не обещаю».
Блэр Конрад
2
+1 iter(s).next()не брутто, но отлично. Полностью общий, чтобы взять произвольный элемент из любого итерируемого объекта. Ваш выбор, если вы хотите быть осторожным, если коллекция пуста.
u0b34a0f6ae
8
Следующий (iter (s)) также в порядке, и я склонен думать, что он читается лучше. Кроме того, вы можете использовать часовой для обработки случая, когда s пусто. Например, следующий (iter (s), set ()).
JA
5
next(iter(your_list or []), None)обрабатывать None множеств и пустых множеств
MrE
112

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

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

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

Джон
источник
97
next(iter(s))превышает только list(s)[0]на три символа и в остальном значительно превосходит как по времени, так и по сложности пространства. Таким образом, хотя утверждение «наименьшего кода» тривиально верно, также тривиально верно, что это наихудший возможный подход. Даже удаление вручную и затем повторное добавление удаленного элемента в исходный набор лучше, чем «создать целый новый контейнер только для извлечения первого элемента», что явно безумно. Больше всего меня беспокоит то, что 38 Stackoverflowers фактически проголосовали за это. Я просто знаю, что увижу это в рабочем коде.
Сесил Карри
19
@augurar: Потому что это делается довольно просто. И иногда это все, что имеет значение в быстром сценарии.
tonysdg
4
@Vicrobot Да, но это происходит путем копирования всей коллекции и превращения операции O (1) в операцию O (n). Это ужасное решение, которое никто не должен использовать.
Авгурар
9
Кроме того, если вы просто стремитесь к «наименьшему коду» (который глуп), тогда min(s)используйте еще меньше символов, будучи столь же ужасным и неэффективным, как этот.
Авгурар
5
+1 для победителя кода гольф, который у меня есть практический контрпример для того, чтобы быть "ужасным и неэффективным": min(s)немного быстрее, чем next(iter(s))для наборов размера 1, и я пришел к этому ответу, специально ища особый случай извлечения единственного элемента из наборов размером 1.
Lehiester
52

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

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

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

MSeifert
источник
43

ТЛ; др

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

ты делаешь это

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

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

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

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()способ для нас. Если вы читаете это, они: «Пожалуйста. Сделайте что-нибудь».

Сесил Карри
источник
2
Я думаю, что жаловаться, что next(iter(s)) это в два раза медленнее, чем for x in s: breakв, CPythonэто немного странно. Я имею в виду, что это так CPython. Это будет примерно в 50-100 раз (или что-то в этом роде) медленнее, чем C или Haskell, выполняющие одно и то же (в большинстве случаев, особенно в итерации, без исключения хвостовых вызовов и без оптимизаций). Потеря некоторых микросекунд не имеет большого значения. Ты не думаешь? И есть также PyPy
user1685095
39

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

сог.
источник
Кто-нибудь есть идея, почему iter (s) .next () намного медленнее, чем другие возможности, даже медленнее, чем s.add (s.pop ())? Для меня это очень плохой дизайн iter () и next (), если время выглядит так.
Песчу
Для этой строки каждая новая итерация создает новый объект iter.
Райан
3
@Ryan: Не является ли объект итератора неявным образом созданным для for x in s? «Итератор создан для результата expression_list
Musiphil
2
@musiphil Это правда; Первоначально я пропустил «разрыв», который был на уровне 0,14, что действительно нелогично. Я хочу глубоко погрузиться в это, когда у меня будет время.
Райан
1
Я знаю, что это старо, но при добавлении s.remove()в микс iterпримеры forи iterидут катастрофически плохо.
Чемпион
28

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

>>> 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
дР.
источник
14
Если вам нужен только один элемент, random.choice будет более разумным.
Грегг Линд
list (s) .pop () будет делать, если вам все равно, какой элемент взять.
Евгений
8
@Gregg: Вы не можете использовать choice(), потому что Python попытается проиндексировать ваш набор, и это не работает.
Кевин
3
Хотя это и умно, на самом деле это самое медленное решение, которое предлагается на порядок. Да, это , что медленно. Даже преобразование набора в список просто для извлечения первого элемента этого списка происходит быстрее. Для неверующих среди нас ( ... привет! ) Посмотрите эти невероятные времена .
Сесил Карри
9

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

e,*_=s

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

[*s][0]

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

Сковородкин
источник
1
Метод цикла for (или, точнее, метод итератора) имеет временную сложность O (1), тогда как эти методы O (N). Они лаконичны . :)
ForeverWintr
6

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

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None
Ник
источник
2
Вы также можете перейти к следующему (iter (итерируемый), None), чтобы сэкономить чернила :)
1 ''
3

После @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

Тем не менее, при изменении базового набора (например, call to 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
AChampion
источник
1

Что я обычно делаю для небольших коллекций, так это для создания такого метода синтаксического анализа / конвертера, как этот

def convertSetToList(setName):
return list(setName)

Тогда я могу использовать новый список и доступ по номеру индекса

userFields = convertSetToList(user)
name = request.json[userFields[0]]

В качестве списка у вас будут все остальные методы, с которыми вам может потребоваться работать

Хосе Карвахаль
источник
почему бы просто не использовать listметод создания конвертера?
Дарен Томас
-1

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

Соломон Уцко
источник
-6

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


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]

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

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


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()
Пэт Нотц
источник
3
Это не работает так, как вы надеетесь. В python 2 keys () - это операция O (n), поэтому вы больше не используете постоянное время, но, по крайней мере, keys [0] вернет ожидаемое вами значение. В python 3 keys () - это O (1) операции, так что ура! Однако он больше не возвращает объект списка, он возвращает объект, подобный множеству, который не может быть проиндексирован, поэтому keys [0] выдает TypeError. stackoverflow.com/questions/39219065/…
sage88