如何从集合中检索一个元素而不将其删除？

Question

假设如下：

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

如何在不使用 s.pop() 的情况下从 s 中获取一个值（任意值）？我想在确认可以将其删除之前保留集合中的项目 - 这只有在对另一个主机进行异步调用后才能确定。

简单粗暴：

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

你知道更好的方法吗？最好是常数时间。

- Daren Thomas

---

有人知道为什么Python还没有实现这个函数吗？ - hlin117

使用场景是什么？集合之所以没有这种能力是有原因的。您应该通过迭代它并执行类似于“union”等的集合操作，而不是从中获取元素。例如，next(iter({3,2,1}))总是返回1，因此如果您认为它会返回随机元素-它不会。那么也许您只是使用了错误的数据结构？使用场景是什么？ - user1685095

@hlin117 因为集合是一种无序集合。由于不需要顺序，因此在给定位置检索元素是没有意义的 - 预计它是随机的。 - Jeyekomon

@hlin117 那么为什么这没有意义呢？它被称为“有放回抽样”... - Radio Controlled

一个我经常遇到的合理应用场景是这样的：我正在编写一项测试，并且获得了一个集合。我想查看其中任何一个值以便为测试构建更多数据。我不关心我得到哪一个值，我也不在乎每次是否相同或不同。我只需要从集合中获取一个值。 - Troy Daniels

Answer 1

两种选项不需要复制整个集合：

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

或者...

e = next(iter(s))

但一般而言，集合不支持索引或切片。

- Blair Conrad

---

这回答了我的问题。唉，我想我还是会使用pop()，因为迭代似乎会对元素进行排序。我更喜欢它们的随机顺序... - Daren Thomas

我认为 iter() 函数并没有对元素进行排序——当我创建一个集合并且不断使用 pop() 直到为空时，我得到一致的（已排序的，在我的例子中）顺序，并且与迭代器的顺序相同。pop() 函数并不保证随机顺序，只是任意的，就像“我什么也不保证”一样。 - Blair Conrad

+1 iter(s).next()不仅不粗糙，而且非常棒。它可以从任何可迭代对象中提取任意元素，非常通用。但如果集合为空，你可以选择小心处理。 - u0b34a0f6ae

使用 next(iter(s)) 也可以，我认为这样读起来更好。另外，你可以使用一个 sentinel 来处理 s 为空的情况。例如：next(iter(s), set())。 - j-a

为了处理空集合和None集合，可以使用next(iter(your_list or []), None)。 - MrE

Answer 2

最简代码：

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

显然，这将创建一个包含集合中每个成员的新列表，因此如果您的集合非常大，则不是一个好的选择。

- John

---

因为它以相对简单的方式完成任务。有时在快速编写脚本时，这就是最重要的。 - tonysdg

我认为人们选择这个答案是因为set主要不适用于索引和切片操作；而这位用户建议改用适合这类工作的数据类型，即list。 - Vicrobot

@Vicrobot 没错，但这么做的方式是通过复制整个集合并将一个 O(1) 操作变成一个 O(n) 操作。这是一种可怕的解决方案，任何人都不应该使用它。 - augurar

如果你只追求“最少的代码”（这很愚蠢），那么使用min(s)虽然更少字符，但和这个方法一样糟糕和低效。 - augurar

对于代码高尔夫比赛的获胜者点赞，但我有一个实际的反例证明了"可怕且低效"：当集合大小为1时，min(s) 稍微比 next(iter(s)) 快一些，而我恰好寻求从大小为1的集合中特殊情况提取唯一元素的答案。 - lehiester

Answer 3

我想知道不同数据集对这些函数的性能表现如何，因此我进行了基准测试：

我想知道不同数据集对这些函数的性能表现如何，因此我进行了基准测试：

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

---

这是一个很棒的回答。感谢您花时间进行实证。 - Eric McLachlan

我有一个简短的问题，为什么你在ForLoop中使用break而不是直接使用return e？函数应该在执行返回时“中断”。 - Andreas

@Andreas 非常好的观点，感谢你提出。但是关于“为什么”：我想比较其他答案的运行时间，所以我只是简单地复制了那些答案的方法。在这种情况下，答案中有 break（参见 https://dev59.com/1HVD5IYBdhLWcg3wL4cA#59841）…虽然不是一个好的答案，但我并不想太大程度地改变他们的代码。 - MSeifert

我决定使用你的包 - 如果集合为空，希望它能抛出一个错误。这只是未来的一个想法。 - Adventure-Knorrig

@DanielJerrehian 在这种情况下，你可以提供一个默认值 first(set(), default=None) 作为示例 :) - MSeifert

Answer 4

简短总结

for first_item in muh_set: break 仍然是在Python 3.x中最优的方法。 ^{Guido，你这个混蛋。}

