Python数据结构深度解析

数据结构选择策略与性能分析

数据结构选择是程序优化的关键决策。Python的四大内置数据结构在内存布局、访问模式和时间复杂度上各有特点，理解这些特性对后续学习NumPy数值计算和Pandas数据结构的性能优化至关重要。

数据结构技术特性对比

特性对比表:

list - 动态数组的内部机制

技术定义: Python的list是一个基于动态数组(dynamic array)实现的可变序列容器，内部存储PyObject指针，支持均摇常数时间的末尾插入和删除操作。

内存模型: 采用连续内存布局，元素是指向实际对象的指针，可存储不同类型对象。预分配机制避免频繁内存重分配。

创建与初始化机制

# 不同创建方式的性能对比
import sys

# 1. 字面量创建 - 编译时优化
data_literal = [1, 2, 3, 4, 5]
print(f"字面量列表内存: {sys.getsizeof(data_literal)} bytes")

# 2. 构造函数创建 - 运行时分配
data_constructor = list(range(1, 6))
print(f"构造函数列表内存: {sys.getsizeof(data_constructor)} bytes")

# 3. 列表推导式 - 性能取决于构造任务与运行环境
data_comprehension = [x for x in range(1, 6)]
print(f"推导式列表内存: {sys.getsizeof(data_comprehension)} bytes")

# 内存预分配机制演示
empty_list = []
print(f"空列表初始长度: {len(empty_list)}, 内存: {sys.getsizeof(empty_list)}")

for i in range(10):
    empty_list.append(i)
    if i in [0, 3, 7, 9]:
        print(f"添加{i+1}个元素后 - 长度: {len(empty_list)}, 内存: {sys.getsizeof(empty_list)}")

# 数据类型混合存储 - PyObject指针数组
mixed_data = [
    42,                    # int对象指针
    3.14159,              # float对象指针
    "data_science",       # str对象指针
    [1, 2, 3],           # list对象指针
    {'key': 'value'}     # dict对象指针
]
print(f"混合类型列表内存开销: {sys.getsizeof(mixed_data)} bytes")

# 索引操作的时间复杂度分析
test_data = list(range(1000000))  # 100万元素

# O(1) 随机访问
import time
start = time.time()
value = test_data[500000]  # 中间位置访问
end = time.time()
print(f"随机访问时间: {(end-start)*1000:.6f} ms")

# O(n) 成员测试
start = time.time()
exists = 500000 in test_data  # 线性查找
end = time.time()
print(f"成员测试时间: {(end-start)*1000:.2f} ms")

# 切片操作的内存复制行为
original = list(range(100))
slice_view = original[10:20]      # 创建新列表(浅拷贝)
print(f"原列表ID: {id(original)}, 切片ID: {id(slice_view)}")
print(f"切片是否为新对象: {original is not slice_view}")

动态修改操作与性能分析

import time
import sys

# 1. append() - O(1)均摇复杂度
def analyze_append_performance():
    """分析append操作的均摇常数时间复杂度"""
    data = []
    times = []
    
    for i in range(10000):
        start = time.perf_counter()
        data.append(i)
        end = time.perf_counter()
        times.append(end - start)
        
        # 记录关键时刻的内存重新分配
        if i in [0, 4, 8, 16, 25, 35, 46, 58, 72, 88]:
            print(f"append {i+1}个元素: 内存={sys.getsizeof(data)} bytes, 长度={len(data)}")
    
    avg_time = sum(times) / len(times)
    print(f"append平均时间: {avg_time*1e6:.3f} 微秒")

analyze_append_performance()

# 2. insert() - O(n)线性复杂度
def analyze_insert_performance():
    """分析insert操作在不同位置的性能差异"""
    base_data = list(range(10000))
    
    # 在头部插入 - 最坏情况
    data_copy = base_data.copy()
    start = time.perf_counter()
    data_copy.insert(0, -1)  # 需要移动所有元素
    end = time.perf_counter()
    print(f"在头部插入时间: {(end-start)*1e6:.3f} 微秒")
    
    # 在中间插入
    data_copy = base_data.copy()
    start = time.perf_counter()
    data_copy.insert(5000, -1)
    end = time.perf_counter()
    print(f"在中间插入时间: {(end-start)*1e6:.3f} 微秒")
    
    # 在末尾插入 - 等同append
    data_copy = base_data.copy()
    start = time.perf_counter()
    data_copy.insert(len(data_copy), -1)
    end = time.perf_counter()
    print(f"在末尾插入时间: {(end-start)*1e6:.3f} 微秒")

analyze_insert_performance()

# 3. 删除操作性能对比
def analyze_delete_performance():
    """remove, pop, del的性能对比"""
    # remove() - O(n) 需要查找
    data = list(range(10000))
    start = time.perf_counter()
    data.remove(5000)  # 查找 + 删除
    end = time.perf_counter()
    print(f"remove()查找并删除时间: {(end-start)*1e6:.3f} 微秒")
    
    # pop() 末尾 - O(1)
    data = list(range(10000))
    start = time.perf_counter()
    data.pop()  # 末尾删除
    end = time.perf_counter()
    print(f"pop()末尾删除时间: {(end-start)*1e6:.3f} 微秒")
    
    # pop(index) - O(n)
    data = list(range(10000))
    start = time.perf_counter()
    data.pop(0)  # 头部删除
    end = time.perf_counter()
    print(f"pop(0)头部删除时间: {(end-start)*1e6:.3f} 微秒")
    
    # del 切片 - O(n)
    data = list(range(10000))
    start = time.perf_counter()
    del data[1000:2000]  # 切片删除
    end = time.perf_counter()
    print(f"del 切片删除时间: {(end-start)*1e6:.3f} 微秒")

analyze_delete_performance()

# 4. 拷贝操作的内存行为
import copy

