假设如下:
>>> s = set([1, 2, 3])
我如何得到一个值(任何值)不做s.pop()?我希望将项目留在集合中,直到我确定可以删除它—只有在对另一个主机进行异步调用之后才能确定这一点。
又快又脏:
>>> elem = s.pop()
>>> s.add(elem)
但你知道更好的办法吗?理想情况是在常数时间内。
假设如下:
>>> s = set([1, 2, 3])
我如何得到一个值(任何值)不做s.pop()?我希望将项目留在集合中,直到我确定可以删除它—只有在对另一个主机进行异步调用之后才能确定这一点。
又快又脏:
>>> elem = s.pop()
>>> s.add(elem)
但你知道更好的办法吗?理想情况是在常数时间内。
两个不需要复制整个集合的选项:
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]
这种选择的一个副作用是,您的代码将向后兼容旧的预先设置的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
如果随机性很重要,并且你需要在常数时间内(大型集合)使用一堆元素,那么我会使用随机性。先采样并转换为列表:
>>> 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
这意味着for/break解决方案是最快的(有时比自定义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;
对于muh_set中的first_item: break仍然是Python 3.x中的最佳方法。诅咒你,圭多。
你这样做
欢迎来到另一套Python 3。X时序,由wr推断。的优秀Python 2。x-specific响应。不像champion同样有用的Python 3。x特定的响应,下面的时间以及上面建议的时间异常值解决方案-包括:
list(s)[0], John新颖的基于序列的解决方案。 随机的。样品(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
面向整个家庭的Faceplants
不出所料,手动迭代的速度至少是第二快的解决方案的两倍。虽然与Bad Old Python 2相比,差距有所缩小。x天(其中手动迭代的速度至少是它的四倍),最详细的解决方案是最好的,这让我这个PEP 20狂热者感到失望。至少将一个集合转换为一个列表只是为了提取集合的第一个元素是可怕的。感谢圭多,愿他的光芒继续指引我们。
令人惊讶的是,基于rng的解决方案非常糟糕。列表转换是糟糕的,但随机确实是糟糕的。随机数之神也就这么多了。
我只是希望无定形的They已经为我们PEP了一个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()
这张图清楚地显示了一些方法(RandomSample, SetUnpacking和ListIndex)依赖于集合的大小,在一般情况下应该避免(至少在性能可能很重要的情况下)。正如其他答案所示,最快的方法是ForLoop。
然而,只要使用常数时间方法中的一种,性能差异就可以忽略不计。
iteration_utilities(免责声明:我是作者)包含了这个用例的方便函数:
>>> from iteration_utilities import first
>>> first({1,2,3,4})
1
我还将它包含在上面的基准测试中。它可以与其他两种“快速”解决方案竞争,但两者之间的差异并不大。
对于小型集合,我通常会创建类似这样的解析器/转换器方法
def convertSetToList(setName):
return list(setName)
然后我可以使用新的列表和访问索引号
userFields = convertSetToList(user)
name = request.json[userFields[0]]
作为一个列表,您将拥有所有其他可能需要使用的方法