在Python中使用Trie或Set
在Python中使用Trie或Set
提问于 2020-09-16 20:29:23
我有一张10万字的单子。如果我读到的单词存在于这个已知的单词列表中，我希望能够非常有效地搜索。在用Python实现时，我可以在Trie或Set中以哪种数据结构搜索得更快？
回答 3
Stack Overflow用户
发布于 2020-09-16 20:34:14
如果只是"in或not"，没有前缀或后缀之类的检查，只需使用set即可。它们是内置的，这本身就使它们更方便，而且比用Python手工实现的任何东西都要快。尝试有自己的位置，但是对于简单的成员资格测试，set在几乎所有情况下都会很好。不要过早地优化；如果它在set中运行得足够快，甚至没有理由考虑另一种选择。
Stack Overflow用户
发布于 2020-09-16 20:35:04
如果只需要检查一个单词是否已经存在，则set (哈希表)总是更好的。(摊销)时间复杂度是恒定的。
对于其他用例来说，trie是有意义的，例如找到以特定前缀开头的已经存在的单词。
Stack Overflow用户
发布于 2020-09-16 20:46:19
要与其他朋友的评论相提并论，set绝对更可取。
编写了此基准测试，将python set与marisa-trie进行比较，即：
的静态内存-高效的类Trie结构
结果几乎为10级，有利于set。
function [trie_performance_test] finished in 22 ms
function [set_performance_test] finished in 2 ms代码：
# pip install marisa-trie
import functools
from timeit import default_timer as timer
import marisa_trie
import requests
word_site = "http://svnweb.freebsd.org/csrg/share/dict/words?view=co&content-type=text/plain"
response = requests.get(word_site)
WORDS = [w.decode('utf8') for w in response.content.splitlines()]
def timeit(func):
@functools.wraps(func)
def newfunc(*args, **kwargs):
startTime = timer()
func(*args, **kwargs)
elapsedTime = timer() - startTime
print('function [{}] finished in {} ms'.format(
func.__name__, int(elapsedTime * 1000)))
return newfunc
@timeit
def trie_performance_test(words=WORDS):
trie = marisa_trie.Trie(words)
for key in words:
key_id = trie.get(key)
@timeit
def set_performance_test(words=WORDS):
words_set = set(words)
for key in words:
if key in words_set:
pass
trie_performance_test()
set_performance_test()页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/63927523
复制相关文章
相似问题
腾讯云开发者
