Table of contents
Open Table of contents
🧮 Part 1:最小生成树问题(MST)——Kruskal算法
题目简述
大山里有 N 个村落,人们通过长时间勘测,确定了 M 条道路的修建方案。每条道路连接且仅连接 2 个村落。请在这 M 个方案里,挑选适量的道路,使得挑选出来的方案建成后能让所有村落之间都能互相连通,且建设长度最小。
输入说明
第一行输入2个整数 N 和 M。 接下来 M 行,每行 X Y Z 共 3 个整数,代表第 i 个方案连通 X 和 Y 村,长度为 Z(村落从 0 开始编号)。
输出说明
如果所有道路都建设后也仍不能全部连通,输出 IMPOSSIBLE;否则输出建设的道路总长度。
解题思路分析
本题可以抽象为图的最小生成树(MST)问题,即:在一个无向加权图中,选择一些边,使得所有节点连通,且边的权值总和最小。
由于边的数量不一定形成连通图,我们还需考虑无法连通的情况。
我们选择使用 Kruskal 算法 来求解,核心思路如下:
-
初始化:每个村落看作一个节点,所有道路看作无向边,边权为道路长度。
-
贪心排序:将所有边按照权重从小到大排序。
-
并查集辅助判断连通性:
- 每次从小权重边开始尝试加入结果集中;
- 使用并查集判断两个端点是否属于同一集合(是否已连通);
- 若不连通,则将这条边加入最小生成树,并合并两个集合。
-
终止条件:
- 成功加入
N-1
条边时(生成树的特性),算法结束,输出当前总权重; - 若遍历完所有边仍未连通所有节点(加入边数 <
N-1
),说明原图不连通,返回IMPOSSIBLE
。
- 成功加入
Python 实现(Kruskal + Union-Find)
def find(parent, x):
if parent[x] != x:
parent[x] = find(parent, parent[x]) # 路径压缩
return parent[x]
def union(parent, rank, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX == rootY:
return False
if rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
if rank[rootX] == rank[rootY]:
rank[rootX] += 1
return True
def kruskal(N, edges):
edges.sort(key=lambda x: x[2]) # 按照权重排序
parent = [i for i in range(N)]
rank = [0] * N
total_weight = 0
edge_count = 0
for u, v, w in edges:
if union(parent, rank, u, v):
total_weight += w
edge_count += 1
if edge_count == N - 1:
break
return total_weight if edge_count == N - 1 else "IMPOSSIBLE"
# 读取输入
N, M = map(int, input().split())
edges = []
for _ in range(M):
u, v, w = map(int, input().split())
edges.append((u, v, w))
# 输出结果
print(kruskal(N, edges))
时间复杂度
- 排序:
- 并查集操作:接近常数时间,整体近似
🔧 为什么 Python 不能使用多线程并行计算?
核心原因是 GIL(全局解释器锁)。GIL,全称是 Global Interpreter Lock(全局解释器锁),是 CPython(最常用的 Python 实现)中的一个机制。它的作用是:同一时间只允许一个线程执行 Python 字节码。
在 CPU 密集型任务 中(如:图像处理、大量计算、加密解密等),即使开了多个线程,由于 GIL 的存在,它们依然是轮流执行的,不是并行。
但对于 IO 密集型任务(如网络请求、文件读写等),Python 多线程仍然有意义,因为线程会在等待 IO 时释放 GIL,其他线程就可以继续执行。
解决方案 —— 多进程(multiprocessing)
为了实现真正的并行计算,Python 提供了 multiprocessing
模块,它通过多个进程来绕过 GIL。
- 每个进程都有自己的 Python 解释器和内存空间;
- 所以它们可以真正并行运行在多个 CPU 核心上;
- 适合处理 CPU 密集型任务。
🧠 线程 vs 进程
线程、进程定义
名称 | 概念说明 |
---|---|
进程(Process) | 操作系统分配资源的最小单位。一个进程包含代码、数据、内存、打开的文件等,是一个完整的程序运行实例。 |
线程(Thread) | CPU 调度执行的最小单位。一个进程中可以包含多个线程,它们共享该进程的资源(如内存、文件描述符等)。 |
线程、进程核心区别
对比维度 | 线程 | 进程 |
---|---|---|
资源隔离 | 同一进程内多个线程共享资源(内存空间等) | 不同进程资源互相隔离 |
开销大小 | 创建和销毁开销小,切换速度快 | 创建和切换的开销大 |
通信方式 | 直接共享内存,通信快,但容易出错 | 通过进程间通信(如管道、队列),通信复杂但更安全 |
稳定性 | 某个线程崩溃可能影响整个进程 | 一个进程崩溃不会影响其他进程 |
并行性 | 受 GIL 限制(在 CPython 中不能并行) | 每个进程有独立解释器,可并行运行 |
线程、进程相同点
相同点 | 说明 |
---|---|
都是并发编程模型 | 都可用于提高程序运行效率,利用多核资源 |
都由操作系统调度 | 无论线程还是进程,最终都要被 CPU 执行 |
都有创建、销毁、切换的生命周期 | 系统会分配时间片和处理上下文切换 |
都可被阻塞、唤醒 | 如等待 IO、信号等 |
如果是多进程模型,能否实现进程之间内存共享?
虽然多进程模型下每个进程的内存是隔离的,但操作系统提供了共享内存机制,可以让多个进程访问同一块物理内存。共享内存是最快的进程间通信方式,但需要借助同步原语避免数据冲突。这在高性能系统中非常常见,比如数据库、图像处理等场景。
方法 | 说明 |
---|---|
共享内存(shmget) | 映射物理内存至多个进程地址空间 |
mmap 文件映射 | 利用磁盘文件映射为共享内存区域 |
管道、队列等 IPC | 不共享内存,但能通信 |
⚖️ 在同一进程内多个线程共享资源时,操作系统或程序是如何解决资源冲突/同步问题的?
核心问题:多个线程共享内存时如何同步?
同步机制 | 特点/使用场景 |
---|---|
互斥锁(mutex) | 最常见,适合保护单个资源 |
信号量(semaphore) | 控制并发数量,如线程池或连接池 |
条件变量(condition) | 等待特定状态,适合生产者消费者模型 |
自旋锁(spinlock) | 忙等待,不适合耗时长的锁定 |
🔒 自旋锁实现原理?
自旋锁是一种忙等待(busy-wait)锁机制。它通过不断轮询一个共享变量(通常是原子变量)来判断锁是否可用,常使用 原子操作(如 CAS: compare-and-swap) 来实现加锁与解锁,从而避免线程上下文切换的开销,适合锁持有时间非常短的场景。
CAS = Compare-And-Swap:比较当前值与预期值,如果相等则替换为新值
bool CAS(addr, expected, new) {
if (*addr == expected) {
*addr = new;
return true;
} else {
return false;
}
}
为什么是原子的?
- 因为 CPU 提供了原子指令支持(如 x86 的
CMPXCHG
); - 保证在执行过程中不会被中断、切换线程。
缺点
- ABA问题:值从 A→B→A,CAS 不知道其实变过;
- 自旋浪费 CPU:尤其在多核激烈竞争下;
- 一次只操作一个变量:不能原子更新多个内存块。
🎮 联机FPS游戏的传输层协议应该如何选用?
✅ UDP 为首选:低延迟、无连接,适合实时数据; ❌ TCP 会引入拥塞控制、队头阻塞,破坏游戏体验
如何保证 UDP 下重要数据不丢?
- 使用 应用层协议模拟可靠传输机制
- 为重要消息添加唯一编号(sequence ID)
- 发送后等待 ACK(确认)
- 超时未收到 ACK → 自动重发
- 收到重复包时进行“去重”
- 关键消息列表缓存机制
例子:玩家死亡事件
- 玩家死亡后发送一个 player_dead 消息(带 msg_id=555);
- 服务端确认后回复一个 ACK 555;
- 客户端记录该消息已确认;
- 如果 ACK 没收到,客户端将在 300ms 后再次发送 msg_id=555;
- 服务端如果重复收到 msg_id=555,可丢弃或仅处理一次(幂等)。
📶 移动网络优化方案(高丢包场景)
技术点 | 说明 |
---|---|
冗余包发送 | 关键消息重复发送几次,提升成功率 |
客户端预测 | 临时“假象”动作,服务器回正 |
差分压缩 | 只发送变更部分,减少带宽 |
关键帧机制 | 每隔 N 帧全量发一次状态包,防丢包恢复 |
自适应重传 | 根据 RTT 和丢包动态调节超时和重试频率 |
FEC 纠错码 | 多发校验信息,少数包丢失也能恢复数据 |