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.

+3


source to share


4 answers


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'])

      

+4


source


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.

+1


source


Installs on average O (1) membership tests and a nice interface.

0


source


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.

0


source







All Articles