Python 内置数据结构完全指南：list、dict、set 与 collections 深度解析

# 创建
lst = [1, 2, 3, 4, 5]
lst = list(range(1000))

# 访问（O(1)）
print(lst[0])      # 第一个
print(lst[-1])     # 最后一个（Pythonic！）
print(lst[2:5])    # 切片：[3, 4, 5]

# 修改（O(1)）
lst[0] = 100

# 末尾添加（均摊 O(1)）
lst.append(6)

# 插入（O(n)）—— 尽量避免在头部/中间插入
lst.insert(0, 0)   # 所有元素后移！

# 删除
lst.pop()          # 末尾弹出，O(1)
lst.pop(0)         # 头部弹出，O(n)！
lst.remove(3)      # 按值删除，O(n)

# 查找
try:
    idx = lst.index(42)   # O(n)
except ValueError:
    idx = -1

# 存在性检测
if 42 in lst:      # O(n)
    pass

# ❌ 非 Pythonic
result = []
for x in range(10):
    if x % 2 == 0:
        result.append(x ** 2)

# ✅ Pythonic
result = [x ** 2 for x in range(10) if x % 2 == 0]

# 字典推导式
squares = {x: x**2 for x in range(5)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

# 集合推导式
unique_squares = {x**2 for x in range(100)}  # 自动去重

# ❌ 陷阱 1：可变默认参数
def foo(x, items=[]):
    items.append(x)
    return items

foo(1)   # [1]
foo(2)   # [1, 2]   —— 同一个列表！

# ✅ 正确
from typing import List

def foo(x, items: List[int] = None):
    if items is None:
        items = []
    items.append(x)
    return items

# ❌ 陷阱 2：list 复制
a = [1, 2, [3, 4]]
b = a[:]        # 浅拷贝！b[2] is a[2]
c = a.copy()    # 同样是浅拷贝
import copy
d = copy.deepcopy(a)  # 深拷贝

# ❌ 陷阱 3：循环中修改列表
for item in lst:
    if item < 0:
        lst.remove(item)   # ❌ 修改正在迭代的列表

# ✅ 正确：用列表推导式或倒序删除
lst = [x for x in lst if x >= 0]
# 或
for i in range(len(lst) - 1, -1, -1):
    if lst[i] < 0:
        lst.pop(i)

# 预分配空间（大数据量时有用）
lst = [None] * 10000
for i in range(10000):
    lst[i] = i * 2

# 使用 array 模块存储同类型数据（更省内存）
from array import array
numbers = array('i', [1, 2, 3, 4, 5])   # 'i' = signed int

# 内存占用对比
import sys
py_list = [0] * 1000
arr = array('i', [0] * 1000)
print(f"list: {sys.getsizeof(py_list)} bytes")
print(f"array: {sys.getsizeof(arr)} bytes")

# 1. 作为 dict 的 key（需要不可变）
locations = {
    (39.9, 116.4): "北京",
    (31.2, 121.5): "上海",
}

# 2. 解构赋值（比 list 更清晰）
point = (3, 4)
x, y = point

# 3. 函数多返回值
def get_min_max(nums):
    return min(nums), max(nums)

minimum, maximum = get_min_max([3, 1, 4, 1, 5])

# 4. 比 list 更省内存、更快
import sys
lst = [1, 2, 3]
t = (1, 2, 3)
print(sys.getsizeof(lst))   # 88 bytes
print(sys.getsizeof(t))     # 72 bytes

from collections import namedtuple

# 创建具名元组类
Person = namedtuple('Person', ['name', 'age', 'email'])

# 使用
alice = Person(name='Alice', age=25, email='alice@example.com')
print(alice.name)    # Alice（比 alice[0] 清晰多了）

# 可以替换字段
bob = alice._replace(name='Bob', age=30)

# 从 dict 创建
data = {'name': 'Charlie', 'age': 35, 'email': 'charlie@example.com'}
charlie = Person(**data)

from dataclasses import dataclass

@dataclass(frozen=True)   # frozen=True 使其不可变
class Person:
    name: str
    age: int
    email: str
    
alice = Person(name='Alice', age=25, email='alice@example.com')
print(alice.name)

# 创建
d = {'a': 1, 'b': 2}
d = dict(a=1, b=2)
d = {x: x**2 for x in range(5)}   # 字典推导式

# 访问（O(1)）
print(d['a'])           # 1
d['c'] = 3              # 添加/修改

# 安全访问
print(d.get('z', 0))    # 0（不存在时返回默认值）

# 存在性检测
if 'a' in d:            # O(1)
    pass

# 删除
del d['a']
popped = d.pop('b')     # 删除并返回值

# 遍历
for key in d:           # 等价于 for key in d.keys():
    print(key)

for key, value in d.items():
    print(f"{key}: {value}")

for value in d.values():
    print(value)

# Python 3.7+ 起，dict 保留插入顺序（语言规范保证）
d = {}
d['first'] = 1
d['second'] = 2
d['third'] = 3

print(list(d.keys()))   # ['first', 'second', 'third']

d1 = {'a': 1, 'b': 2}
d2 = {'b': 3, 'c': 4}

# | 合并（d2 覆盖 d1 的重复键）
merged = d1 | d2   # {'a': 1, 'b': 3, 'c': 4}

# |= 就地更新
d1 |= d2           # d1 变为 {'a': 1, 'b': 3, 'c': 4}

# 1. 用 setdefault 统计
char_count = {}
for char in "hello world":
    char_count.setdefault(char, 0)
    char_count[char] += 1

# 2. 用 collections.Counter 更简单
from collections import Counter
char_count = Counter("hello world")

# 3. 多级字典（需要默认值）
# ❌ 手动检查
if 'users' not in data:
    data['users'] = {}
if 'alice' not in data['users']:
    data['users']['alice'] = []
data['users']['alice'].append('action1')

# ✅ 用 defaultdict
from collections import defaultdict
data = defaultdict(lambda: defaultdict(list))
data['users']['alice'].append('action1')   # 自动创建中间层级

# 创建
s = {1, 2, 3, 3, 3}     # {1, 2, 3} —— 自动去重
s = set([1, 2, 2, 3])   # {1, 2, 3}

# 添加/删除
s.add(4)
s.remove(2)             # KeyError if not found
s.discard(999)          # 不报错

# 存在性检测（O(1)）
if 3 in s:
    pass

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

# 并集
print(a | b)            # {1, 2, 3, 4, 5, 6}
print(a.union(b))

# 交集
print(a & b)            # {3, 4}
print(a.intersection(b))

# 差集
print(a - b)            # {1, 2}（在 a 中但不在 b 中）
print(a.difference(b))

# 对称差集（只在一边出现的）
print(a ^ b)            # {1, 2, 5, 6}
print(a.symmetric_difference(b))

# 子集/超集
print(a <= b)           # False（a 是 b 的子集？）
print({1, 2} <= a)      # True

def unique_ordered(items):
    """去重并保持原始顺序"""
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

# Python 3.7+（dict 有序）
def unique_ordered_v2(items):
    return list(dict.fromkeys(items))

# 测试
data = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(unique_ordered(data))      # [3, 1, 4, 5, 9, 2, 6]
print(unique_ordered_v2(data))   # [3, 1, 4, 5, 9, 2, 6]

from collections import Counter

# 统计字符频率
text = "hello world"
count = Counter(text)
print(count)            # Counter({'l': 3, 'o': 2, 'h': 1, ...})
print(count.most_common(3))   # [('l', 3), ('o', 2), ('h', 1)]

# 统计单词
words = "the quick brown fox jumps over the lazy dog".split()
word_count = Counter(words)
print(word_count.most_common(2))   # [('the', 2), ('quick', 1)]

# 集合运算
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2, c=3)
print(c1 + c2)   # Counter({'a': 4, 'b': 3, 'c': 3})
print(c1 - c2)   # Counter({'a': 2}) —— 只保留正数

