Set vs. frozenset performance
The frozenset
and set
implementations are largely shared; a set
is simply a frozenset
with mutating methods added, with the exact same hashtable implementation. See the Objects/setobject.c
source file; the top-level PyFrozenSet_Type
definition shares functions with the PySet_Type
definition.
There is no optimisation for a frozenset here, as there is no need to calculate the hashes for the items in the frozenset
when you are testing for membership. The item that you use to test against the set still needs to have their hash calculated, in order to find the right slot in the set hashtable so you can do an equality test.
As such, your timing results are probably off due to other processes running on your system; you measured wall-clock time, and did not disable Python garbage collection nor did you repeatedly test the same thing.
Try to run your test using the timeit
module, with one value from numbers
and one not in the set:
import randomimport sysimport timeitnumbers = [random.randrange(sys.maxsize) for _ in range(10000)]set_ = set(numbers)fset = frozenset(numbers)present = random.choice(numbers)notpresent = -1test = 'present in s; notpresent in s'settime = timeit.timeit( test, 'from __main__ import set_ as s, present, notpresent')fsettime = timeit.timeit( test, 'from __main__ import fset as s, present, notpresent')print('set : {:.3f} seconds'.format(settime))print('frozenset: {:.3f} seconds'.format(fsettime))
This repeats each test 1 million times and produces:
set : 0.050 secondsfrozenset: 0.050 seconds
The reason for the two different datatypes is not for performance, it is functional. Because frozensets are immutable they can be used as a key in dictionaries. Sets cannot be used for this purpose.