集合

# 用花括号（注意：空 {} 是字典，不是集合）
s = {1, 2, 3, 3, 3}
print s             # set([1, 2, 3])，重复自动去重

# 用 set() 构造函数
s = set([1, 2, 3, 3])
print s             # set([1, 2, 3])

# 空集合（必须用 set()）
empty = set()
print type(empty)   # <type 'set'>

not_set = {}        # 这是空字典！
print type(not_set) # <type 'dict'>

s = {1, 2, 3}

# 添加单个元素
s.add(4)
print s             # set([1, 2, 3, 4])

# 添加已存在的元素，无效果
s.add(3)
print s             # set([1, 2, 3, 4])

# 删除元素
s.remove(3)
print s             # set([1, 2, 4])

# remove 不存在的元素会报错
s.remove(10)        # KeyError: 10

# discard：删除元素，不存在不报错
s.discard(10)
print s             # 无变化

# pop()：删除并返回任意元素
item = s.pop()
print item          # 1（或其他元素，顺序不确定）

# clear()：清空
s.clear()
print s             # set([])

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

# 并集：在 a 或 b 中的元素
print a | b         # set([1, 2, 3, 4, 5, 6])
print a.union(b)    # 同上

# 交集：同时在 a 和 b 中的元素
print a & b         # set([3, 4])
print a.intersection(b)  # 同上

# 差集：在 a 中但不在 b 中的元素
print a - b         # set([1, 2])
print a.difference(b)      # 同上

# 对称差集：只在 a 或只在 b 中的元素
print a ^ b         # set([1, 2, 5, 6])
print a.symmetric_difference(b)  # 同上

# 子集和超集
print a <= b        # False，a 不是 b 的子集
print {3, 4} <= a   # True
print a >= {1, 2}  # True

nums = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(nums))
print unique        # [1, 2, 3, 4]（顺序可能不同）

# 保留顺序的去重
seen = set()
result = []
for x in nums:
    if x not in seen:
        seen.add(x)
        result.append(x)
print result        # [1, 2, 3, 4]

# 列表查找是 O(n)
large_list = range(1000000)
print 999999 in large_list      # 慢，需要遍历

# 集合查找是 O(1)
large_set = set(large_list)
print 999999 in large_set       # 快，哈希查找

# 两个列表是否有共同元素
list1 = [1, 2, 3]
list2 = [3, 4, 5]

# 低效：O(n*m)
has_common = any(x in list2 for x in list1)

# 高效：O(n+m)
has_common = not set(list1).isdisjoint(list2)

# 平方集合（自动去重）
squares = {x**2 for x in range(10)}
print squares       # set([0, 1, 4, 81, 64, 9, 16, 49, 25, 36])

# 过滤
odds = {x for x in range(20) if x % 2 == 1}
print odds          # set([1, 3, 5, 7, 9, 11, 13, 15, 17, 19])

# frozenset 作为字典键
locations = {
    frozenset(["a", "b"]): "edge AB",
    frozenset(["b", "c"]): "edge BC",
}

# 普通 set 不能作为键
# d = {set([1, 2]): "A"}    # TypeError: unhashable type: 'set'

# frozenset 支持所有查询操作，不支持修改
fs = frozenset([1, 2, 3])
print 2 in fs       # True
print fs | {3, 4}   # frozenset([1, 2, 3, 4])
# fs.add(5)         # AttributeError: 'frozenset' object has no attribute 'add'