Как получить элемент из набора, не удаляя его?
https://stackoverflow.com/questions/59825
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Предположим следующее:
>>> s = set([1, 2, 3])
Как мне получить значение (любое значение) из s не делая s.pop()?Я хочу оставить элемент в наборе до тех пор, пока не буду уверен, что смогу его удалить — в этом я могу быть уверен только после асинхронного вызова другого хоста.
Быстро и грязно:
>>> elem = s.pop()
>>> s.add(elem)
Но знаете ли вы лучший способ?В идеале в постоянное время.
Решение
Два варианта, не требующие копирования всего набора:
for e in s:
break
# e is now an element from s
Или...
e = next(iter(s))
Но в целом наборы не поддерживают индексацию и нарезку.
Другие советы
Наименьший код будет:
>>> s = set([1, 2, 3])
>>> list(s)[0]
1
Очевидно, что это приведет к созданию нового списка, который будет содержать каждого члена набора, поэтому это не очень хорошо, если ваш набор очень большой.
Чтобы предоставить некоторые временные данные, лежащие в основе различных подходов, рассмотрим следующий код.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
Это означает, что на/перерыв решение является самым быстрым (иногда быстрее, чем собственное решение get()).
TL; доктор
for first_item in muh_set: break остается оптимальным подходом в Python 3.x. Будь ты проклят, Гвидо.
ты делаешь это
Добро пожаловать в еще один набор таймингов Python 3.x, экстраполированный из авторотлично Ответ, специфичный для Python 2.x.В отличие от Чемпионодинаково полезно Ответ, специфичный для Python 3.x, расписание ниже также предложенные выше решения по временным выбросам, в том числе:
list(s)[0], Джонроман решение на основе последовательности.random.sample(s, 1), дФ.эклектичный Решение на основе ГСЧ.
Фрагменты кода для великой радости
Включите, настройтесь, засеките время:
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
Лицевые растения для всей семьи
Неудивительно, ручная итерация остается как минимум в два раза быстрее как следующее самое быстрое решение.Хотя разрыв и сократился по сравнению с временами Bad Old Python 2.x (когда ручная итерация была как минимум в четыре раза быстрее), это разочаровывает ПЭП 20 Я фанатик того, что самое многословное решение — лучшее.По крайней мере, преобразование набора в список только для извлечения первого элемента набора столь же ужасно, как и ожидалось. Спасибо Гвидо, пусть его свет продолжает вести нас.
Удивительно, но Решение на основе ГСЧ абсолютно ужасно. Преобразование списков — это плохо, но random Действительно берет торт с ужасным соусом.Вот вам и Бог случайных чисел.
Я просто хочу, чтобы аморфные люди подняли настроение. set.get_first() метод для нас уже.Если вы это читаете, они:"Пожалуйста.Сделай что-нибудь."
Поскольку вам нужен случайный элемент, это тоже будет работать:
>>> 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
Мне было интересно, как функции будут работать для разных наборов, поэтому я провел тест:
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
Я также включил его в тест выше.Он может конкурировать с двумя другими «быстрыми» решениями, но разница в любом случае невелика.
Я использую служебную функцию, которую написал.Его название несколько вводит в заблуждение, поскольку подразумевает, что это может быть случайный предмет или что-то в этом роде.
def anyitem(iterable):
try:
return iter(iterable).next()
except StopIteration:
return None
По-видимому самый компактный (6 символов) хотя очень медленно способ получить заданный элемент (стал возможным благодаря ПЭП 3132):
e,*_=s
В Python 3.5+ вы также можете использовать это выражение из 7 символов (благодаря ПЭП 448):
[*s][0]
Оба варианта на моей машине примерно в 1000 раз медленнее, чем метод цикла for.
Следуя за @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
Как насчет s.copy().pop()?Я не засек время, но это должно сработать, и это просто.Однако лучше всего он работает для небольших наборов, поскольку копирует весь набор.
Другой вариант — использовать словарь со значениями, которые вас не интересуют.Например.,
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()
