Skip to content

perf: reduce updateReferences() O(N^2) scans #619

@luojiyin1987

Description

@luojiyin1987

背景

StageManager.updateReferences() 在连接/删除/section 进出等高频路径调用,内部多次全量扫描 + 嵌套循环,可能导致卡顿。

现状

  • entity × association 双层遍历
  • section.children 每个 child 用 stage.find
  • line edge 双层遍历检测反向

思路

在 updateReferences 内部建立一次性索引,避免 N^2 扫描:

  • uuid -> StageObject map
  • sections/entities/associations/lineEdges arrays
  • line edge 反向检测用 set key ${source}->${target}

伪代码

function updateReferences() {
  const stage = this.project.stage;
  const uuidToObj = new Map(stage.map(o => [o.uuid, o]));
  const associations = stage.filter(o => o instanceof Association);
  const lineEdges = associations.filter(o => o instanceof LineEdge);
  const sections = stage
    .filter(o => o instanceof Section)
    .sort((a, b) => b.collisionBox.getRectangle().location.y - a.collisionBox.getRectangle().location.y);

  for (const edge of associations) {
    if (edge instanceof Edge) {
      if (edge.source.unknown) edge.source = uuidToObj.get(edge.source.uuid) ?? edge.source;
      if (edge.target.unknown) edge.target = uuidToObj.get(edge.target.uuid) ?? edge.target;
    }
  }

  for (const section of sections) {
    const newChildren: Entity[] = [];
    for (const child of section.children) {
      const obj = uuidToObj.get(child.uuid);
      if (obj instanceof Entity) newChildren.push(obj);
    }
    section.children = newChildren;
    section.adjustLocationAndSize();
    section.adjustChildrenStateByCollapse();
  }

  const pairSet = new Set(lineEdges.map(e => `${e.source.uuid}->${e.target.uuid}`));
  for (const edge of lineEdges) {
    edge.isShifting = pairSet.has(`${edge.target.uuid}->${edge.source.uuid}`);
  }
}

预期收益

避免 O(N^2) / O(E^2),降低 updateReferences 的卡顿风险。

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions