第四部分：数据结构与算法优化

4.1 常用数据结构性能比较

python

import time

import random

from collections import deque, defaultdict, Counter, OrderedDict

from heapq import heappush, heappop, heapify

from bisect import bisect_left, bisect_right

import sys

def test_list_operations(size=100000):

   """测试列表操作性能"""

   print(f"测试列表操作 (size={size}):")

   

   # 创建列表

   start = time.time()

   lst = list(range(size))

   create_time = time.time() - start

   

   # 随机访问

   start = time.time()

   for _ in range(1000):

       _ = lst[random.randint(0, size-1)]

   random_access_time = time.time() - start

   

   # 尾部添加

   start = time.time()

   for i in range(1000):

       lst.append(i)

   append_time = time.time() - start

   

   # 头部插入

   start = time.time()

   for i in range(100):

       lst.insert(0, i)

   insert_time = time.time() - start

   

   # 查找元素

   start = time.time()

   for i in range(100):

       _ = i in lst

   search_time = time.time() - start

   

   print(f"  创建: {create_time:.6f}秒")

   print(f"  随机访问: {random_access_time:.6f}秒")

   print(f"  尾部添加: {append_time:.6f}秒")

   print(f"  头部插入: {insert_time:.6f}秒")

   print(f"  查找元素: {search_time:.6f}秒")

def test_deque_operations(size=100000):

   """测试deque操作性能"""

   print(f"\n测试deque操作 (size={size}):")

   

   # 创建deque

   start = time.time()

   dq = deque(range(size))

   create_time = time.time() - start

   

   # 随机访问

   start = time.time()

   for _ in range(1000):

       _ = dq[random.randint(0, size-1)]

   random_access_time = time.time() - start

   

   # 尾部添加

   start = time.time()

   for i in range(1000):

       dq.append(i)

   append_time = time.time() - start

   

   # 头部添加

   start = time.time()

   for i in range(1000):

       dq.appendleft(i)

   appendleft_time = time.time() - start

   

   # 头部弹出

   start = time.time()

   for _ in range(1000):

       _ = dq.popleft()

   popleft_time = time.time() - start

   

   print(f"  创建: {create_time:.6f}秒")

   print(f"  随机访问: {random_access_time:.6f}秒")

   print(f"  尾部添加: {append_time:.6f}秒")

   print(f"  头部添加: {appendleft_time:.6f}秒")

   print(f"  头部弹出: {popleft_time:.6f}秒")

def test_dict_operations(size=100000):

   """测试字典操作性能"""

   print(f"\n测试字典操作 (size={size}):")

   

   # 创建字典

   start = time.time()

   d = {i: f"value_{i}" for i in range(size)}

   create_time = time.time() - start

   

   # 随机访问

   start = time.time()

   for _ in range(1000):

       _ = d.get(random.randint(0, size-1))

   random_access_time = time.time() - start

   

   # 添加元素

   start = time.time()

   for i in range(1000):

       d[size + i] = f"new_value_{i}"

   add_time = time.time() - start

   

   # 删除元素

   start = time.time()

   for i in range(1000):

       if size + i in d:

           del d[size + i]

   delete_time = time.time() - start

   

   # 查找键

   start = time.time()

   for i in range(1000):

       _ = random.randint(0, size*2) in d

   search_time = time.time() - start

   

   print(f"  创建: {create_time:.6f}秒")

   print(f"  随机访问: {random_access_time:.6f}秒")

   print(f"  添加元素: {add_time:.6f}秒")

   print(f"  删除元素: {delete_time:.6f}秒")

   print(f"  查找键: {search_time:.6f}秒")

