# Python collections 模块

## 学习目标
- 掌握 `namedtuple` 创建命名元组
- 学会使用 `Counter` 统计频率
- 理解 `defaultdict` 的默认工厂机制
- 掌握 `deque` 双端队列和 `OrderedDict`

---

## 1. namedtuple 命名元组

`namedtuple` 创建带有命名字段的元组子类，兼具元组的不可变性和类的可读性。

```python
from collections import namedtuple

# 定义命名元组
Point = namedtuple('Point', ['x', 'y'])

# 创建实例
p = Point(10, 20)
print(p)           # Point(x=10, y=20)
print(p.x, p.y)    # 10 20
print(p[0], p[1])  # 10 20（也可用索引）

# 解包
x, y = p
print(f"x={x}, y={y}")

# 不可变性
# p.x = 100  # AttributeError
```

### 1.1 实际应用

```python
from collections import namedtuple

# 定义员工
Employee = namedtuple('Employee', ['name', 'department', 'salary'])

employees = [
    Employee("Alice", "Engineering", 80000),
    Employee("Bob", "Sales", 60000),
    Employee("Charlie", "Engineering", 90000),
]

# 访问更清晰
for emp in employees:
    print(f"{emp.name} 在 {emp.department} 部门，薪水 ${emp.salary}")

# 转换为字典
emp_dict = emp._asdict()
print(emp_dict)

# 替换字段（创建新实例）
new_emp = emp._replace(salary=95000)
print(new_emp)
```

---

## 2. Counter 计数器

`Counter` 是字典的子类，用于计数可哈希对象。

```python
from collections import Counter

# 统计字符频率
text = "abracadabra"
counter = Counter(text)
print(counter)
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})

# 获取最常见的
print(counter.most_common(3))  # [('a', 5), ('b', 2), ('r', 2)]

# 访问不存在的元素返回 0
print(counter['z'])  # 0
```

### 2.1 Counter 运算

```python
from collections import Counter

a = Counter(['a', 'b', 'a', 'c'])
b = Counter(['a', 'b', 'b', 'd'])

print("a:", a)  # Counter({'a': 2, 'b': 1, 'c': 1})
print("b:", b)  # Counter({'b': 2, 'a': 1, 'd': 1})

# 加法（合并计数）
print("a + b:", a + b)  # Counter({'a': 3, 'b': 3, 'c': 1, 'd': 1})

# 减法
print("a - b:", a - b)  # Counter({'a': 1, 'c': 1})

# 交集（取最小值）
print("a & b:", a & b)  # Counter({'a': 1, 'b': 1})

# 并集（取最大值）
print("a | b:", a | b)  # Counter({'a': 2, 'b': 2, 'c': 1, 'd': 1})
```

### 2.2 实际应用

```python
from collections import Counter
import re

# 统计单词频率
text = """
Python is great. Python is easy. 
Python is powerful and Python is popular.
"""

words = re.findall(r'\b\w+\b', text.lower())
word_count = Counter(words)

print("单词频率:")
for word, count in word_count.most_common(5):
    print(f"  {word}: {count}")

# 统计列表元素
colors = ['red', 'blue', 'green', 'red', 'blue', 'red']
color_count = Counter(colors)
print(f"\n颜色统计: {color_count}")
```

---

## 3. defaultdict 默认字典

`defaultdict` 在访问不存在的键时，会自动创建默认值。

```python
from collections import defaultdict

# 普通字典的问题
d = {}
# d['a'].append(1)  # KeyError!

# 使用 defaultdict
d = defaultdict(list)
d['a'].append(1)
d['a'].append(2)
d['b'].append(3)
print(dict(d))  # {'a': [1, 2], 'b': [3]}

# 默认值为 int（计数）
count = defaultdict(int)
for char in 'abracadabra':
    count[char] += 1
print(dict(count))

# 默认值为 set
d = defaultdict(set)
d['fruits'].add('apple')
d['fruits'].add('banana')
d['fruits'].add('apple')  # 重复被忽略
print(dict(d))  # {'fruits': {'apple', 'banana'}}
```

### 3.1 实际应用：分组

```python
from collections import defaultdict

# 按首字母分组
words = ['apple', 'bat', 'bar', 'atom', 'book', 'candy']
by_first_letter = defaultdict(list)

for word in words:
    by_first_letter[word[0]].append(word)

print(dict(by_first_letter))
# {'a': ['apple', 'atom'], 'b': ['bat', 'bar', 'book'], 'c': ['candy']}

# 按长度分组
by_length = defaultdict(list)
for word in words:
    by_length[len(word)].append(word)

print(dict(by_length))
# {5: ['apple'], 3: ['bat', 'bar', 'book'], 4: ['atom'], 5: ['candy']}
```

