Does the set work like a dictionary without values?
This question is a python version: Is there a collection that works like a dictionary without values?
I need a data structure that has a list of English words, but not their definitions.
Basically: given a sequence of letters, I want to be able to do a constant O (1) search to determine if that sequence is in an English dictionary.
Will it be the right choice set()
or frozenset()
?
I know that I could use a dictionary where each key value is None
, but that seems like a waste of memory.
source to share
Yes, the set
right tool for the job. You can find out if a word is in the set with in
, which works O (1) times. Adding words is done with an element add
that takes O (1) amortized time. It also has all the usual finite set operations: union, intersection, difference, etc .:
>>> 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'])
source to share
Yes. Set your search to O (1) on average, much to my surprise. the implementation should be close to what you describe (a dictionary with dummy values). See also this related question .
For more information on timing complexities refer to:
http://wiki.python.org/moin/TimeComplexity
It is not built in or included in any module that I know of, but you might want to take a look at the Trie data structure if you need some of its properties in the future.
source to share
I don't know about Big-O, but here's what Python languages say about setting types :
Common uses for sets are to quickly test membership , remove duplicates from a sequence, and calculate mathematical operations such as intersection, union, difference, and symmetric difference.
source to share