假设如下:

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

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

又快又脏:

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

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


当前回答

@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

其他回答

最少的代码是:

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

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

@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

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

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

>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]

文档中似乎没有提到random.sample的性能。从一个非常快速的经验测试中,有一个巨大的列表和一个巨大的集合,对于列表来说似乎是常数时间,而对于集合来说则不是。而且,集合上的迭代不是随机的;顺序没有定义,但可以预测:

>>> list(set(range(10))) == range(10)
True 

如果随机性很重要,并且你需要在常数时间内(大型集合)使用一堆元素,那么我会使用随机性。先采样并转换为列表:

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

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

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