---

## 4. deque 双端队列

`deque`（double-ended queue）支持从两端快速添加和删除元素。

```python
from collections import deque

# 创建
d = deque([1, 2, 3, 4, 5])
print(d)  # deque([1, 2, 3, 4, 5])

# 右端操作
d.append(6)       # 右侧添加
d.pop()           # 右侧删除

# 左端操作
d.appendleft(0)   # 左侧添加
d.popleft()       # 左侧删除

print(d)  # deque([1, 2, 3, 4, 5])
```

### 4.1 deque 进阶

```python
from collections import deque

# 指定最大长度（超出时自动从另一端删除）
d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
print(d)  # deque([1, 2, 3])

d.append(4)  # 超出长度，左侧 1 被删除
print(d)     # deque([2, 3, 4])

# 旋转
d = deque([1, 2, 3, 4, 5])
d.rotate(2)   # 向右旋转2位
print(d)      # deque([4, 5, 1, 2, 3])

d.rotate(-1)  # 向左旋转1位
print(d)      # deque([5, 1, 2, 3, 4])

# 清空
d.clear()
print(d)  # deque([])
```

### 4.2 与列表的性能对比

```python
from collections import deque
import time

# deque 左端添加更快
d = deque()
l = []

# deque 左端添加
start = time.time()
for i in range(100000):
    d.appendleft(i)
print(f"deque appendleft: {time.time() - start:.4f}s")

# list 左端添加（很慢）
start = time.time()
for i in range(100000):
    l.insert(0, i)
print(f"list insert(0): {time.time() - start:.4f}s")
```

---

## 5. OrderedDict 有序字典

`OrderedDict` 保持键值对的插入顺序（Python 3.7+ 普通 dict 也保持顺序，但 OrderedDict 有额外功能）。

```python
from collections import OrderedDict

# 创建有序字典
od = OrderedDict()
od['a'] = 1
od['b'] = 2
od['c'] = 3

print(od)  # OrderedDict([('a', 1), ('b', 2), ('c', 3)])

# 移动到末尾
od.move_to_end('a')
print(od)  # OrderedDict([('b', 2), ('c', 3), ('a', 1)])

# 移动到开头
od.move_to_end('c', last=False)
print(od)  # OrderedDict([('c', 3), ('b', 2), ('a', 1)])

# 反转
print(reversed(od))  # 反转迭代器
```

### 5.1 实现 LRU Cache

```python
from collections import OrderedDict

class LRUCache:
    """简单 LRU 缓存实现"""
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    
    def get(self, key):
        if key not in self.cache:
            return -1
        # 移动到末尾（最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 删除最久未使用的（第一个）
            self.cache.popitem(last=False)
    
    def __repr__(self):
        return f"LRUCache({dict(self.cache)})"

# 使用
cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache)  # LRUCache({1: 'a', 2: 'b'})

cache.get(1)  # 使用 1
cache.put(3, "c")  # 2 被淘汰
print(cache)  # LRUCache({1: 'a', 3: 'c'})
```

---

## 6. ChainMap 链式映射

`ChainMap` 将多个字典组合在一起，查找时按顺序遍历。

```python
from collections import ChainMap

# 组合多个字典
defaults = {'theme': 'light', 'language': 'en'}
user_prefs = {'theme': 'dark'}

# 用户设置优先于默认设置
settings = ChainMap(user_prefs, defaults)

print(settings['theme'])     # dark（来自 user_prefs）
print(settings['language'])  # en（来自 defaults）
print(dict(settings))        # {'theme': 'dark', 'language': 'en'}

# 添加新值到第一个映射
settings['font'] = 'Arial'
print(user_prefs)  # {'theme': 'dark', 'font': 'Arial'}
```

---

## 本节小结

- **namedtuple**：创建带名字的元组，提高代码可读性
- **Counter**：快速统计元素频率，支持数学运算
- **defaultdict**：自动提供默认值的字典，避免 KeyError
- **deque**：双端队列，两端操作 O(1)，支持 maxlen
- **OrderedDict**：有序字典，支持 move_to_end
- **ChainMap**：链式组合多个字典，不复制数据

---

## 练习

1. 使用 `Counter` 统计一段文本中每个汉字出现的频率
2. 使用 `defaultdict` 实现一个多级字典（字典的字典）
3. 使用 `deque` 实现一个滑动窗口平均值计算器
4. 使用 `namedtuple` 重构你项目中的简单数据类