为什么要这样做

欢迎来到另一组Python 3.x定时数据，这些数据是从wr的出色的Python 2.x-specific response中推断而来。与AChampion同样有用的Python 3.x-specific response不同，下面的定时还计时了上面提出的异常解决方案，包括：

• list(s)[0]，John的新颖基于序列的解决方案。
• random.sample(s, 1)，dF.的折衷基于RNG的解决方案。

代码片段带来的巨大喜悦

打开，调整，计时：

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

全家人都可以尝试的失败案例

毫不意外，手动迭代仍然是至少比下一个最快的解决方案快两倍。虽然差距已经从糟糕的 Python 2.x 时代减小（手动迭代至少比其他方法快四倍），但让我这个 PEP 20 狂热者失望的是，最冗长的解决方案是最好的。至少将集合转换为列表以提取集合的第一个元素就像预期的那样可怕。感谢 Guido，愿他的光继续引领我们。

令人惊讶的是，基于 RNG 的解决方案非常糟糕。列表转换很糟糕，但是 random 的表现真的很差。所以这就是所谓的随机数之神。

我只希望无形中的“他们”能够为我们推出一个set.get_first() 方法。如果你正在阅读这篇文章，“他们”啊：“请做些什么吧。”

- Cecil Curry

---

我认为在Python解释器中，抱怨next(iter(s))比for x in s: break慢两倍有点奇怪。我是说这是Python解释器，相比于使用C或Haskell完成同样的任务，它将慢50-100倍左右（尤其是在迭代中）。失去几微秒并不会产生实质上的影响，你觉得呢？此外还有PyPy。 - user1685095

由于集合没有顺序，set.get_first() 可能会误导。但我想要一个 set.get_any() 方法，它可以返回集合中的任意元素，即使该元素总是相同的。 - Eduardo

在Python 3.11中，似乎s.add(s.pop())的速度更快：循环1000次所需时间： for x in s: break: 0.044704 循环1000次所需时间： next(iter(s)): 0.063221 循环1000次所需时间： s.add(s.pop()): 0.056717 循环1000次所需时间： list(s)[0]: 0.835464 - undefined

Answer 5

为了提供一些关于不同方法的时间数据，请考虑以下代码。 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

这意味着for/break解决方案是最快的（有时比自定义get()解决方案更快）。

- wr.

---

有没有人知道为什么iter(s).next()比其他选项慢得多，甚至比s.add(s.pop())还要慢？对我来说，如果时间看起来像那样，那么这似乎是iter()和next()非常糟糕的设计。 - peschü

首先，这行代码会在每次迭代中创建一个新的 iter 对象。 - Ryan

@Ryan：对于 for x in s，也会隐式创建一个迭代器对象，是吗？"会为 expression_list 的结果创建一个迭代器。" - musiphil

@musiphil 没错；最初我错过了 "break" 在 0.14 的位置，这确实很不直观。我想等有时间时深入研究一下这个问题。 - Ryan

我知道这很老，但是当将s.remove()加入到混合中时，iter示例的for和iter都会变得非常糟糕。 - AChampion

Answer 6

如果你需要一个随机的元素，这个方法同样适用：

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

---

如果您只想要一个元素，使用random.choice更为合适。 - Gregg Lind

list（s）.pop（）如果您不关心采取哪个元素，就可以使用它。 - Evgeny

@Gregg：你不能使用choice()，因为Python会尝试索引你的集合，并且这样做是行不通的。 - Kevin

虽然聪明，但这实际上是迄今为止建议的最慢的解决方案，比其他解决方案慢了一个数量级。是的，就是那么慢。即使将集合转换为列表以提取该列表的第一个元素也更快。对于我们中的怀疑者（嗨！），请参见这些绝妙的计时。 - Cecil Curry

Answer 7

Python 3 中另一种方法：

next(iter(s))

或者

s.__iter__().__next__()

- dzang

---

next(iter(s))会做同样的事情，但更短且更符合Python风格。 - Eerik Sven Puudist

Answer 8

看似是最紧凑（6个字符），但非常缓慢的获取一个集合元素的方法（通过PEP 3132实现）：

e,*_=s

从Python 3.5+开始，您还可以使用这个7符号表达式（感谢PEP 448）：

[*s][0]

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

- skovorodkin

---

for循环方法（更准确地说是迭代器方法）的时间复杂度为O(1)，而这些方法的时间复杂度为O(N)。虽然它们比较“简洁” :)。 - ForeverWintr

Answer 9

在@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

Answer 10

我使用了一个我自己写的实用函数。它的名称有些误导，因为它有点暗示它可能是一个随机项或类似的东西。

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

- Nick

---

你也可以使用 next(iter(iterable), None) 来节省墨水 :) - 1''