logo标签列表

Python：在枚举中查找字符串的最快方法

pythonstringsearchpython-2.7enumeration
4

解析了IANA子标记（参见级联字符串拆分，Pythonic方式），并列出了8600个标记：

tags= ['aa',
       'ab',
       'ae',
       'af',
       'ak',
       'am',
       'an',
       'ar',
       # ...

我希望检查例如mytag="ro"是否在列表中，最快的方法是什么：

第一种解决方案：

if mytag in tags:
    print "found"

第二解决方案：

if mytag in Set(tags):
    print "found"

第三种解决方案：将列表转换为一个大字符串，如：'|aa|ab|ae|af|ak|am|an|ar|...'，然后查看该字符串是否在另一个字符串中：

tags = '|aa|ab|ae|af|ak|am|an|ar|...'
if mytag in tags:
    print "found"

还有其他方法吗？哪种方法最快，已经进行过测试了吗？如果没有，我该如何评估自己的水平（是从列表中随机选取一个元素还是选择最后一个元素进行测试？是否有人能提供一个“计时器”的Python代码）？

我认为元组比列表更快。然后只需要转换一次，查找就应该加速（当然，这只有在构建一次并多次使用时才有意义）。 - javex
1
@Tichodroma 在 Python 中的注释符号是 #。 - Eduard Florinescu
@javex 构建一次，多次使用 - Eduard Florinescu
@Javex 可能是这样，但是它们对于查找的效率都很差，它们每个都需要 O(N) 的时间，而集合几乎总是具有恒定的 O(1) 查找时间。注意给 OP 的提示：在 set(tags) 中检查 mytag 会破坏集合的目的，因为你每次都在构建一个新的集合。请确保在实际代码中不要这样做，只在初始时初始化集合。 - jamylak
6个回答
6
由于我无法访问原始字符串，任何测试都会有偏差。不过，你要求一个计时器吗？请查看设计用于计时代码片段的timeit模块。
请注意，如果您使用IPython，%timeit是一个魔法函数，可以轻松计时函数的执行，如下所示。
一些注释：
  • 你应该将Set替换为set...
  • 在运行任何测试之前，请构建您的set和长字符串。
  • 从您的tags列表中随机选择一个元素确实是正确的方法。
以下是在IPython中使用%timeit的示例：
tags = ['aa','ab','ae','af','ak','an','ar']
tags_set = set(tags)
tags_str = "|".join(tags)

%timeit 'ro' in tags
1000000 loops, best of 3: 223 ns per loop
%timeit 'ro' in tags_set
1000000 loops, best of 3: 73.5 ns per loop
%timeit 'ro' in tags_str
1000000 loops, best of 3: 98.1 ns per loop
1
我在列表中尝试了65780个元素，结果是843微秒（列表），54.6纳秒（集合），264微秒（字符串）。所以我肯定会选择使用集合。 - yilmazhuseyin
我遇到了错误 %timeit 'ro' in tags ^ SyntaxError: 无效的语法 - Eduard Florinescu
这是在控制台中使用%timeit的IPython语法。 - Christian Witts
@ChristianWitts 我已经成功让它工作了，现在我使用%cpaste并放置所有的代码。 - Eduard Florinescu
@yilmazhuseyin 我尝试使用IANA标签，得到了相同的结果，首先设置，其次是字符串，最后是列表，你可以看到我的答案。 - Eduard Florinescu
从列表转换为集合需要多长时间呢？ - davecom
2

这与时间或性能无关，但通过以不同的方式构建数据，您可能能够更早地不必担心这种情况。

从您之前的帖子中可以看出，您接受的答案包含一个函数iana_parse，该函数生成一个字典。因此，如果您在预解析时间知道要查找什么，那么可以执行以下操作：

looking_for = {'ro', 'xx', 'yy', 'zz'}
for res in iana_parse(data): # from previous post
    if res['Subtag'] in looking_for:
        print res['Subtag'], 'was found'

否则（或结合使用），您可以从该函数构建字典并使用它：
subtag_lookup = {rec['Subtag']:rec for rec in iana_parse(data)}

ro = subtag_lookup['ro']
print ro['Description']

如果你只需要子标签列表，请使用以下代码：

subtags = list(subtag_lookup)
1

您可以自行检查。只需使用timeit模块即可。

timeit.Timer()可能对您有用。

或者，您也可以使用time模块：-

import time
ct = time.clock()
if mytag in tags:
    print "found"
print "diff: ", time.clock() - ct
1

我更喜欢方案 #1。因为在比较之前，你不需要对列表进行额外的处理，所以它应该能够为你提供最佳性能。

至于如何测试性能... timeit 是你想要的。

import timeit
s1 = """
tags= ['aa', 'ab', 'ae', 'af', 'ak', 'am', 'an', 'ar']
mytag = 'ro'
if mytag in tags:
    print 'found'
"""
s2 = """
tags= ['aa', 'ab', 'ae', 'af', 'ak', 'am', 'an', 'ar']
mytag = 'ro'
if mytag in set(tags):
    print 'found'
"""
s3 = """
tags= ['aa', 'ab', 'ae', 'af', 'ak', 'am', 'an', 'ar']
mytag = 'ro'
if mytag in '|'.join(tags):
    print 'found'
"""

print(timeit.Timer(s1, 'gc.enable()').timeit())
print(timeit.Timer(s2, 'gc.enable()').timeit())
print(timeit.Timer(s3, 'gc.enable()').timeit())

>>> 
0.261634511713
0.476344575019
0.282574283666
对于 s3，您还计时了连接操作，这可能会影响基准测试。 - Eduard Florinescu
2
在第二个测试中，真正花费时间的是集合对象的初始化。而第三个测试则是字符串的拼接。你只需要为多个值创建这些对象一次。因此，可以说第二个和第三个测试对于多个值来说并不公平。 - yilmazhuseyin
1

我已使用此代码进行了测试，您可以在IPython控制台中使用%cpaste并粘贴以下代码。

#Get IANA language defs
import urllib
import pprint
import timeit
import IPython
import random
f = urllib.urlopen("http://www.iana.org/assignments/language-subtag-registry")
#lan.split("%%") .split("\n").split(":")
lan=f.read()
def iana_parse(data):
    for record in data.split("%%\n"):
        # skip empty records at file endings:
        if not record.strip():
            continue
        rec_data = {}
        for line in record.split("\n"):
#            key, value = line.split(":") doesn't work
            key, value = line.partition(':')[::2]
#            key, _, value = line.partition(':')
            rec_data[key.strip()] = value.strip() 
        yield rec_data

tags =[]

for k in iana_parse(lan):
#    print k
    if "Subtag" in k: tags.append(k["Subtag"])
#maybe store it in a shelve http://docs.python.org/library/shelve.html

tags_set = set(tags)
tags_str = "|".join(tags)
print "Search 'ro'" 
print "List:"
%timeit 'ro' in tags
print "Set:"
%timeit 'ro' in tags_set
print "String:"
%timeit 'ro' in tags_str

random_tag = tags[random.randint(0,len(tags)-1)]
print "Search random" 
print "List:"
%timeit random_tag in tags 
print "Set:"
%timeit random_tag in tags_set 
print "String:"
%timeit random_tag in tags_str

结果如下：

Search 'ro'
List: 1000000 loops, best of 3: 1.61 us per loop
Set: 10000000 loops, best of 3: 45.2 ns per loop
String: 1000000 loops, best of 3: 239 ns per loop

Search random
List:10000 loops, best of 3: 36.2 us per loop
Set:10000000 loops, best of 3: 50.9 ns per loop
String:100000 loops, best of 3: 4.88 us per loop

所以顺序是：

  1. 如果集合的初始化已经完成且不包括在测量中，则Set是最快的。
  2. 字符串解决方案测量第二个速度，也不包括连接在时间测量中。
  3. 令人惊讶的是，列表是最后一个。
1

对于一次性使用，选项＃1应该是最快的，因为它甚至不需要通过整个列表（构建集合需要通过整个列表）；而如果您只构建set()一次，则＃2将在所有后续运行中最快，因为它将在小常数时间内工作。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接