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

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

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

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

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

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

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

вопрос задан 12.09.2008
Daren Thomas
41190 репутация

11 ответов


  • 0 рейтинг

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

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

    Редактировать: Вы даже можете сделать что-то подобное, чтобы скрыть тот факт, что вы использовали 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()
    
    ответ дан Pat Notz, с репутацией 124449, 12.09.2008
  • 0 рейтинг

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

    e,*_=s
    

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

    [*s][0]
    

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

    ответ дан skovorodkin, с репутацией 2807, 21.08.2017
  • 0 рейтинг

    Подписан на @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
    
    ответ дан AChampion, с репутацией 20218, 24.01.2016
  • 0 рейтинг

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

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

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

    ответ дан John, с репутацией 8698, 13.09.2008
  • 0 рейтинг

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

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

    ответ дан wr., с репутацией 2391, 23.10.2009
  • 0 рейтинг

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

    >>> 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., с репутацией 50579, 12.09.2008
  • 0 рейтинг

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

    ответ дан Solomon Ucko, с репутацией 488, 6.03.2018
  • 0 рейтинг

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

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

    или. , ,

    e = next(iter(s))
    

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

    ответ дан Blair Conrad, с репутацией 145093, 12.09.2008
  • 0 рейтинг

    тл; д-р

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

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

    Добро пожаловать в еще один набор Python 3. х тайминги, экстраполированные от отлично Python 2. х-специфический ответ . В отличие от 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()
    

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

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

    $ ./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 для всей семьи

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

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

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

    ответ дан Cecil Curry, с репутацией 3830, 15.10.2016
  • 0 рейтинг

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

    def anyitem(iterable):
        try:
            return iter(iterable).next()
        except StopIteration:
            return None
    
    ответ дан Nick, с репутацией 8066, 14.09.2008
  • 0 рейтинг

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

    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()
    

    enter image description here

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

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


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

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

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

    ответ дан MSeifert, с репутацией 69479, 19.02.2018