def test_set_operations(size=100000):

   """测试集合操作性能"""

   print(f"\n测试集合操作 (size={size}):")

   

   # 创建集合

   start = time.time()

   s = set(range(size))

   create_time = time.time() - start

   

   # 添加元素

   start = time.time()

   for i in range(1000):

       s.add(size + i)

   add_time = time.time() - start

   

   # 删除元素

   start = time.time()

   for i in range(1000):

       s.discard(size + i)

   delete_time = time.time() - start

   

   # 查找元素

   start = time.time()

   for i in range(1000):

       _ = random.randint(0, size*2) in s

   search_time = time.time() - start

   

   # 集合操作

   start = time.time()

   s2 = set(range(size//2, size*2))

   union_result = s.union(s2)

   intersection_result = s.intersection(s2)

   difference_result = s.difference(s2)

   set_ops_time = time.time() - start

   

   print(f"  创建: {create_time:.6f}秒")

   print(f"  添加元素: {add_time:.6f}秒")

   print(f"  删除元素: {delete_time:.6f}秒")

   print(f"  查找元素: {search_time:.6f}秒")

   print(f"  集合操作: {set_ops_time:.6f}秒")

def test_heap_operations(size=10000):

   """测试堆操作性能"""

   print(f"\n测试堆操作 (size={size}):")

   

   # 创建堆

   start = time.time()

   heap = list(range(size))

   random.shuffle(heap)

   heapify(heap)

   create_time = time.time() - start

   

   # 添加元素

   start = time.time()

   for i in range(1000):

       heappush(heap, size + i)

   push_time = time.time() - start

   

   # 弹出最小元素

   start = time.time()

   for _ in range(1000):

       _ = heappop(heap)

   pop_time = time.time() - start

   

   print(f"  创建: {create_time:.6f}秒")

   print(f"  添加元素: {push_time:.6f}秒")

   print(f"  弹出最小元素: {pop_time:.6f}秒")

def test_bisect_operations(size=100000):

   """测试二分查找性能"""

   print(f"\n测试二分查找操作 (size={size}):")

   

   # 创建有序列表

   start = time.time()

   lst = sorted(random.sample(range(size*2), size))

   create_time = time.time() - start

   

   # 二分查找

   start = time.time()

   for _ in range(1000):

       target = random.randint(0, size*2)

       pos = bisect_left(lst, target)

       if pos < len(lst) and lst[pos] == target:

           pass  # 找到

   bisect_time = time.time() - start

   

   # 线性查找（对比）

   start = time.time()

   for _ in range(100):

       target = random.randint(0, size*2)

       _ = target in lst

   linear_time = time.time() - start

   

   print(f"  创建有序列表: {create_time:.6f}秒")

   print(f"  二分查找 (1000次): {bisect_time:.6f}秒")

   print(f"  线性查找 (100次): {linear_time:.6f}秒")

def test_defaultdict_usage():

   """测试defaultdict的使用"""

   print("\n测试defaultdict使用:")

   

   # 示例1: 统计单词频率

   text = "this is a test this is only a test"

   words = text.split()

   

   # 使用普通字典

   word_count1 = {}

   for word in words:

       if word in word_count1:

           word_count1[word] += 1

       else:

           word_count1[word] = 1

   

   # 使用defaultdict

   from collections import defaultdict

   word_count2 = defaultdict(int)

   for word in words:

       word_count2[word] += 1

   

   print(f"  普通字典: {word_count1}")

   print(f"  defaultdict: {dict(word_count2)}")

   

   # 示例2: 分组数据

   students = [

       ('class1', '张三'),

       ('class2', '李四'),

       ('class1', '王五'),

       ('class3', '赵六'),

       ('class2', '钱七')

   ]

   

   classes = defaultdict(list)

   for class_name, student in students:

       classes[class_name].append(student)

   

   print(f"\n  按班级分组: {dict(classes)}")

def test_counter_usage():

   """测试Counter的使用"""

   print("\n测试Counter使用:")

   

   # 示例1: 统计元素频率

   from collections import Counter

   

   data = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']

   counter = Counter(data)

   

   print(f"  原始数据: {data}")

   print(f"  计数结果: {counter}")

   print(f"  最常见2个: {counter.most_common(2)}")

   

   # 示例2: 统计单词

   text = "the quick brown fox jumps over the lazy dog"

   word_counter = Counter(text.split())

   

   print(f"\n  文本: {text}")

   print(f"  单词统计: {word_counter}")

   

   # 示例3: 数学运算

   counter1 = Counter({'a': 3, 'b': 2, 'c': 1})

   counter2 = Counter({'a': 1, 'b': 2, 'd': 3})

   

   print(f"\n  计数器1: {counter1}")

   print(f"  计数器2: {counter2}")

   print(f"  加法: {counter1 + counter2}")

   print(f"  减法: {counter1 - counter2}")

   print(f"  交集: {counter1 & counter2}")

   print(f"  并集: {counter1 | counter2}")

def test_ordereddict_usage():

   """测试OrderedDict的使用"""

   print("\n测试OrderedDict使用:")

   

   from collections import OrderedDict

   

   # 创建有序字典

   od = OrderedDict()

   od['z'] = 1

   od['y'] = 2

   od['x'] = 3

   

   print(f"  有序字典: {od}")

   print(f"  顺序遍历: {list(od.keys())}")

   

   # 移动到末尾

   od.move_to_end('z')

   print(f"  移动'z'到末尾: {list(od.keys())}")

   

   # 移动到开头

   od.move_to_end('x', last=False)

   print(f"  移动'x'到开头: {list(od.keys())}")

   

   # 删除第一个元素

   first_key = next(iter(od))

   del od[first_key]

   print(f"  删除第一个元素后: {list(od.keys())}")

def algorithm_optimization_examples():

   """算法优化示例"""

   print("\n=== 算法优化示例 ===")

   

   # 示例1: 两数之和

   print("1. 两数之和问题:")

   

   def two_sum_naive(nums, target):

       """暴力解法 O(n²)"""

       for i in range(len(nums)):

           for j in range(i + 1, len(nums)):

               if nums[i] + nums[j] == target:

                   return [i, j]

       return []

   

   def two_sum_optimized(nums, target):

       """优化解法 O(n)"""

       num_map = {}

       for i, num in enumerate(nums):

           complement = target - num

           if complement in num_map:

               return [num_map[complement], i]

           num_map[num] = i

       return []

   

   nums = [2, 7, 11, 15, 3, 6, 8, 1]

   target = 9

   

   import timeit

   

   naive_time = timeit.timeit(lambda: two_sum_naive(nums, target), number=10000)

   optimized_time = timeit.timeit(lambda: two_sum_optimized(nums, target), number=10000)

   

   print(f"  数组: {nums}, 目标: {target}")

   print(f"  暴力解法结果: {two_sum_naive(nums, target)}, 耗时: {naive_time:.6f}秒 (10000次)")

   print(f"  优化解法结果: {two_sum_optimized(nums, target)}, 耗时: {optimized_time:.6f}秒 (10000次)")

   print(f"  优化倍数: {naive_time/optimized_time:.1f}倍")

   

   # 示例2: 斐波那契数列

   print("\n2. 斐波那契数列优化:")

   

   def fib_recursive(n):

       """递归解法 O(2^n)"""

       if n <= 1:

           return n

       return fib_recursive(n-1) + fib_recursive(n-2)

   

   def fib_memoization(n, memo={}):

       """记忆化递归 O(n)"""

       if n in memo:

           return memo[n]

       

       if n <= 1:

           result = n

       else:

           result = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)

       

       memo[n] = result

       return result

   

   def fib_iterative(n):

       """迭代解法 O(n)"""

       if n <= 1:

           return n

       

       a, b = 0, 1

       for _ in range(2, n+1):

           a, b = b, a + b

       return b

   

   n = 30

   

   # 递归解法太慢，只测试一次

   print(f"  计算fib({n}):")

   

   start = time.time()

   result_iterative = fib_iterative(n)

   iterative_time = time.time() - start

   print(f"    迭代解法: {result_iterative}, 耗时: {iterative_time:.6f}秒")

   

   start = time.time()

   result_memo = fib_memoization(n)

   memo_time = time.time() - start

   print(f"    记忆化递归: {result_memo}, 耗时: {memo_time:.6f}秒")

   

   # 示例3: 最大子数组和

   print("\n3. 最大子数组和问题:")

   

   def max_subarray_naive(nums):

       """暴力解法 O(n³)"""

       max_sum = float('-inf')

       n = len(nums)

       

       for i in range(n):

           for j in range(i, n):

               current_sum = sum(nums[i:j+1])

               if current_sum > max_sum:

                   max_sum = current_sum

       

       return max_sum

   

   def max_subarray_kadane(nums):

       """Kadane算法 O(n)"""

       max_current = max_global = nums[0]

       

       for i in range(1, len(nums)):

           max_current = max(nums[i], max_current + nums[i])

           if max_current > max_global:

               max_global = max_current

       

       return max_global

   

   test_nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

   

   naive_time = timeit.timeit(lambda: max_subarray_naive(test_nums), number=1000)

   kadane_time = timeit.timeit(lambda: max_subarray_kadane(test_nums), number=1000)

   

   print(f"  数组: {test_nums}")

   print(f"  暴力解法结果: {max_subarray_naive(test_nums)}, 耗时: {naive_time:.6f}秒 (1000次)")

   print(f"  Kadane算法结果: {max_subarray_kadane(test_nums)}, 耗时: {kadane_time:.6f}秒 (1000次)")

   print(f"  优化倍数: {naive_time/kadane_time:.1f}倍")

# 主程序

if __name__ == "__main__":

   print("=== 数据结构性能比较 ===")

   

   # 测试各种数据结构

   test_list_operations(100000)

   test_deque_operations(100000)

   test_dict_operations(100000)

   test_set_operations(100000)

   test_heap_operations(10000)

   test_bisect_operations(100000)

   

   # 测试collections模块

   test_defaultdict_usage()

   test_counter_usage()

   test_ordereddict_usage()

   

   # 算法优化示例

   algorithm_optimization_examples()

第五部分：测试与调试技巧

推荐阅读：

Python中级教程 第六课：高级特性与性能优化 2/2

Python中级教程 第六课：高级特性与性能优化 1/2

Python中级教程 第五课：异步编程与并发 2/2

Python中级教程 第五课：异步编程与并发 1/2

Python中级教程 第四课：上下文管理器、生成器与迭代器

Python中级教程 第三课：面向对象编程深入与装饰器