Python 基于lines_origin与lines_dest返回坐标连通点并匹配状态列表的问题
现有代码的核心问题
- 遍历取值逻辑错误:循环中
for i in coordinates的i本身就是坐标元组,后续代码却把i当列表索引用coordinates[i]取元素,会直接触发类型错误 - 连通点匹配逻辑错误:没有筛选和当前坐标对应的连接,直接把全量的
lines_dest/lines_origin赋值给connections,完全不符合预期的“仅返回当前点连通的坐标”需求 - 去重操作失效:
list(set(connections))只是临时生成去重后的列表,没有回写到connections变量,后续用到的还是原来的未去重的列表 - 索引查询效率极低:反复调用
coordinates.index(coord)查找坐标对应的位置,列表索引查找的时间复杂度为O(n),当坐标规模达到数千时会出现明显卡顿 - 循环逻辑错误:在校验连通点的循环里直接写
return,会导致程序第一次匹配到点就直接退出,无法完成全量坐标的遍历校验
可直接运行的优化实现
import random import numpy as np from collections import defaultdict ### 原有基础数据生成逻辑(保留,仅调整了边生成的空转问题) coordinates = [] for x in range(10): for y in range(20): coordinates.append((x,y)) lines = [] while len(lines) < 800: rnd_pair = random.sample(coordinates, 2) rnd_pair_rev = [rnd_pair[1], rnd_pair[0]] # 先计算距离,不满足要求直接跳过当次循环,避免空转 distance = abs(rnd_pair[0][0] - rnd_pair[1][0]) + abs(rnd_pair[0][1] - rnd_pair[1][1]) if distance > 2: continue if rnd_pair not in lines and rnd_pair_rev not in lines: lines.append(rnd_pair) lines_origin, lines_dest = zip(*lines) states = np.random.choice(["ON", "OFF"], size=len(coordinates), replace=True, p=[0.2, 0.8]) ### 核心预处理逻辑(解决效率问题) # 生成坐标到索引的映射,O(1)查询,替代低效的index()方法 coord2idx = {coord: idx for idx, coord in enumerate(coordinates)} # 生成邻接表:key为当前坐标,value为所有连通的坐标集合(自动去重,天然支持双向连接) adjacency = defaultdict(set) for orig, dest in zip(lines_origin, lines_dest): adjacency[orig].add(dest) adjacency[dest].add(orig) ### 遍历与校验逻辑 all_check_result = [] for current_coord in coordinates: # 获取当前坐标的所有连通点 connected_points = adjacency.get(current_coord, set()) # 校验是否存在ON状态的连通点,遇到第一个符合条件的点就停止遍历 has_on_neighbor = any(states[coord2idx[neighbor]] == "ON" for neighbor in connected_points) # 存储结果,可根据实际需求调整返回结构 all_check_result.append({ "current_point": current_coord, "connected_points": list(connected_points), "has_on_neighbor": has_on_neighbor })
性能对比说明
- 原逻辑的时间复杂度约为O(n*m):每次遍历一个坐标,都要扫完全量的边列表做匹配,再加全量的坐标列表做索引查询,规模越大卡顿越明显
- 优化后的时间复杂度约为O(n+m):邻接表和索引映射的构建只需要扫一遍边列表和坐标列表,后续每个坐标的连通点查询、状态校验都是O(1)级别,即使坐标规模扩展到上万也能保持流畅
- 连通点存储用集合实现,从结构上避免重复值,不需要额外做去重操作
- 校验逻辑用
any()搭配生成器表达式,只要找到第一个ON状态的连通点就终止遍历,减少无效计算
注意:邻接表已经补全了双向边的匹配,不需要再额外判断当前坐标是在
lines_origin还是lines_dest里,会自动把两个方向的连通点都收录进去。
内容的提问来源于stack exchange,提问作者stixmcvix
相关产品推荐
相关产品推荐