from collections import deque

# deque 两端操作都是 O(1)，list 头部操作是 O(n)
d = deque([1, 2, 3, 4, 5])

# 右端操作（和 list 一样）
d.append(6)           # deque([1, 2, 3, 4, 5, 6])
d.pop()               # 6

# 左端操作（O(1)！）
d.appendleft(0)       # deque([0, 1, 2, 3, 4, 5])
d.popleft()           # 0

# 旋转
d.rotate(1)           # 向右旋转 1 位
d.rotate(-2)          # 向左旋转 2 位

# 定长队列（自动丢弃旧元素）
cache = deque(maxlen=3)
cache.append(1)
cache.append(2)
cache.append(3)
cache.append(4)       # 自动丢弃 1
cache                 # deque([2, 3, 4], maxlen=3)

from collections import defaultdict

# 场景 1：按首字母分组
words = ['apple', 'bat', 'bar', 'atom', 'book']
by_letter = defaultdict(list)
for word in words:
    by_letter[word[0]].append(word)

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

# 场景 2：计数（比 Counter 更灵活）
counts = defaultdict(int)
for word in words:
    counts[word[0]] += 1

# 场景 3：树形结构
Tree = lambda: defaultdict(Tree)
tree = Tree()
tree['users']['alice']['age'] = 25