original_list = [[1, 2], [3, 4], [5, 6|1, 2], [3, 4], [5, 6]]

# 浅拷贝 - 只复制外层容器
shallow_copy = original_list.copy()
print(f"浅拷贝共享内部对象: {original_list[0] is shallow_copy[0]}")

# 深拷贝 - 递归复制所有对象
deep_copy = copy.deepcopy(original_list)
print(f"深拷贝创建新对象: {original_list[0] is not deep_copy[0]}")

# 切片赋值的内存优化
data = list(range(10))
print(f"原始数据: {data}")

# 切片替换 - 可以改变列表长度
data[2:5] = [100, 200]  # 3个元素被2个元素替换
print(f"切片替换后: {data}")

# 批量操作的性能优化
def batch_operations_comparison():
    """extend vs 多次append的性能对比"""
    # 多次append
    data1 = []
    new_items = list(range(10000))
    
    start = time.perf_counter()
    for item in new_items:
        data1.append(item)
    end = time.perf_counter()
    time_append = end - start
    
    # 一次extend
    data2 = []
    start = time.perf_counter()
    data2.extend(new_items)
    end = time.perf_counter()
    time_extend = end - start
    
    print(f"多次append时间: {time_append:.6f}秒")
    print(f"一次extend时间: {time_extend:.6f}秒")
    print(f"extend性能提升: {time_append/time_extend:.2f}倍")

batch_operations_comparison()

列表推导式与函数式编程

import dis
import time
from typing import List, Callable

# 1. 推导式 vs 循环的性能对比
def performance_comparison():
    data = range(100000)
    
    # 传统循环方式
    start = time.perf_counter()
    result1 = []
    for x in data:
        if x % 2 == 0:
            result1.append(x * x)
    time_loop = time.perf_counter() - start
    
    # 列表推导式
    start = time.perf_counter()
    result2 = [x * x for x in data if x % 2 == 0]
    time_comp = time.perf_counter() - start
    
    # filter + map 组合
    start = time.perf_counter()
    result3 = list(map(lambda x: x * x, filter(lambda x: x % 2 == 0, data)))
    time_functional = time.perf_counter() - start
    
    print(f"传统循环: {time_loop:.6f}秒")
    print(f"推导式: {time_comp:.6f}秒 (提升 {time_loop/time_comp:.2f}倍)")
    print(f"函数式: {time_functional:.6f}秒")
    
    return result1, result2, result3

performance_comparison()

# 2. 复杂推导式的可读性优化
def advanced_comprehensions():
    """高级推导式技巧与可读性平衡"""
    # 嵌套数据结构处理
    matrix_data = [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12]
    ]
    
    # 一维展开 - flatten
    flattened = [item for row in matrix_data for item in row]
    print(f"矩阵展开: {flattened}")
    
    # 条件过滤 + 变换
    filtered_transformed = [
        item ** 2 for row in matrix_data 
        for item in row if item % 2 == 0
    ]
    print(f"条件变换: {filtered_transformed}")
    
    # 字典推导式的高级应用
    word_lengths = {word: len(word) for word in ['python', 'java', 'go', 'rust']}
    print(f"单词长度: {word_lengths}")
    
    # 集合推导式去重
    unique_lengths = {len(word) for word in ['python', 'java', 'javascript', 'go']}
    print(f"唯一长度: {unique_lengths}")
    
    # 生成器表达式 - 内存优化
    def fibonacci_generator(n):
        a, b = 0, 1
        for _ in range(n):
            yield a
            a, b = b, a + b
    
    # 生成器推导式
    fib_squares = (x**2 for x in fibonacci_generator(10))
    print(f"斐波那契平方: {list(fib_squares)}")

advanced_comprehensions()

