一个集合是否像一个没有值的字典？

Question

这个问题是关于Python版本的：Is there a Collection that works like a Dictionary without the values? 我需要一个数据结构，其中包含英文单词列表，但不包含它们的定义。

基本上，给定一串字母，我希望能够进行常数时间O(1)的查找，以确定该序列是否在英语词典中。

使用set()或frozenset()是否是正确的选择？

我知道我可以使用字典，其中每个键的值为None，但这似乎浪费了内存空间。

- zzz

---

“给定一系列字母”是什么意思？假设你的词典中有一个单词“apocalypse”，你希望通过查找“apoca”或“lypse”来得到真实结果吗？ - tomasz

Answer 1

是的，set是处理这个任务的正确工具。您可以使用in来查找一个单词是否在集合中，这个操作的时间复杂度为O(1)。添加单词使用add成员完成，其平摊时间复杂度为O(1)。此外，它还具有所有常见的有限集操作：并集、交集、差集等。

>>> A = set(["foo", "bar", "baz"])
>>> B = set(["foo", "ham", "spam"])
>>> "foo" in A
True
>>> "bar" in B
False
>>> A | B
set(['bar', 'ham', 'spam', 'foo', 'baz'])
>>> A & B
set(['foo'])
>>> A - B
set(['bar', 'baz'])
>>> B - A
set(['ham', 'spam'])

- Fred Foo

---

我有些困惑：使用re相比使用in有什么优势呢？ - bluepnume

@bluepnume：它占用更少的内存。因为它很明显会分散注意力，所以把它删除了。 - Fred Foo

Answer 2

是的。在平均情况下，设置查找是O(1)，这让我非常惊讶。 实现应该接近您描述的内容（带有虚拟值的字典）。另请参见此相关问题。

有关时间复杂性的更多信息，请参阅：

http://wiki.python.org/moin/TimeComplexity

我不知道任何一个内建或者模块中包含它的，但是如果你将来需要使用一些类似的属性，也许你应该研究一下Trie数据结构。

- Eduardo Ivanec

---

这是一个打字错误。链接确实显示了正确的信息。很抱歉，我应该先校对一下。 - Eduardo Ivanec

啊，现在好多了解 :) - Niklas B.

Answer 3

集合拥有O(1)的成员测试平均时间复杂度和良好的接口。

- miku

Answer 4

我不知道Big-O是什么，但这是Python语言参考手册关于set types的说法：

常见的集合用途包括快速成员测试、从序列中删除重复项以及计算数学运算，如交集、并集、差集和对称差集。

- Rik Poggi