blocks|key|1599150|text|如果只是"in或not"，没有前缀或后缀之类的检查，只需使用set即可。它们是内置的，这本身就使它们更方便，而且比用Python手工实现的任何东西都要快。尝试有自己的位置，但是对于简单的成员资格测试，set在几乎所有情况下都会很好。不要过早地优化；如果它在set中运行得足够快，甚至没有理由考虑另一种选择。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1599151|entityMap^0|U|3|2S|3|3K|3|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|O|8|@]|D|@]|E|$]]]|G|$]]

If it's just &quot;in or not&quot;, no checking by prefix or suffix or anything, just use a <code>set</code>. They're built-in, which by itself makes them more convenient, and they're faster than anything you'll implement by hand in Python. Tries have their place, but for simple membership tests, <code>set</code>s will be just fine in almost all cases. Don't prematurely optimize; if it works fast enough with a <code>set</code>, there's no reason to even consider another option.

blocks|key|1599186|text|如果只需要检查一个单词是否已经存在，则set+(哈希表)总是更好的。(摊销)时间复杂度是恒定的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1599187|对于其他用例来说，trie是有意义的，例如找到以特定前缀开头的已经存在的单词。|1599188|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

A set (hash table) is always better if you just need to check if a word already exists. The (amortized) time complexity is constant. 
A trie makes sense for other use cases, such as finding words that already exist that start with certain prefix.

blocks|key|1599202|text|要与其他朋友的评论相提并论，set绝对更可取。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1599203|编写了此基准测试，将python+set与marisa-trie进行比较，即：|1599204|1599205|的静态内存-高效的类Trie结构|blockquote|1599206|1599207|1599208|结果几乎为10级，有利于set。|1599209|function+[trie_performance_test]+finished+in+22+ms
function+[set_performance_test]+finished+in+2+ms|code-block|syntax|javascript|1599210|代码：|1599211|#+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()|1599212|entityMap^0|E|3|0|H|3|L|B|0|0|0|0|0|C|3|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@$9|11|A|12|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|13|8|@$9|14|A|15|B|C]|$9|16|A|17|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|18|8|@]|D|@]|E|$]]|$1|I|3|J|5|K|7|19|8|@]|D|@]|E|$]]|$1|L|3|-4|5|6|7|1A|8|@]|D|@]|E|$]]|$1|M|3|-4|5|6|7|1B|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|1C|8|@$9|1D|A|1E|B|C]]|D|@]|E|$]]|$1|P|3|Q|5|R|7|1F|8|@]|D|@]|E|$S|T]]|$1|U|3|V|5|6|7|1G|8|@]|D|@]|E|$]]|$1|W|3|X|5|R|7|1H|8|@]|D|@]|E|$S|T]]|$1|Y|3|-4|5|6|7|1I|8|@]|D|@]|E|$]]]|Z|$]]

To add up to what other friends have commented, <code>set</code> is definitely preferable.
Written this benchmark comparing python <code>set</code> to <code>marisa-trie</code> which is:
<blockquote>
Static memory-efficient Trie-like structures for Python
</blockquote>
The results are almost 10 magnitude in favor of <code>set</code>:
<pre><code>function [trie_performance_test] finished in 22 ms
function [set_performance_test] finished in 2 ms
</code></pre>
Code:
<pre><code>
# pip install marisa-trie
import functools
from timeit import default_timer as timer

import marisa_trie

import requests

word_site = &quot;http://svnweb.freebsd.org/csrg/share/dict/words?view=co&amp;content-type=text/plain&quot;

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()
</code></pre>

I have a list of 100k words. I wish to search very efficiently if a word I read exists in this known list of words. Which of the two data structures can I search faster in a Trie or a Set while implementing in Python?

Trie or Set in Python

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一张10万字的单子。如果我读到的单词存在于这个已知的单词列表中，我希望能够非常有效地搜索。在用Python实现时，我可以在Trie或Set中以哪种数据结构搜索得更快？

问在Python中使用Trie或Set
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python中使用Trie或SetEN