from collections import OrderedDict

# Python 3.7+ 的普通 dict 已经有序，OrderedDict 主要用于：
# 1. 明确表达"顺序重要"的意图
# 2. 使用 move_to_end 等方法

d = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
d.move_to_end('a')    # 把 'a' 移到最后

from collections import ChainMap

# 合并多个字典查找（不复制数据）
defaults = {'theme': 'dark', 'language': 'en'}
user_prefs = {'theme': 'light'}

config = ChainMap(user_prefs, defaults)
print(config['theme'])      # 'light'（从第一个 dict 找到）
print(config['language'])   # 'en'（从第二个 dict 找到）

# 用于参数解析：命令行 > 环境变量 > 配置文件
cmd_args = {'verbose': True}
env_vars = {'output_dir': '/tmp'}
config_file = {'output_dir': './output'}

settings = ChainMap(cmd_args, env_vars, config_file)
print(settings['verbose'])      # True（命令行）
print(settings['output_dir'])   # /tmp（环境变量覆盖配置文件）

from collections import Counter
import re

# 日志格式：192.168.1.1 - - [12/Aug/2024 ...]
IP_PATTERN = re.compile(r'^(\d+\.\d+\.\d+\.\d+)')

def analyze_ips(logfile):
    ip_counter = Counter()
    
    with open(logfile) as f:
        for line in f:
            m = IP_PATTERN.match(line)
            if m:
                ip_counter[m.group(1)] += 1
    
    return ip_counter.most_common(10)

from collections import OrderedDict

class LRUCache:
    """使用 OrderedDict 实现 LRU Cache"""
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()
    
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key: int, value: int) -> None:
        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)

# Python 3.2+ 更简单的实现
from functools import lru_cache

@lru_cache(maxsize=128)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

from collections import defaultdict
import json

def nested_dict():
    return defaultdict(nested_dict)

def load_config(path):
    with open(path) as f:
        data = json.load(f)
    
    config = nested_dict()
    
    def merge(d, keys=()):
        for k, v in d.items():
            new_keys = keys + (k,)
            if isinstance(v, dict):
                merge(v, new_keys)
            else:
                target = config
                for key in keys:
                    target = target[key]
                target[k] = v
    
    merge(data)
    return config

from collections import deque
from typing import List

def max_sliding_window(nums: List[int], k: int) -> List[int]:
    """O(n) 时间求滑动窗口最大值"""
    result = []
    dq = deque()   # 存索引，保持单调递减
    
    for i, num in enumerate(nums):
        # 移除窗口外的元素
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 保持单调递减：移除所有小于当前元素的
        while dq and nums[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # 窗口填满后开始输出
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(max_sliding_window(nums, k))   # [3, 3, 5, 5, 6, 7]