You need to enable JavaScript to run this app. Python 基于lines_origin与lines_dest返回坐标连通点并匹配状态列表的问题
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.10 20:15:04