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

Обновить

November 2018

Просмотры

270.9k раз

305

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

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

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

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

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

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

11 ответы

0

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

71

Наименее код будет выглядеть так:

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

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

9

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

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

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

5

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

e,*_=s

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

[*s][0]

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

2

После @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()) дела идут плохо для Iterable примеров ( 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
6

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

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

ТЛ; др

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

юй это сделать

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

Фрагменты кода для Great Joy

Включите, настроиться, раз это:

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

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

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

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

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

-1

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


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. Это , возможно , не самый лучший ответ , но это еще один вариант.

Edit: Вы можете даже сделать что-то вроде этого, чтобы скрыть тот факт, что вы использовали 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()
394

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

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

Или же...

e = next(iter(s))

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

25

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

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

Для того, чтобы обеспечить некоторые цифры синхронизации позади различных подходов, рассмотрим следующий код. ГЭТ () мой заказ дополнение к setobject.c Python, будучи просто поп () без удаления элемента.

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

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

wr.