如何从集合中检索一个元素而不删除它?

假设如下:

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

我如何得到一个值(任何值)从s不做s.pop()?我希望将项目留在集合中，直到我确定可以删除它—只有在对另一个主机进行异步调用之后才能确定这一点。

又快又脏:

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

但你知道更好的办法吗?理想情况是在常数时间内。

775291 次浏览
小开
最佳答案

两个不需要复制整个集合的选项:

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

还是……

e = next(iter(s))

但一般来说，集合不支持索引或切片。

小开

另一种选择是使用包含您不关心的值的字典。例如,


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。这可能不是最好的答案，但这是另一种选择。

编辑:你甚至可以这样做来隐藏你使用字典而不是数组或集合的事实:


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

因为你想要一个随机元素，这也可以:

>>> 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
小开

最少的代码是:

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

显然，这将创建一个包含集合中的每个成员的新列表，所以如果你的集合非常大，就不太好了。

小开

我用的是我写的效用函数。它的名字有点误导，因为它暗示它可能是一个随机的项目或类似的东西。

def anyitem(iterable):
try:
return iter(iterable).next()
except StopIteration:
return None
小开
为了提供不同方法背后的一些时间数字，考虑以下代码。 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

这意味着< em > /打破< / em >解决方案是最快的(有时比自定义get()解决方案还要快)。

小开

@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
小开

博士tl;

for first_item in muh_set: break仍然是Python 3.x中的最佳方法。# EYZ1

你这样做

欢迎来到另一套Python 3。x计时，从或者说是。的优秀Python 2。x-specific响应推断。与冠军同样有用的Python 3。x-specific响应不同，上面建议的也时间异常值解决方案包括:

快乐的代码片段

打开，收听，计时:

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相比，差距有所缩小。* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *。至少将一个集合转换为一个列表只是为了提取集合的第一个元素是可怕的。# EYZ2

令人惊讶的是，基于rng的解决方案非常糟糕。列表转换很糟糕，但random 真的却获得了糟糕的酱料蛋糕。EYZ3就是这么多了。

我只是希望他们能给我们提供一个set.get_first()方法。如果你在读这篇文章，他们会说:“拜托。做点什么。”

小开

看起来最紧凑的(6个符号)虽然非常缓慢的的方式来获得一个集合元素(由PEP 3132实现):

e,*_=s

在Python 3.5+中，你也可以使用这个7符号表达式(感谢PEP 448):

[*s][0]

在我的机器上，这两个选项都比for循环方法慢大约1000倍。

小开

我想知道这些函数对于不同的集合会有怎样的表现，所以我做了一个基准测试:

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(免责声明:我是作者)包含了这个用例的方便函数:

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

我还将它包含在上面的基准测试中。它可以与其他两种“快速”解决方案竞争，但两者之间的差异并不大。

小开

s.copy().pop()怎么样?我还没有计时，但应该可以，而且很简单。但是，它最适用于小集，因为它复制了整个集。

小开

对于小型集合，我通常会创建类似这样的解析器/转换器方法

def convertSetToList(setName):
return list(setName)

然后我可以使用新的列表和访问索引号

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

作为一个列表，您将拥有所有其他可能需要使用的方法

小开

你可以解包这些值来访问元素:

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


v1, v2, v3 = s


print(v1,v2,v3)
#1 2 3
小开

在Python 3中还有另一种方法:

next(iter(s))

或

s.__iter__().__next__()
小开

如果你只想要第一个元素，试试这个: B = (a-set()).pop()


提交答案