#算法耗时优化

Junjie

2026-04-14 07f17e0e057e7207500bc4b6731afc0aa94723a6

#算法耗时优化

 src/main/java/com/zy/common/utils/NavigateSolution.java

@@ -28,8 +28,8 @@

    // Open表用优先队列
    public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
    //Close表用普通的数组
    public ArrayList<NavigateNode> Close = new ArrayList<NavigateNode>();
    //Close表用坐标key集合，O(1)查找
    public Set<String> Close = new HashSet<>();
    //用来存放已经出现过的结点。
    Map<String, Integer> bestGMap = new HashMap<>();

@@ -392,13 +392,13 @@
            }

            //将这个结点加入到Close表中
            Close.add(current_node);
            Close.add(keyOf(current_node));
            //对当前结点进行扩展，得到一个四周结点的数组
            ArrayList<NavigateNode> neighbour_node = extend_current_node(map, current_node);
            //对这个结点遍历，看是否有目标结点出现
            for (NavigateNode node : neighbour_node) {
                // 已在关闭列表中的节点不再处理，避免父链反复改写形成环
                if (Close.contains(node)) {
                if (Close.contains(keyOf(node))) {
                    continue;
                }
                // G + H + E (对启发函数增加去拐点方案calcNodeExtraCost)
@@ -410,7 +410,7 @@
                node.setH(calcNodeCost(node, end));
                node.setF(node.getG() + node.getH());

                String key = node.getX() + "_" + node.getY();
                String key = keyOf(node);
                Integer recordedG = bestGMap.get(key);
                // 仅当找到更小的代价时才更新与入Open，避免等价代价反复入队导致父链抖动
                if (recordedG == null || node.getG() < recordedG) {

 src/main/java/com/zy/common/utils/NavigateUtils.java

@@ -27,6 +27,7 @@
import com.zy.asrs.service.StationCycleCapacityService;
import com.zy.asrs.service.StationPathPolicyService;
import com.zy.core.News;
import org.springframework.scheduling.annotation.Scheduled;
import com.zy.core.model.StationObjModel;
import com.zy.core.model.command.StationCommand;
import com.zy.core.enums.StationCommandType;
@@ -77,11 +78,23 @@
    @Autowired
    private StationTaskTraceRegistry stationTaskTraceRegistry;

    private final Object runtimeSnapshotLock = new Object();
    private volatile CachedStationPathRuntimeSnapshot cachedRuntimeSnapshot;

    private final Object loopMergeGuardLock = new Object();
    private volatile CachedLoopMergeGuardContext cachedLoopMergeGuardContext;

    @Scheduled(fixedDelay = 1500, initialDelay = 3000)
    public void refreshStationPathCaches() {
        try {
            BaseRuntimeSnapshot snapshot = buildBaseRuntimeSnapshot(null);
            cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), snapshot);
        } catch (Exception ignore) {
        }
        try {
            LoopMergeGuardContext context = buildLoopMergeGuardContext();
            cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
        } catch (Exception ignore) {
        }
    }

    public List<NavigateNode> calcOptimalPathByStationId(Integer startStationId,
                                                         Integer endStationId,
@@ -1691,22 +1704,21 @@
            }
            return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
        }
        synchronized (runtimeSnapshotLock) {
            cachedSnapshot = cachedRuntimeSnapshot;
            if (cachedSnapshot != null && now - cachedSnapshot.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
                if (stepCostMap != null) {
                    stepCostMap.put("baseSnapshotCacheHit", 0L);
                }
                return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
            }
            long stepStartNs = System.nanoTime();
            BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
        // 缓存过期：用过期缓存兜底（@Scheduled 定时任务会很快刷新），避免多线程阻塞
        if (cachedSnapshot != null) {
            if (stepCostMap != null) {
                stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
                stepCostMap.put("baseSnapshotStale", 0L);
            }
            cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
            return baseRuntimeSnapshot;
            return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
        }
        // 极端情况：从未有过缓存（启动首次调用），同步构建
        long stepStartNs = System.nanoTime();
        BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
        if (stepCostMap != null) {
            stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
        }
        cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
        return baseRuntimeSnapshot;
    }

    private BaseRuntimeSnapshot buildBaseRuntimeSnapshot(Map<String, Long> stepCostMap) {
@@ -1774,15 +1786,14 @@
        if (cached != null && now - cached.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
            return new LoopMergeGuardContext(cached.context);
        }
        synchronized (loopMergeGuardLock) {
            cached = cachedLoopMergeGuardContext;
            if (cached != null && now - cached.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
                return new LoopMergeGuardContext(cached.context);
            }
            LoopMergeGuardContext context = buildLoopMergeGuardContext();
            cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
            return new LoopMergeGuardContext(context);
        // 缓存过期：用过期缓存兜底（@Scheduled 定时任务会很快刷新）
        if (cached != null) {
            return new LoopMergeGuardContext(cached.context);
        }
        // 极端情况：从未有过缓存，同步构建
        LoopMergeGuardContext context = buildLoopMergeGuardContext();
        cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
        return new LoopMergeGuardContext(context);
    }

    private LoopMergeGuardContext buildLoopMergeGuardContext() {