Python常用算法解析：从优雅简洁到高效实战

二、列表与字典算法

2.1 列表推导式的艺术

# 基本列表推导式
squares = [x**2 for x in range(10)]  # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# 带条件的列表推导式
even_squares = [x**2 for x in range(10) if x % 2 == 0]  # 偶数的平方

# 嵌套列表推导式
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flattened = [num for row in matrix for num in row]  # 展平二维列表

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

# 集合推导式
unique_chars = {char for char in "hello world" if char != ' '}  # {'h', 'e', 'l', 'o', 'w', 'r', 'd'}

# 生成器表达式（惰性求值）
large_squares = (x**2 for x in range(1000000))  # 不立即生成所有值
sum_of_squares = sum(x**2 for x in range(1000))  # 内存高效

2.2 字典的高级用法

from collections import defaultdict, Counter, OrderedDict

# defaultdict：自动初始化字典
word_counts = defaultdict(int)
for word in text.split():
    word_counts[word] += 1

# 按首字母分组
words_by_letter = defaultdict(list)
for word in words:
    words_by_letter[word[0]].append(word)

# Counter：计数专用字典
colors = ['red', 'blue', 'red', 'green', 'blue', 'blue']
color_counts = Counter(colors)  # Counter({'blue': 3, 'red': 2, 'green': 1})

# 最常见的n个元素
most_common = color_counts.most_common(2)  # [('blue', 3), ('red', 2)]

# OrderedDict：保持插入顺序（Python 3.7+普通dict已有序）

# LRU缓存实现
class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    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)  # 移除最旧的项

三、排序与搜索算法

3.1 内置排序的灵活运用

# 复杂对象的排序
class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age
    
    def __repr__(self):
        return f"Student({self.name}, {self.grade}, {self.age})"

students = [
    Student('Alice', 'A', 20),
    Student('Bob', 'B', 19),
    Student('Charlie', 'A', 21),
    Student('David', 'C', 20)
]

# 按多个字段排序
sorted_students = sorted(students, key=lambda s: (s.grade, s.age))

# 使用attrgetter和itemgetter
from operator import attrgetter, itemgetter

# attrgetter用于对象属性
sorted_by_age = sorted(students, key=attrgetter('age'))

# itemgetter用于元组或字典
data = [{'name': 'Alice', 'score': 85},
        {'name': 'Bob', 'score': 92},
        {'name': 'Charlie', 'score': 78}]
sorted_data = sorted(data, key=itemgetter('score'), reverse=True)

# 稳定排序的特性
# Python的sorted()是稳定排序，相等元素的相对顺序保持不变
items = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
sorted_items = sorted(items, key=lambda x: x[0])
# 结果：[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]
# 相同颜色的元素保持了原始顺序

3.2 二分查找与二等分模块

import bisect

# 基本二分查找
sorted_list = [1, 3, 5, 7, 9, 11, 13]

# 查找元素位置（返回插入位置）
position = bisect.bisect_left(sorted_list, 7)  # 3
position = bisect.bisect_right(sorted_list, 7)  # 4（重复元素时有用）

# 插入元素保持有序
bisect.insort_left(sorted_list, 6)  # 在适当位置插入6
bisect.insort_right(sorted_list, 8)  # 插入8