# 3. 排序算法与稳定性分析
def sorting_analysis():
    """Python排序算法Timsort的特性分析"""
    # 数据准备
    import random
    
    # 已排序数据 - Timsort优势
    sorted_data = list(range(10000))
    start = time.perf_counter()
    sorted_data.sort()
    time_sorted = time.perf_counter() - start
    
    # 随机数据
    random_data = list(range(10000))
    random.shuffle(random_data)
    start = time.perf_counter()
    random_data.sort()
    time_random = time.perf_counter() - start
    
    print(f"已排序数据: {time_sorted:.6f}秒")
    print(f"随机数据: {time_random:.6f}秒")
    print(f"Timsort对已排序数据优化: {time_random/time_sorted:.2f}倍")
    
    # 多关键字排序
    students = [
        {'name': 'Alice', 'grade': 85, 'age': 20},
        {'name': 'Bob', 'grade': 92, 'age': 19},
        {'name': 'Charlie', 'grade': 85, 'age': 21},
        {'name': 'David', 'grade': 92, 'age': 18}
    ]
    
    # 多级排序: 先按成绩，再按年龄
    students.sort(key=lambda x: (x['grade'], x['age']))
    print("\n多关键字排序结果:")
    for student in students:
        print(f"{student['name']}: 成绩{student['grade']}, 年龄{student['age']}")
    
    # 稳定排序特性验证
    data_with_ties = [(1, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]
    data_with_ties.sort(key=lambda x: x[0])  # 只按第一个元素排序
    print(f"\n稳定排序结果: {data_with_ties}")
    # 输出: [(1, 'a'), (1, 'c'), (2, 'b'), (2, 'd')] - 保持原始顺序

sorting_analysis()

# 4. 内存优化的高级技巧
def memory_optimization_techniques():
    """list内存优化的实用技巧"""
    import sys
    
    # __slots__ 优化对象大小
    class RegularStudent:
        def __init__(self, name, grade):
            self.name = name
            self.grade = grade
    
    class SlottedStudent:
        __slots__ = ['name', 'grade']
        def __init__(self, name, grade):
            self.name = name
            self.grade = grade
    
    # 内存使用对比
    regular_students = [RegularStudent(f"student{i}", 85) for i in range(1000)]
    slotted_students = [SlottedStudent(f"student{i}", 85) for i in range(1000)]
    
    regular_size = sum(sys.getsizeof(obj) + sys.getsizeof(obj.__dict__) for obj in regular_students)
    slotted_size = sum(sys.getsizeof(obj) for obj in slotted_students)
    
    print(f"\n常规对象列表内存: {regular_size} bytes")
    print(f"__slots__优化列表内存: {slotted_size} bytes")
    print(f"内存节省: {(regular_size - slotted_size) / regular_size * 100:.1f}%")
    
    # 数组模块优化数值数据
    import array
    
    # Python list vs array 内存效率
    python_list = list(range(100000))
    int_array = array.array('i', range(100000))
    
    print(f"\nPython list内存: {sys.getsizeof(python_list)} bytes")
    print(f"array.array内存: {sys.getsizeof(int_array)} bytes")
    print(f"内存节省: {(sys.getsizeof(python_list) - sys.getsizeof(int_array)) / sys.getsizeof(python_list) * 100:.1f}%")

memory_optimization_techniques()

tuple - 不可变序列的内存优化机制

技术定义: Python的tuple是一个不可变(immutable)的序列容器，内部实现为固定长度的PyObject指针数组。与 list 相比，通常具有更低的容器内存开销；访问性能差异取决于解释器版本与具体操作。

优势特性:

• 内存效率: 固定大小，无需预留扩展空间
• 哈希支持: 所有元素均可哈希时，可作为dict的key和set的元素
• 并发边界: 元组本身不可变，但内部可变对象的并发访问仍需按实际操作进行同步
• 解包优化: 编译器对元组解包有特殊优化

创建机制与内存分析

import sys
import time
import gc

# 1. 不同创建方式的内存对比
def tuple_memory_analysis():
    """tuple与 list 在内存使用上的对比"""
    # 相同数据的内存比较
    data = range(1000)
    
    tuple_obj = tuple(data)
    list_obj = list(data)
    
    print(f"tuple内存: {sys.getsizeof(tuple_obj)} bytes")
    print(f"list内存: {sys.getsizeof(list_obj)} bytes")
    print(f"tuple节省: {(sys.getsizeof(list_obj) - sys.getsizeof(tuple_obj)) / sys.getsizeof(list_obj) * 100:.1f}%")
    
    # 小元组对象的浅层大小测量，不用于证明缓存或对象复用
    small_tuples = []
    for i in range(1000):
        # 创建并保留单元素元组；本循环没有展示对象释放后的复用
        t = (i,)
        small_tuples.append(t)
    
    print(f"\n1000个单元素元组总内存: {sum(sys.getsizeof(t) for t in small_tuples)} bytes")

tuple_memory_analysis()

# 2. 元组创建性能对比
def creation_performance():
    """tuple 创建性能分析"""
    data = range(10000)
    
    # 字面量创建
    start = time.perf_counter()
    literal_tuple = (1, 2, 3, 4, 5)
    end = time.perf_counter()
    time_literal = end - start
    
    # 构造函数创建
    start = time.perf_counter()
    constructor_tuple = tuple([1, 2, 3, 4, 5])
    end = time.perf_counter()
    time_constructor = end - start
    
    # 从生成器创建
    start = time.perf_counter()
    generator_tuple = tuple(x for x in [1, 2, 3, 4, 5])
    end = time.perf_counter()
    time_generator = end - start
    
    print(f"\ntuple创建性能对比:")
    print(f"字面量: {time_literal*1e6:.3f} 微秒")
    print(f"构造函数: {time_constructor*1e6:.3f} 微秒")
    print(f"生成器: {time_generator*1e6:.3f} 微秒")

creation_performance()

# 3. 元组解包的字节码优化
def unpacking_optimization():
    """Python对元组解包的特殊优化"""
    import dis
    
    # 多变量赋值的字节码
    def tuple_unpacking():
        point = (10, 20, 30)
        x, y, z = point  # 元组解包
        return x, y, z
    
    def list_unpacking():
        point = [10, 20, 30]
        x, y, z = point  # 列表解包
        return x, y, z
    
    print("\n元组解包字节码:")
    dis.dis(tuple_unpacking)
    
    print("\n列表解包字节码:")
    dis.dis(list_unpacking)
    
    # 性能测试
    tuple_data = (1, 2, 3, 4, 5)
    list_data = [1, 2, 3, 4, 5]
    
    # 元组解包性能
    start = time.perf_counter()
    for _ in range(100000):
        a, b, c, d, e = tuple_data
    tuple_time = time.perf_counter() - start
    
    # 列表解包性能
    start = time.perf_counter()
    for _ in range(100000):
        a, b, c, d, e = list_data
    list_time = time.perf_counter() - start
    
    print(f"\n解包性能对比:")
    print(f"tuple解包: {tuple_time:.6f}秒")
    print(f"list解包: {list_time:.6f}秒")
    print(f"tuple优势: {list_time/tuple_time:.2f}倍")

unpacking_optimization()

# 4. 元组的哈希特性分析
def tuple_hashing():
    """tuple作为dict key和set元素的哈希机制"""
    # 复合键的应用场景
    coordinate_data = {}
    
    # 使用tuple作为复合键
    for x in range(10):
        for y in range(10):
            coordinate_data[(x, y)] = x * y
    
    print(f"\n坐标系统数据点数量: {len(coordinate_data)}")
    print(f"访问坐标(5,7): {coordinate_data[(5, 7)]}")
    
    # 测试哈希冲突
    hash_values = set()
    collision_count = 0
    
    for key in coordinate_data.keys():
        hash_val = hash(key)
        if hash_val in hash_values:
            collision_count += 1
        hash_values.add(hash_val)
    
    print(f"哈希冲突数量: {collision_count}")
    print(f"该样本完整哈希值不重复的比例: {(len(coordinate_data) - collision_count) / len(coordinate_data) * 100:.2f}%")
    
    # 嵌套元组的哈希
    nested_tuple = ((1, 2), (3, 4), (5, 6))
    print(f"\n嵌套元组哈希值: {hash(nested_tuple)}")
    print(f"可以作为集合元素: {nested_tuple in {nested_tuple}}")
    
    # 不可变性约束验证
    try:
        mutable_list = [1, 2, 3]
        hash(mutable_list)  # 这会抛出TypeError
    except TypeError as e:
        print(f"\n可变对象不可哈希: {e}")

tuple_hashing()

# 5. 单例模式中的tuple应用
def singleton_pattern_with_tuple():
    """tuple在单例模式中的应用"""
    class DatabaseConfig:
        _instance = None
        _config_tuple = None
        
        def __new__(cls, host, port, database):
            config_tuple = (host, port, database)
            if cls._instance is None or cls._config_tuple != config_tuple:
                cls._instance = super().__new__(cls)
                cls._config_tuple = config_tuple
            return cls._instance
        
        def __init__(self, host, port, database):
            if not hasattr(self, 'initialized'):
                self.host, self.port, self.database = host, port, database
                self.initialized = True
    
    # 测试单例行为
    config1 = DatabaseConfig("localhost", 5432, "mydb")
    config2 = DatabaseConfig("localhost", 5432, "mydb")
    config3 = DatabaseConfig("remote", 5432, "mydb")
    
    print(f"\nconfig1 is config2: {config1 is config2}")
    print(f"config1 is config3: {config1 is config3}")
    print(f"配置1: {config1._config_tuple}")
    print(f"配置3: {config3._config_tuple}")

singleton_pattern_with_tuple()

元组在数据分析中的应用

# 数据记录表示
student_records = [
    ("张三", 20, "计算机科学", 85.5),
    ("李四", 19, "数据科学", 92.0),
    ("王五", 21, "人工智能", 78.3)
]

# 处理学生记录
for name, age, major, score in student_records:
    if score >= 90:
        print(f"{name}({major})获得优秀成绩: {score}")

# 坐标和几何数据
points = [(0, 0), (1, 1), (2, 4), (3, 9)]  # 抛物线上的点

# 计算点之间的距离
def distance(p1, p2):
    x1, y1 = p1
    x2, y2 = p2
    return ((x2-x1)**2 + (y2-y1)**2)**0.5

for i in range(len(points)-1):
    dist = distance(points[i], points[i+1])
    print(f"点{points[i]}到{points[i+1]}的距离: {dist:.2f}")

# 枚举函数的返回值
data = ["python", "java", "javascript"]
for index, language in enumerate(data):
    print(f"{index}: {language}")

# 命名元组(更高级的应用)
from collections import namedtuple

# 创建学生类
Student = namedtuple('Student', ['name', 'age', 'major', 'gpa'])
student1 = Student("Alice", 20, "CS", 3.8)

print(student1.name)                 # Alice (可通过属性名访问)
print(student1)                   # 输出完整Student记录；索引访问示例为student1[0]

dict - 哈希表的实现与优化机制

技术定义: Python的dict基于开放寻址哈希(open addressing)实现，采用紧密哈希表(compact hash table)结构，提供O(1)平均时间复杂度的查找、插入和删除操作。

核心特性:

• 顺序保持: Python 3.7+保证插入顺序(insertion order)
• 动态扩容: 负载因子超过2/3时自动rehash
• 内存优化: 紧密布局减少空间开销
• 特殊方法: keys()、values()、items()返回视图对象

哈希机制与创建性能

import sys
import time
import string
import random
from collections import defaultdict

# 1. 哈希冲突与负载因子分析
def hash_collision_analysis():
    """dict哈希冲突的实际影响"""
    # 测试不同类型的键的哈希值
    test_keys = [
        "string_key",     # 字符串键
        42,               # 整数键
        (1, 2, 3),        # 元组键
        3.14159,          # 浮点数键
    ]
    
    print("不同类型键的哈希值:")
    for key in test_keys:
        hash_val = hash(key)
        print(f"{repr(key):15} -> {hash_val:20} (二进制长度: {hash_val.bit_length()})")
    
    # 分析哈希冲突率
    def generate_similar_keys(count=1000):
        """generate相似的键来测试哈希冲突"""
        keys = []
        for i in range(count):
            # 创建相似但不同的字符串键
            key = f"data_point_{i:04d}"
            keys.append(key)
        return keys
    
    similar_keys = generate_similar_keys()
    hash_values = {hash(key) for key in similar_keys}
    
    collision_rate = 1 - (len(hash_values) / len(similar_keys))
    print(f"\n哈希冲突率: {collision_rate:.6f} ({collision_rate*100:.4f}%)")
    print(f"唯一哈希值数量: {len(hash_values)} / {len(similar_keys)}")

hash_collision_analysis()

# 2. dict内存增长模式分析
def dict_memory_growth():
    """dict在扩容过程中的内存变化"""
    data = {}
    memory_usage = []
    sizes = []
    
    for i in range(1000):
        data[f"key_{i}"] = i
        current_size = sys.getsizeof(data)
        
        # 记录关键点的内存增长
        if i in [0, 7, 15, 31, 63, 127, 255, 511]:
            memory_usage.append(current_size)
            sizes.append(i + 1)
            print(f"元素数量: {i+1:3d}, 内存: {current_size:5d} bytes")
    
    # 分析内存增长模式
    for i in range(1, len(memory_usage)):
        growth_ratio = memory_usage[i] / memory_usage[i-1]
        print(f"从{sizes[i-1]}到{sizes[i]}元素内存增长: {growth_ratio:.2f}倍")

dict_memory_growth()

# 3. 不同创建方式的性能对比
def dict_creation_performance():
    """dict不同创建方式的性能对比"""
    test_data = [(f"key_{i}", i) for i in range(10000)]
    
    # 字典推导式
    start = time.perf_counter()
    dict_comp = {k: v for k, v in test_data}
    time_comp = time.perf_counter() - start
    
    # dict()构造函数
    start = time.perf_counter()
    dict_constructor = dict(test_data)
    time_constructor = time.perf_counter() - start
    
    # 循环赋值
    start = time.perf_counter()
    dict_loop = {}
    for k, v in test_data:
        dict_loop[k] = v
    time_loop = time.perf_counter() - start
    
    # update()方法
    start = time.perf_counter()
    dict_update = {}
    dict_update.update(test_data)
    time_update = time.perf_counter() - start
    
    print(f"\ndict创建性能对比(10000元素):")
    print(f"字典推导式: {time_comp:.6f}秒")
    print(f"dict()构造:  {time_constructor:.6f}秒")
    print(f"循环赋值:     {time_loop:.6f}秒")
    print(f"update()方法:  {time_update:.6f}秒")
    
    # 最佳性能标识
    times = [time_comp, time_constructor, time_loop, time_update]
    methods = ['推导式', 'dict()', '循环', 'update()']
    best_idx = times.index(min(times))
    print(f"最优方法: {methods[best_idx]}")

dict_creation_performance()

# 4. dict访问模式的性能分析
def dict_access_patterns():
    """dict不同访问模式的性能分析"""
    # 准备测试数据
    large_dict = {f"key_{i:06d}": i for i in range(100000)}
    existing_keys = list(large_dict.keys())[::1000]  # 每1000个取1个
    nonexistent_keys = [f"missing_{i}" for i in range(100)]
    
    # 1. 直接访问 vs .get()
    start = time.perf_counter()
    for key in existing_keys:
        value = large_dict[key]
    time_direct = time.perf_counter() - start
    
    start = time.perf_counter()
    for key in existing_keys:
        value = large_dict.get(key)
    time_get = time.perf_counter() - start
    
    print(f"\n存在的键访问(100个):")
    print(f"直接访问 [key]: {time_direct:.6f}秒")
    print(f".get(key) 方法:  {time_get:.6f}秒")
    print(f"直接访问优势: {time_get/time_direct:.2f}倍")
    
    # 2. 不存在的键处理
    start = time.perf_counter()
    for key in nonexistent_keys:
        try:
            value = large_dict[key]
        except KeyError:
            value = None
    time_exception = time.perf_counter() - start
    
    start = time.perf_counter()
    for key in nonexistent_keys:
        value = large_dict.get(key)
    time_get_missing = time.perf_counter() - start
    
    start = time.perf_counter()
    for key in nonexistent_keys:
        if key in large_dict:
            value = large_dict[key]
        else:
            value = None
    time_check_first = time.perf_counter() - start
    
    print(f"\n不存在的键处理(100个):")
    print(f"try-except:      {time_exception:.6f}秒")
    print(f".get() 方法:     {time_get_missing:.6f}秒")
    print(f"in 检查后访问: {time_check_first:.6f}秒")
    
    # 3. 成员访问 vs 键存在性检查
    start = time.perf_counter()
    for key in existing_keys:
        exists = key in large_dict
    time_membership = time.perf_counter() - start
    
    print(f"\n成员访问性能:")
    print(f"'in' 操作符: {time_membership:.6f}秒")
    print(f"平均每次查找: {time_membership/len(existing_keys)*1e6:.3f} 微秒")

dict_access_patterns()

字典高级操作

# 字典遍历方式
student_grades = {
    "张三": [85, 92, 78, 91],
    "李四": [90, 88, 92, 89],
    "王五": [76, 84, 88, 82]
}

# 遍历键
for name in student_grades.keys():
    print(f"学生: {name}")

# 遍历值
for grades in student_grades.values():
    avg_grade = sum(grades) / len(grades)
    print(f"平均分: {avg_grade:.2f}")

# 遍历键值对(最常用)
for name, grades in student_grades.items():
    avg_grade = sum(grades) / len(grades)
    print(f"{name}的平均分: {avg_grade:.2f}")

# 字典合并(Python 3.9+)
dict1 = {"a": 1, "b": 2}
dict2 = {"c": 3, "d": 4}
merged = dict1 | dict2               # {a: 1, b: 2, c: 3, d: 4}

# 传统合并方式
dict1.update(dict2)                  # 修改dict1
merged_old = {**dict1, **dict2}      # 解包合并

# 嵌套字典处理
company_data = {
    "employees": {
        "engineering": ["Alice", "Bob", "Charlie"],
        "marketing": ["David", "Eve"],
        "sales": ["Frank", "Grace", "Henry"]
    },
    "revenue": {
        "2022": 1000000,
        "2023": 1250000
    }
}

# 安全访问嵌套数据
def safe_get(dictionary, *keys, default=None):
    """安全获取嵌套字典的值"""
    for key in keys:
        if isinstance(dictionary, dict) and key in dictionary:
            dictionary = dictionary[key]
        else:
            return default
    return dictionary

engineering_team = safe_get(company_data, "employees", "engineering", default=[])
revenue_2023 = safe_get(company_data, "revenue", "2023", default=0)

字典在数据分析中的应用

# 数据统计和分组
sales_data = [
    {"product": "laptop", "category": "electronics", "price": 1200, "quantity": 5},
    {"product": "mouse", "category": "electronics", "price": 25, "quantity": 50},
    {"product": "desk", "category": "furniture", "price": 300, "quantity": 10},
    {"product": "chair", "category": "furniture", "price": 150, "quantity": 20}
]

# 按类别分组统计
category_stats = {}
for item in sales_data:
    category = item["category"]
    if category not in category_stats:
        category_stats[category] = {"total_revenue": 0, "total_quantity": 0}
    
    revenue = item["price"] * item["quantity"]
    category_stats[category]["total_revenue"] += revenue
    category_stats[category]["total_quantity"] += item["quantity"]

for category, stats in category_stats.items():
    print(f"{category}: 收入 ${stats['total_revenue']:,}, 数量 {stats['total_quantity']}")

# 使用defaultdict简化分组
from collections import defaultdict, Counter

# 计数器应用
product_categories = [item["category"] for item in sales_data]
category_count = Counter(product_categories)
print(category_count)  # Counter({'electronics': 2, 'furniture': 2})

# 价格区间分析
price_ranges = defaultdict(list)
for item in sales_data:
    price = item["price"]
    if price < 100:
        range_key = "低价"
    elif price < 500:
        range_key = "中价"
    else:
        range_key = "高价"
    price_ranges[range_key].append(item["product"])

for range_name, products in price_ranges.items():
    print(f"{range_name}产品: {', '.join(products)}")

set - 哈希集合的数学运算与去重机制

技术定义: Python的set基于哈希表实现，保证元素唯一性的无序集合。内部结构与dict类似，但只存储键而不存储值，提供平均O(1)时间复杂度的成员测试；交集、并集、差集等集合运算的成本取决于参与集合的大小。

数学特性:

• 唯一性约束: 自动去重，不允许重复元素
• 集合代数: 支持交集(∩)、并集(∪)、差集(-)、对称差集(∆)
• 包含关系: 子集、超集、不相交判断
• 可哈希约束: 只能存储可哈希对象；不可变性本身并不保证可哈希

去重机制与内存优化

import sys
import time
import random
from collections import Counter

# 1. 去重性能对比分析
def deduplication_performance():
    """set vs 其他去重方法的性能对比"""
    # 生成含有重复的大数据集
    data_size = 100000
    duplicate_rate = 0.3  # 每次约有30%的概率进入随机取值分支，不保证实际重复率为30%
    
    test_data = []
    for i in range(data_size):
        if random.random() < duplicate_rate:
            # 添加重复元素
            test_data.append(random.randint(0, data_size // 3))
        else:
            test_data.append(i)
    
    print(f"原始数据量: {len(test_data)}")
    print(f"实际唯一元素数: {len(set(test_data))}")
    
    # 方法1: 使用set去重
    start = time.perf_counter()
    unique_set = set(test_data)
    unique_list_from_set = list(unique_set)
    time_set = time.perf_counter() - start
    
    # 方法2: 使用dict.fromkeys()
    start = time.perf_counter()
    unique_dict = list(dict.fromkeys(test_data))
    time_dict = time.perf_counter() - start
    
    # 方法3: 使用列表推导式 + in操作符(低效)
    start = time.perf_counter()
    unique_list = []
    for item in test_data:
        if item not in unique_list:
            unique_list.append(item)
    time_list = time.perf_counter() - start
    
    # 方法4: 使用Counter
    start = time.perf_counter()
    counter = Counter(test_data)
    unique_counter = list(counter.keys())
    time_counter = time.perf_counter() - start
    
    print(f"\n去重性能对比:")
    print(f"set(): {time_set:.6f}秒 - 结果数量: {len(unique_list_from_set)}")
    print(f"dict.fromkeys(): {time_dict:.6f}秒 - 结果数量: {len(unique_dict)}")
    print(f"list + in: {time_list:.6f}秒 - 结果数量: {len(unique_list)}")
    print(f"Counter: {time_counter:.6f}秒 - 结果数量: {len(unique_counter)}")
    
    # 性能提升对比
    print(f"\nset比list+in快: {time_list/time_set:.2f}倍")
    print(f"本次dict.fromkeys耗时 / set去重耗时: {time_dict/time_set:.2f}；dict.fromkeys保留首次出现顺序")

deduplication_performance()

# 2. set内存优化分析
def set_memory_analysis():
    """set的内存使用特性"""
    # 不同数据量的内存使用
    sizes = [10, 100, 1000, 10000, 100000]
    
    print("\nset内存增长模式:")
    for size in sizes:
        test_set = set(range(size))
        test_list = list(range(size))
        test_dict = {i: None for i in range(size)}
        
        set_memory = sys.getsizeof(test_set)
        list_memory = sys.getsizeof(test_list)
        dict_memory = sys.getsizeof(test_dict)
        
        print(f"Size {size:6d}: set={set_memory:6d}B, list={list_memory:6d}B, dict={dict_memory:6d}B")
        print(f"             set vs list: {set_memory/list_memory:.2f}x, set vs dict: {set_memory/dict_memory:.2f}x")

set_memory_analysis()

# 3. set的哈希特性测试
def set_hash_characteristics():
    """set的哈希特性和约束"""
    # 可哈希类型测试
    hashable_items = [
        42,              # int
        3.14,            # float
        "string",        # str
        (1, 2, 3),       # tuple
        frozenset([1,2]) # frozenset
    ]
    
    print("\n可哈希类型测试:")
    valid_set = set()
    for item in hashable_items:
        try:
            valid_set.add(item)
            print(f"✓ {type(item).__name__:12}: {repr(item)[:30]:30} -> hash={hash(item)}")
        except TypeError as e:
            print(f"✗ {type(item).__name__:12}: {repr(item)[:30]:30} -> {e}")
    
    # 不可哈希类型测试
    unhashable_items = [
        [1, 2, 3],           # list
        {"key": "value"},    # dict
        {1, 2, 3},          # set
    ]
    
    print("\n不可哈希类型测试:")
    for item in unhashable_items:
        try:
            test_set = {item}
            print(f"✓ {type(item).__name__:12}: {repr(item)[:30]:30}")
        except TypeError as e:
            print(f"✗ {type(item).__name__:12}: {repr(item)[:30]:30} -> {e}")
    
    # frozenset的特殊应用
    nested_sets = [
        frozenset([1, 2, 3]),
        frozenset([3, 4, 5]),
        frozenset([1, 2, 3])  # 重复
    ]
    
    set_of_sets = set(nested_sets)
    print(f"\n嵌套集合去重: {len(nested_sets)} -> {len(set_of_sets)}")
    print(f"set元素: {set_of_sets}")

set_hash_characteristics()

# 4. 成员测试性能对比
def membership_test_performance():
    """set vs list 成员测试性能对比"""
    sizes = [100, 1000, 10000, 100000]
    
    print("\n成员测试性能对比 ('in' 操作符):")
    print("Size\t\tList Time\tSet Time\tSpeedup")
    print("-" * 50)
    
    for size in sizes:
        # 创建测试数据
        test_list = list(range(size))
        test_set = set(test_list)
        search_items = [size//4, size//2, size*3//4, size-1]  # 不同位置的元素
        
        # list成员测试
        start = time.perf_counter()
        for item in search_items * 1000:  # 重复1000次
            result = item in test_list
        list_time = time.perf_counter() - start
        
        # set成员测试
        start = time.perf_counter()
        for item in search_items * 1000:
            result = item in test_set
        set_time = time.perf_counter() - start
        
        speedup = list_time / set_time if set_time > 0 else float('inf')
        print(f"{size:8d}\t{list_time:.6f}\t{set_time:.6f}\t{speedup:8.2f}x")

membership_test_performance()

集合运算

# 数据分析中的集合运算示例
online_users = {"Alice", "Bob", "Charlie", "David", "Eve"}
mobile_users = {"Bob", "Charlie", "Frank", "Grace", "Alice"}

# 交集 - 同时使用两个平台的用户
both_platforms = online_users & mobile_users  # 或 online_users.intersection(mobile_users)
print(f"同时使用两平台: {both_platforms}")

# 并集 - 所有用户
all_users = online_users | mobile_users       # 或 online_users.union(mobile_users)
print(f"总用户数: {len(all_users)}")

# 差集 - 只使用在线平台的用户
online_only = online_users - mobile_users     # 或 online_users.difference(mobile_users)
print(f"仅在线用户: {online_only}")

# 对称差集 - 只使用一个平台的用户
single_platform = online_users ^ mobile_users # 或 online_users.symmetric_difference(mobile_users)
print(f"单平台用户: {single_platform}")

# 子集和超集检查
premium_users = {"Alice", "Bob"}
print(premium_users.issubset(online_users))   # True
print(online_users.issuperset(premium_users)) # True

集合在数据处理中的应用

# 数据去重和验证
email_list = [
    "user1@example.com", "user2@example.com", "user1@example.com",
    "user3@example.com", "user2@example.com", "user4@example.com"
]

# 去重邮箱
unique_emails = list(set(email_list))
print(f"原始邮箱数: {len(email_list)}, 去重后: {len(unique_emails)}")

# 数据验证和清洗
valid_domains = {"gmail.com", "yahoo.com", "outlook.com", "example.com"}
user_emails = ["alice@gmail.com", "bob@suspicious.com", "charlie@yahoo.com"]

# 验证邮箱域名
for email in user_emails:
    domain = email.split("@")[1]
    if domain in valid_domains:
        print(f"✅ {email} - 有效域名")
    else:
        print(f"❌ {email} - 可疑域名")

# 数据完整性检查
required_fields = {"name", "email", "age", "phone"}
user_data_samples = [
    {"name": "Alice", "email": "alice@example.com", "age": 25},
    {"name": "Bob", "email": "bob@example.com", "age": 30, "phone": "123-456-7890"},
    {"email": "charlie@example.com", "age": 28, "phone": "098-765-4321"}
]

for i, user in enumerate(user_data_samples):
    provided_fields = set(user.keys())
    missing_fields = required_fields - provided_fields
    extra_fields = provided_fields - required_fields
    
    print(f"用户{i+1}:")
    if missing_fields:
        print(f"  缺失字段: {missing_fields}")
    if extra_fields:
        print(f"  额外字段: {extra_fields}")
    if not missing_fields:
        print(f"  ✅ 数据完整")

# 快速查找和过滤
# 在大数据集中,集合的查找效率比列表高得多
large_dataset_ids = set(range(1000000))      # 100万个ID的集合
target_ids = [999999, 1000001, 500000]      # 要查找的ID

for target_id in target_ids:
    if target_id in large_dataset_ids:       # O(1)平均时间复杂度
        print(f"ID {target_id} 存在于数据集中")
    else:
        print(f"ID {target_id} 不存在于数据集中")

🔧 数据结构综合应用

实战案例：学生成绩管理系统

# 使用所有数据结构的综合案例
class StudentGradeAnalyzer:
    def __init__(self):
 # 字典存储学生信息
        self.students = {}
 # 集合存储所有课程
        self.all_courses = set()
 # 列表存储成绩记录
        self.grade_records = []
    
    def add_student(self, student_id, name, major):
        """添加学生信息"""
        self.students[student_id] = {
            "name": name,
            "major": major,
            "grades": {}  # 课程成绩字典
        }
    
    def add_grade(self, student_id, course, grade):
        """添加成绩记录"""
        if student_id in self.students:
            self.students[student_id]["grades"][course] = grade
            self.all_courses.add(course)
 # 元组记录：(学生ID, 课程, 成绩, 时间戳)
            import datetime
            record = (student_id, course, grade, datetime.datetime.now())
            self.grade_records.append(record)
    
    def get_student_avg(self, student_id):
        """计算学生平均分"""
        if student_id in self.students:
            grades = list(self.students[student_id]["grades"].values())
            return sum(grades) / len(grades) if grades else 0
        return 0
    
    def get_course_stats(self, course):
        """获取课程统计信息"""
        course_grades = []
        for student_data in self.students.values():
            if course in student_data["grades"]:
                course_grades.append(student_data["grades"][course])
        
        if not course_grades:
            return None
            
        return {
            "count": len(course_grades),
            "average": sum(course_grades) / len(course_grades),
            "max": max(course_grades),
            "min": min(course_grades)
        }
    
    def find_top_students(self, n=3):
        """找出成绩最好的N名学生"""
        student_averages = []
        for student_id, data in self.students.items():
            avg = self.get_student_avg(student_id)
            if data["grades"]:  # 有成绩的学生，包括平均分为0的学生
                student_averages.append((avg, student_id, data["name"]))
        
 # 按平均分排序
        student_averages.sort(reverse=True)
        return student_averages[:n]
    
    def analyze_major_performance(self):
        """分析专业表现"""
        major_stats = {}
        for student_id, data in self.students.items():
            major = data["major"]
            avg = self.get_student_avg(student_id)
            
            if data["grades"]:
                if major not in major_stats:
                    major_stats[major] = []
                major_stats[major].append(avg)
        
 # 计算各专业平均分
        for major, averages in major_stats.items():
            major_avg = sum(averages) / len(averages)
            print(f"{major}: 平均分 {major_avg:.2f}, 学生数 {len(averages)}")

# 使用示例
analyzer = StudentGradeAnalyzer()

# 添加学生
analyzer.add_student("S001", "张三", "计算机科学")
analyzer.add_student("S002", "李四", "数据科学")
analyzer.add_student("S003", "王五", "计算机科学")

# 添加成绩
analyzer.add_grade("S001", "模型部署", 92)
analyzer.add_grade("S001", "数据结构", 88)
analyzer.add_grade("S002", "模型部署", 95)
analyzer.add_grade("S002", "机器学习", 90)
analyzer.add_grade("S003", "模型部署", 85)

# 分析结果
print("=== 课程统计 ===")
for course in analyzer.all_courses:
    stats = analyzer.get_course_stats(course)
    if stats:
        print(f"{course}: 平均分 {stats['average']:.2f}, 最高分 {stats['max']}, 最低分 {stats['min']}")

print("\n=== 优秀学生 ===")
top_students = analyzer.find_top_students()
for i, (avg, student_id, name) in enumerate(top_students, 1):
    print(f"{i}. {name} ({student_id}): 平均分 {avg:.2f}")

print("\n=== 专业表现 ===")
analyzer.analyze_major_performance()

🎯 性能对比和最佳实践

性能测试

import time

def performance_test():
    """测试不同数据结构的性能"""
    n = 100000
    
 # 创建测试数据
    test_data = list(range(n))
    
 # 列表查找性能
    start_time = time.time()
    for i in range(1000):
        _ = n//2 in test_data  # O(n)
    list_time = time.time() - start_time
    
 # 集合查找性能
    test_set = set(test_data)
    start_time = time.time()
    for i in range(1000):
        _ = n//2 in test_set   # O(1)
    set_time = time.time() - start_time
    
    print(f"列表查找时间: {list_time:.4f}秒")
    print(f"集合查找时间: {set_time:.4f}秒")
    print(f"性能提升: {list_time/set_time:.1f}倍")

# performance_test()

数据结构选择决策树与性能优化指南

# 大量随机访问 - 优选 list
if access_pattern == 'random' and data_size > 10000:
    container = list(data)  # O(1) 访问，连续内存

# 高频查找 - 优选 dict/set
if operation == 'lookup' and frequency > 1000:
    container = set(data)   # O(1) 平均查找

# 数据去重 - 优选 set 或 dict.fromkeys()
if need_deduplication:
    if preserve_order:
        unique_data = list(dict.fromkeys(data))
    else:
        unique_data = list(set(data))  # 不保序；与dict.fromkeys的速度差异需实测

# 小数据集内存优化 - 不需要修改时可考虑tuple，实际开销需测量
if data_size < 100 and memory_critical:
    container = tuple(data)  # 不可变序列候选，不保证所有场景下内存最少

# 不可变数据 + 哈希需求 - tuple
if immutable_required and hashable_needed:
    key = tuple(coordinates)  # 可作为 dict key

# 高频集合运算 - frozenset
if frequent_set_operations:
    frozen_sets = {frozenset(group) for group in data_groups}

# 时间序列数据 - list 保证顺序
timestamps = []
for record in time_series_data:
    timestamps.append(record['timestamp'])

# 特征映射 - dict 快速查找
feature_map = {
    'categorical_feature': encode_categories(data),
    'numerical_feature': normalize_values(data)
}

# 数据清洗 - set 去重和检验
valid_ids = set(database_ids)
clean_data = [record for record in raw_data 
              if record['id'] in valid_ids]

🔗 知识连接

学习路径：

• ⬅️ 前置：Python基础语法
• ➡️ 后续：Python函数编程 - 学习函数和模块化
• 🔄 相关：NumPy数值计算 | Pandas数据结构

数据科学应用：

• 🎯 数据预处理：为Pandas数据清洗提供基础工具
• 🎯 算法实现：在机器学习中存储和操作数据
• 🎯 数据存储：与SQL学习路线图的数据结构映射关系

进阶方向：

• 📚 高级容器：collections模块(deque, defaultdict, Counter)
• 📚 内存优化：slots、array模块
• 📚 并发安全：线程安全的数据结构

创建时间：2024-06-29
最后更新：2025-01-02
字数统计：约10000字
阅读时长：90-120分钟
技术深度：中级 - 高级

#Python #数据结构 #列表 #字典 #元组 #集合 #数据组织 #编程基础