尚未翻译
本页面尚未翻译成中文，因此显示英文原文。 帮助翻译
Frozenset Operations Complexity¶
The frozenset type is an immutable set that can be hashed and used as a dictionary key or set member.
Complexity Reference¶
| Operation | Time | Space | Notes |
|---|---|---|---|
frozenset(iterable) |
O(n) | O(n) | Create from iterable |
len() |
O(1) | O(1) | Direct count |
in (membership) |
O(1) avg, O(n) worst | O(1) | Hash lookup; worst case with hash collisions |
union(\|) |
O(n+m) | O(n+m) | Combine sets |
intersection(&) |
O(min(n,m)) | O(min(n,m)) | Common elements |
difference(-) |
O(n) | O(n) | Elements in first |
symmetric_difference(^) |
O(n+m) | O(n+m) | Exclusive elements |
issubset() |
O(n) | O(1) | Check containment |
issuperset() |
O(m) | O(1) | Check containment |
isdisjoint() |
O(min(n,m)) | O(1) | Check overlap |
copy() |
O(1) | O(1) | Returns same object (immutable) |
hash() |
O(n) first call, O(1) cached | O(1) | Hash value computed once, then cached |
frozenset(set) |
O(n) | O(n) | Convert from set |
Implementation Details¶
Hashability¶
# Frozenset is hashable - can be used as dict key
fs1 = frozenset([1, 2, 3])
fs2 = frozenset([4, 5, 6])
d = {fs1: 'first', fs2: 'second'} # Works!
s = {fs1, fs2} # Works!
# Set is not hashable
regular_set = {1, 2, 3}
d[regular_set] = 'value' # TypeError: unhashable type
Immutability Benefits¶
# Frozenset is immutable and hashable
fs = frozenset([1, 2, 3])
# Can be dictionary key
cache = {fs: 'result'}
# Can be in another set
nested = {fs, frozenset([4, 5])}
# Hash is stable (doesn't change)
h1 = hash(fs)
# ... time passes ...
h2 = hash(fs)
assert h1 == h2 # Always true
Performance Considerations¶
Copy is O(1)¶
# Frozenset copy returns same object (since immutable)
fs1 = frozenset([1, 2, 3])
fs2 = frozenset(fs1)
print(fs1 is fs2) # True - same object!
# Contrast with set
s1 = {1, 2, 3}
s2 = set(s1)
print(s1 is s2) # False - different objects
Set Operations¶
# Union: O(n+m)
fs1 = frozenset([1, 2, 3])
fs2 = frozenset([3, 4, 5])
fs3 = fs1 | fs2 # O(n+m)
# Intersection: O(min(n,m))
fs4 = fs1 & fs2 # O(min(n,m))
# Difference: O(n)
fs5 = fs1 - fs2 # O(n)
# All create new frozensets
Use Cases¶
As Dictionary Keys¶
from collections import Counter
# Count coordinate pairs - frozenset as key
moves = [(0, 1), (1, 0), (0, 1), (1, 0), (0, 1)]
move_counts = Counter(tuple(m) for m in moves)
# Or with frozenset for unordered pairs
edges = frozenset([(0, 1), (2, 3), (0, 1)])
print(len(edges)) # 2 - duplicate removed
In Graph Algorithms¶
# Store visited states as frozensets
def dfs(node, visited=None):
if visited is None:
visited = frozenset()
visited = visited | {node} # O(n+1)
# ... process node ...
for neighbor in node.neighbors:
if neighbor not in visited: # O(1)
dfs(neighbor, visited)
Function Memoization¶
from functools import lru_cache
@lru_cache(maxsize=128)
def process_items(items):
# items must be hashable - use frozenset
return sum(items)
# Calling with frozenset
result = process_items(frozenset([1, 2, 3])) # O(1) hash
Memory Considerations¶
import sys
# Frozenset overhead
fs = frozenset([1, 2, 3])
print(sys.getsizeof(fs)) # ~216+ bytes
# Similar to set
s = {1, 2, 3}
print(sys.getsizeof(s)) # ~216+ bytes
# Immutable, so can be shared
fs1 = frozenset([1, 2, 3])
fs2 = frozenset(fs1) # Same object, no copy
print(fs1 is fs2) # True
Comparison with Set¶
| Operation | Set | Frozenset |
|---|---|---|
| Hashable | No | Yes |
| Mutable | Yes | No |
| Dict key | No | Yes |
| Copy cost | O(n) | O(1) |
| Hash cost | - | O(1) |
| Memory | Similar | Similar |
Version Notes¶
- All Python 3.x: Core complexity unchanged
- Python 3.5+: Some optimization improvements