# 自定义比较函数的二分查找
def binary_search_custom(arr, target, key_func):
    """使用自定义key函数的二分查找"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if key_func(arr[mid]) < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if lo < len(arr) and key_func(arr[lo]) == target else -1

# 查找范围
def find_range(arr, target):
    """在有序数组中查找目标值的起始和结束位置"""
    left = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target)
    return (left, right) if left < right else (-1, -1)

# 示例
nums = [5, 7, 7, 8, 8, 8, 10]
start, end = find_range(nums, 8)  # (3, 6)

四、图形算法与网络分析

4.1 使用networkx进行图分析

import networkx as nx
import matplotlib.pyplot as plt

# 创建图
G = nx.Graph()  # 无向图
# G = nx.DiGraph()  # 有向图

# 添加节点和边
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)])

# 基本图算法
# 最短路径
shortest_path = nx.shortest_path(G, source=1, target=5)  # [1, 3, 4, 5]

# 连通分量
connected_components = list(nx.connected_components(G))

# 度中心性
degree_centrality = nx.degree_centrality(G)

# PageRank算法
pagerank_scores = nx.pagerank(G, alpha=0.85)

# 社区检测
from networkx.algorithms import community

# Louvain方法
communities = community.greedy_modularity_communities(G)

# 可视化
pos = nx.spring_layout(G)  # 布局算法
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=10)
plt.show()

4.2 自定义图算法实现

from collections import deque, defaultdict

# BFS（广度优先搜索）
def bfs(graph, start):
    """图的广度优先遍历"""
    visited = set()
    queue = deque([start])
    result = []
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            queue.extend(graph[vertex] - visited)
    
    return result

# DFS（深度优先搜索）- 递归版本
def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
    return visited

# Dijkstra算法
import heapq

def dijkstra(graph, start):
    """单源最短路径 - Dijkstra算法"""
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    pq = [(0, start)]  # 优先队列
    
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 拓扑排序
def topological_sort(graph):
    """有向无环图的拓扑排序"""
    in_degree = {u: 0 for u in graph}
    
    # 计算入度
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    
    # 收集入度为0的节点
    queue = deque([u for u in graph if in_degree[u] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    if len(result) != len(graph):
        raise ValueError("图中存在环")
    
    return result

五、数值计算与科学计算

5.1 使用NumPy进行数值计算

import numpy as np

# 数组创建和操作
arr = np.array([1, 2, 3, 4, 5])
matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])

# 向量化操作（避免Python循环）
# 传统Python方式
squares = [x**2 for x in range(1000000)]  # 慢

# NumPy向量化方式
squares_np = np.arange(1000000) ** 2  # 快

# 广播机制
a = np.array([[1, 2, 3], [4, 5, 6]])
b = np.array([10, 20, 30])
result = a + b  # 广播：[[11, 22, 33], [14, 25, 36]]

# 线性代数运算
A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])

dot_product = np.dot(A, B)  # 矩阵乘法
determinant = np.linalg.det(A)  # 行列式
eigenvalues, eigenvectors = np.linalg.eig(A)  # 特征值和特征向量

# 统计计算
data = np.random.randn(1000, 10)  # 1000行10列的随机数据
mean = np.mean(data, axis=0)  # 每列的平均值
std = np.std(data, axis=0)    # 每列的标准差
correlation = np.corrcoef(data.T)  # 相关系数矩阵

5.2 使用pandas进行数据分析

import pandas as pd
import numpy as np

# 创建DataFrame
data = {
    'Name': ['Alice', 'Bob', 'Charlie', 'David'],
    'Age': [25, 30, 35, 40],
    'Salary': [50000, 60000, 70000, 80000],
    'Department': ['HR', 'Engineering', 'Engineering', 'HR']
}
df = pd.DataFrame(data)

# 数据筛选和查询
# 基本筛选
engineering_df = df[df['Department'] == 'Engineering']
high_salary = df[df['Salary'] > 60000]

# 复杂查询
result = df.query('Age > 30 and Salary < 75000')

# 分组聚合
grouped = df.groupby('Department')
summary = grouped.agg({
    'Age': ['mean', 'min', 'max'],
    'Salary': ['sum', 'mean', 'std']
})

# 数据透视表
pivot = pd.pivot_table(df, 
                       values='Salary',
                       index='Department',
                       columns=None,
                       aggfunc=['mean', 'count', 'sum'])

# 时间序列处理
dates = pd.date_range('2023-01-01', periods=100, freq='D')
time_series = pd.Series(np.random.randn(100), index=dates)

# 重采样
monthly_avg = time_series.resample('M').mean()
rolling_avg = time_series.rolling(window=7).mean()  # 7天移动平均

六、机器学习算法

6.1 使用 scikit-learn

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import classification_report, confusion_matrix
import numpy as np

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

# 数据预处理
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(
    X_scaled, y, test_size=0.2, random_state=42, stratify=y
)

# 训练模型
clf = RandomForestClassifier(n_estimators=100, random_state=42)
clf.fit(X_train, y_train)

# 模型评估
y_pred = clf.predict(X_test)
print(classification_report(y_test, y_pred))

# 交叉验证
cv_scores = cross_val_score(clf, X_scaled, y, cv=5)
print(f"交叉验证平均得分: {cv_scores.mean():.3f}")

# 特征重要性
feature_importances = clf.feature_importances_
for name, importance in zip(iris.feature_names, feature_importances):
    print(f"{name}: {importance:.3f}")

6.2 自定义机器学习算法

import numpy as np
from collections import Counter

class KNN:
    """K近邻算法实现"""
    def __init__(self, k=3):
        self.k = k
    
    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
    
    def predict(self, X):
        predictions = [self._predict(x) for x in X]
        return np.array(predictions)
    
    def _predict(self, x):
        # 计算距离
        distances = [np.linalg.norm(x - x_train) for x_train in self.X_train]
        
        # 获取k个最近邻的索引
        k_indices = np.argsort(distances)[:self.k]
        
        # 获取k个最近邻的标签
        k_nearest_labels = [self.y_train[i] for i in k_indices]
        
        # 多数投票
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]

class LinearRegression:
    """线性回归实现（梯度下降）"""
    def __init__(self, learning_rate=0.01, n_iterations=1000):
        self.learning_rate = learning_rate
        self.n_iterations = n_iterations
        self.weights = None
        self.bias = None
    
    def fit(self, X, y):
        n_samples, n_features = X.shape
        
        # 初始化参数
        self.weights = np.zeros(n_features)
        self.bias = 0
        
        # 梯度下降
        for _ in range(self.n_iterations):
            # 预测
            y_pred = np.dot(X, self.weights) + self.bias
            
            # 计算梯度
            dw = (1/n_samples) * np.dot(X.T, (y_pred - y))
            db = (1/n_samples) * np.sum(y_pred - y)
            
            # 更新参数
            self.weights -= self.learning_rate * dw
            self.bias -= self.learning_rate * db
    
    def predict(self, X):
        return np.dot(X, self.weights) + self.bias