#算法耗时优化

Junjie

2026-04-13 2cb43c8bcc1f5b7e6807dfe16bc9e08109bf7833

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

@@ -1,6 +1,7 @@
package com.zy.common.utils;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.alibaba.fastjson.TypeReference;
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
@@ -23,6 +24,7 @@
    private static final long REDIS_MAP_CACHE_TTL_SECONDS = 60 * 60 * 24L;
    private static final long MAP_CACHE_TTL_MS = 5000L;
    private static final Map<String, CachedNavigateMap> NAVIGATE_MAP_CACHE = new ConcurrentHashMap<>();
    private static final Map<String, CachedNavigateMapIndex> NAVIGATE_MAP_INDEX_CACHE = new ConcurrentHashMap<>();

    // Open表用优先队列
    public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
@@ -33,6 +35,10 @@

    public List<List<NavigateNode>> getStationMap(int lev) {
        return cloneNavigateMap(loadCachedNavigateMap("station", lev));
    }

    public NavigateMapIndex getStationMapIndex(int lev) {
        return loadCachedNavigateMapIndex("station", lev);
    }

    public List<List<NavigateNode>> getRgvTrackMap(int lev) {
@@ -49,14 +55,30 @@

        List<List<NavigateNode>> redisNavigateMap = loadNavigateMapFromRedis(mapType, lev);
        if (isValidNavigateMap(redisNavigateMap)) {
            enrichNavigateMapMetadata(redisNavigateMap);
            NAVIGATE_MAP_CACHE.put(cacheKey, new CachedNavigateMap(now, redisNavigateMap));
            return redisNavigateMap;
        }
        clearMapCache(lev);

        List<List<NavigateNode>> navigateNodeList = buildNavigateMap(mapType, lev);
        enrichNavigateMapMetadata(navigateNodeList);
        cacheNavigateMap(cacheKey, mapType, lev, navigateNodeList, now);
        return navigateNodeList;
    }

    private NavigateMapIndex loadCachedNavigateMapIndex(String mapType, int lev) {
        String cacheKey = mapType + ":" + lev;
        long now = System.currentTimeMillis();
        CachedNavigateMapIndex cachedNavigateMapIndex = NAVIGATE_MAP_INDEX_CACHE.get(cacheKey);
        if (cachedNavigateMapIndex != null && now - cachedNavigateMapIndex.cacheAtMs <= MAP_CACHE_TTL_MS) {
            return cachedNavigateMapIndex.navigateMapIndex;
        }

        List<List<NavigateNode>> navigateMap = loadCachedNavigateMap(mapType, lev);
        NavigateMapIndex navigateMapIndex = buildNavigateMapIndex(lev, navigateMap);
        NAVIGATE_MAP_INDEX_CACHE.put(cacheKey, new CachedNavigateMapIndex(now, navigateMapIndex));
        return navigateMapIndex;
    }

    public static void refreshAllMapCaches() {
@@ -82,8 +104,11 @@
        long now = System.currentTimeMillis();
        NavigateSolution navigateSolution = new NavigateSolution();
        List<List<NavigateNode>> stationMap = navigateSolution.buildNavigateMap("station", lev);
        navigateSolution.enrichNavigateMapMetadata(stationMap);
        navigateSolution.cacheNavigateMap("station:" + lev, "station", lev, stationMap, now);
        navigateSolution.cacheNavigateMapIndex("station:" + lev, lev, stationMap, now);
        List<List<NavigateNode>> rgvMap = navigateSolution.buildNavigateMap("rgv", lev);
        navigateSolution.enrichNavigateMapMetadata(rgvMap);
        navigateSolution.cacheNavigateMap("rgv:" + lev, "rgv", lev, rgvMap, now);
    }

@@ -93,6 +118,7 @@
        }
        NAVIGATE_MAP_CACHE.remove("station:" + lev);
        NAVIGATE_MAP_CACHE.remove("rgv:" + lev);
        NAVIGATE_MAP_INDEX_CACHE.remove("station:" + lev);
        RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
        redisUtil.del(buildRedisCacheKey("station", lev), buildRedisCacheKey("rgv", lev));
    }
@@ -107,6 +133,13 @@
                JSON.toJSONString(navigateNodeList),
                REDIS_MAP_CACHE_TTL_SECONDS);
        NAVIGATE_MAP_CACHE.put(localCacheKey, new CachedNavigateMap(cacheAtMs, navigateNodeList));
    }

    private void cacheNavigateMapIndex(String localCacheKey,
                                       int lev,
                                       List<List<NavigateNode>> navigateNodeList,
                                       long cacheAtMs) {
        NAVIGATE_MAP_INDEX_CACHE.put(localCacheKey, new CachedNavigateMapIndex(cacheAtMs, buildNavigateMapIndex(lev, navigateNodeList)));
    }

    private List<List<NavigateNode>> loadNavigateMapFromRedis(String mapType, int lev) {
@@ -181,6 +214,7 @@

                navigateNode.setNodeType(nodeType);
                navigateNode.setNodeValue(nodeValue);
                applyNodeMetadata(navigateNode);
                navigateNodeRow.add(navigateNode);
            }
            navigateNodeList.add(navigateNodeRow);
@@ -198,6 +232,63 @@
            cloneMap.add(cloneRow);
        }
        return cloneMap;
    }

    private void enrichNavigateMapMetadata(List<List<NavigateNode>> navigateMap) {
        if (navigateMap == null || navigateMap.isEmpty()) {
            return;
        }
        for (List<NavigateNode> row : navigateMap) {
            for (NavigateNode node : row) {
                applyNodeMetadata(node);
            }
        }
    }

    private void applyNodeMetadata(NavigateNode node) {
        if (node == null) {
            return;
        }
        if (node.getNodeValue() == null || node.getNodeValue().trim().isEmpty()) {
            if (node.getBridgeStationIds() == null) {
                node.setBridgeStationIds(Collections.emptyList());
            }
            if (node.getLiftTransfer() == null) {
                node.setLiftTransfer(Boolean.FALSE);
            }
            if (node.getRgvCalcFlag() == null) {
                node.setRgvCalcFlag(Boolean.FALSE);
            }
            return;
        }
        JSONObject valueObj = parseNodeValue(node.getNodeValue());
        if (valueObj == null) {
            if (node.getBridgeStationIds() == null) {
                node.setBridgeStationIds(Collections.emptyList());
            }
            if (node.getLiftTransfer() == null) {
                node.setLiftTransfer(Boolean.FALSE);
            }
            if (node.getRgvCalcFlag() == null) {
                node.setRgvCalcFlag(Boolean.FALSE);
            }
            return;
        }
        node.setStationId(valueObj.getInteger("stationId"));
        JSONArray bridgeStationArray = valueObj.getJSONArray("bridgeStationIds");
        if (bridgeStationArray == null || bridgeStationArray.isEmpty()) {
            node.setBridgeStationIds(Collections.emptyList());
        } else {
            node.setBridgeStationIds(Collections.unmodifiableList(new ArrayList<>(bridgeStationArray.toJavaList(Integer.class))));
        }
        Object isLiftTransfer = valueObj.get("isLiftTransfer");
        if (isLiftTransfer == null) {
            node.setLiftTransfer(Boolean.FALSE);
        } else {
            String isLiftTransferText = String.valueOf(isLiftTransfer);
            node.setLiftTransfer("1".equals(isLiftTransferText) || "true".equalsIgnoreCase(isLiftTransferText));
        }
        node.setRgvCalcFlag(valueObj.containsKey("rgvCalcFlag"));
    }

    private boolean isValidNavigateMap(List<List<NavigateNode>> navigateMap) {
@@ -557,8 +648,14 @@
    }

    private Integer extractStationId(NavigateNode node) {
        JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
        return valueObj == null ? null : valueObj.getInteger("stationId");
        if (node == null) {
            return null;
        }
        if (node.getStationId() != null) {
            return node.getStationId();
        }
        applyNodeMetadata(node);
        return node.getStationId();
    }

    private JSONObject parseNodeValue(String nodeValue) {
@@ -689,6 +786,13 @@
        return bestNode;
    }

    public NavigateNode findStationNavigateNode(NavigateMapIndex navigateMapIndex, int stationId) {
        if (navigateMapIndex == null) {
            return null;
        }
        return navigateMapIndex.getBestStationNode(stationId);
    }

    private int countExternalConnectionCount(Integer currentStationId, List<NavigateNode> neighbors) {
        Set<Integer> connectedStationIdSet = new LinkedHashSet<>();
        if (neighbors == null || neighbors.isEmpty()) {
@@ -702,23 +806,125 @@

    private Set<Integer> resolveAdjacentStationIds(Integer currentStationId, NavigateNode node) {
        Set<Integer> stationIdSet = new LinkedHashSet<>();
        JSONObject valueObj = parseNodeValue(node == null ? null : node.getNodeValue());
        if (valueObj == null) {
        if (node == null) {
            return stationIdSet;
        }
        Integer directStationId = valueObj.getInteger("stationId");
        Integer directStationId = extractStationId(node);
        if (directStationId != null && !directStationId.equals(currentStationId)) {
            stationIdSet.add(directStationId);
        }
        if (valueObj.getJSONArray("bridgeStationIds") == null) {
            return stationIdSet;
        }
        for (Integer bridgeStationId : valueObj.getJSONArray("bridgeStationIds").toJavaList(Integer.class)) {
        for (Integer bridgeStationId : node.getBridgeStationIds() == null ? Collections.<Integer>emptyList() : node.getBridgeStationIds()) {
            if (bridgeStationId != null && !bridgeStationId.equals(currentStationId)) {
                stationIdSet.add(bridgeStationId);
            }
        }
        return stationIdSet;
    }

    public List<NavigateNode> getNeighborNodes(NavigateMapIndex navigateMapIndex, NavigateNode node) {
        if (navigateMapIndex == null || node == null) {
            return Collections.emptyList();
        }
        return navigateMapIndex.getNeighborNodes(node);
    }

    public Set<Integer> getConnectedStationIds(NavigateMapIndex navigateMapIndex,
                                               Integer currentStationId,
                                               NavigateNode node) {
        if (navigateMapIndex == null || node == null) {
            return Collections.emptySet();
        }
        return navigateMapIndex.getConnectedStationIds(currentStationId, node);
    }

    private NavigateMapIndex buildNavigateMapIndex(int lev, List<List<NavigateNode>> navigateMap) {
        if (navigateMap == null || navigateMap.isEmpty()) {
            return new NavigateMapIndex(lev,
                    new ArrayList<>(),
                    Collections.emptyMap(),
                    Collections.emptyMap(),
                    Collections.emptyMap(),
                    Collections.emptyMap());
        }

        enrichNavigateMapMetadata(navigateMap);
        Map<String, NavigateNodeMeta> nodeMetaMap = new LinkedHashMap<>();
        Map<String, List<NavigateNode>> neighborNodeMap = new LinkedHashMap<>();
        Map<String, Set<Integer>> connectedStationIdMap = new LinkedHashMap<>();

        for (List<NavigateNode> row : navigateMap) {
            for (NavigateNode node : row) {
                if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
                    continue;
                }
                String nodeKey = buildNodeKey(node);
                nodeMetaMap.put(nodeKey, buildNavigateNodeMeta(node));
                List<NavigateNode> neighborList = extend_current_node(navigateMap, node);
                neighborNodeMap.put(nodeKey, Collections.unmodifiableList(new ArrayList<>(neighborList)));
            }
        }

        Map<Integer, NavigateNode> stationNodeMap = new LinkedHashMap<>();
        Map<Integer, Integer> stationExternalCountMap = new HashMap<>();
        Map<Integer, Integer> stationNeighborCountMap = new HashMap<>();
        for (List<NavigateNode> row : navigateMap) {
            for (NavigateNode node : row) {
                if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
                    continue;
                }
                String nodeKey = buildNodeKey(node);
                Integer stationId = extractStationId(node);
                Set<Integer> connectedStationIds = resolveAdjacentStationIds(stationId, neighborNodeMap.get(nodeKey));
                connectedStationIdMap.put(nodeKey, Collections.unmodifiableSet(connectedStationIds));
                if (stationId == null) {
                    continue;
                }
                int externalConnectionCount = connectedStationIds.size();
                int neighborCount = neighborNodeMap.get(nodeKey).size();
                Integer bestExternalCount = stationExternalCountMap.get(stationId);
                Integer bestNeighborCount = stationNeighborCountMap.get(stationId);
                if (bestExternalCount == null
                        || externalConnectionCount > bestExternalCount
                        || (externalConnectionCount == bestExternalCount && (bestNeighborCount == null || neighborCount > bestNeighborCount))) {
                    stationNodeMap.put(stationId, node);
                    stationExternalCountMap.put(stationId, externalConnectionCount);
                    stationNeighborCountMap.put(stationId, neighborCount);
                }
            }
        }
        return new NavigateMapIndex(lev,
                navigateMap,
                Collections.unmodifiableMap(nodeMetaMap),
                Collections.unmodifiableMap(stationNodeMap),
                Collections.unmodifiableMap(neighborNodeMap),
                Collections.unmodifiableMap(connectedStationIdMap));
    }

    private Set<Integer> resolveAdjacentStationIds(Integer currentStationId, List<NavigateNode> neighbors) {
        Set<Integer> connectedStationIdSet = new LinkedHashSet<>();
        if (neighbors == null || neighbors.isEmpty()) {
            return connectedStationIdSet;
        }
        for (NavigateNode neighbor : neighbors) {
            connectedStationIdSet.addAll(resolveAdjacentStationIds(currentStationId, neighbor));
        }
        return connectedStationIdSet;
    }

    private String buildNodeKey(NavigateNode node) {
        if (node == null) {
            return "";
        }
        return node.getX() + "_" + node.getY();
    }

    private NavigateNodeMeta buildNavigateNodeMeta(NavigateNode node) {
        return new NavigateNodeMeta(
                extractStationId(node),
                node == null || node.getBridgeStationIds() == null ? Collections.emptyList() : node.getBridgeStationIds(),
                node != null && Boolean.TRUE.equals(node.getLiftTransfer()),
                node != null && Boolean.TRUE.equals(node.getRgvCalcFlag())
        );
    }

    public NavigateNode findTrackSiteNoNavigateNode(List<List<NavigateNode>> map, int trackSiteNo) {
@@ -767,6 +973,115 @@

    //------------------A*启发函数-end------------------//

    public static class NavigateMapIndex {
        private final int lev;
        private final List<List<NavigateNode>> navigateMap;
        private final Map<String, NavigateNodeMeta> nodeMetaMap;
        private final Map<Integer, NavigateNode> stationNodeMap;
        private final Map<String, List<NavigateNode>> neighborNodeMap;
        private final Map<String, Set<Integer>> connectedStationIdMap;

        private NavigateMapIndex(int lev,
                                 List<List<NavigateNode>> navigateMap,
                                 Map<String, NavigateNodeMeta> nodeMetaMap,
                                 Map<Integer, NavigateNode> stationNodeMap,
                                 Map<String, List<NavigateNode>> neighborNodeMap,
                                 Map<String, Set<Integer>> connectedStationIdMap) {
            this.lev = lev;
            this.navigateMap = navigateMap == null ? new ArrayList<>() : navigateMap;
            this.nodeMetaMap = nodeMetaMap == null ? Collections.emptyMap() : nodeMetaMap;
            this.stationNodeMap = stationNodeMap == null ? Collections.emptyMap() : stationNodeMap;
            this.neighborNodeMap = neighborNodeMap == null ? Collections.emptyMap() : neighborNodeMap;
            this.connectedStationIdMap = connectedStationIdMap == null ? Collections.emptyMap() : connectedStationIdMap;
        }

        public int getLev() {
            return lev;
        }

        public List<List<NavigateNode>> getNavigateMap() {
            return navigateMap;
        }

        public NavigateNode getBestStationNode(Integer stationId) {
            if (stationId == null) {
                return null;
            }
            return stationNodeMap.get(stationId);
        }

        public List<NavigateNode> getNeighborNodes(NavigateNode node) {
            if (node == null) {
                return Collections.emptyList();
            }
            return neighborNodeMap.getOrDefault(node.getX() + "_" + node.getY(), Collections.emptyList());
        }

        public Set<Integer> getConnectedStationIds(Integer currentStationId, NavigateNode node) {
            if (node == null) {
                return Collections.emptySet();
            }
            Set<Integer> stationIdSet = connectedStationIdMap.getOrDefault(node.getX() + "_" + node.getY(), Collections.emptySet());
            if (currentStationId == null || stationIdSet.isEmpty()) {
                return stationIdSet;
            }
            if (!stationIdSet.contains(currentStationId)) {
                return stationIdSet;
            }
            Set<Integer> filterStationIdSet = new LinkedHashSet<>();
            for (Integer stationId : stationIdSet) {
                if (stationId != null && !stationId.equals(currentStationId)) {
                    filterStationIdSet.add(stationId);
                }
            }
            return filterStationIdSet;
        }

        public Integer getStationId(NavigateNode node) {
            NavigateNodeMeta meta = getNodeMeta(node);
            return meta == null ? null : meta.stationId;
        }

        public List<Integer> getBridgeStationIds(NavigateNode node) {
            NavigateNodeMeta meta = getNodeMeta(node);
            return meta == null ? Collections.emptyList() : meta.bridgeStationIds;
        }

        public boolean isLiftTransfer(NavigateNode node) {
            NavigateNodeMeta meta = getNodeMeta(node);
            return meta != null && meta.liftTransfer;
        }

        public boolean isRgvCalcFlag(NavigateNode node) {
            NavigateNodeMeta meta = getNodeMeta(node);
            return meta != null && meta.rgvCalcFlag;
        }

        private NavigateNodeMeta getNodeMeta(NavigateNode node) {
            if (node == null) {
                return null;
            }
            return nodeMetaMap.get(node.getX() + "_" + node.getY());
        }
    }

    private static class NavigateNodeMeta {
        private final Integer stationId;
        private final List<Integer> bridgeStationIds;
        private final boolean liftTransfer;
        private final boolean rgvCalcFlag;

        private NavigateNodeMeta(Integer stationId,
                                 List<Integer> bridgeStationIds,
                                 boolean liftTransfer,
                                 boolean rgvCalcFlag) {
            this.stationId = stationId;
            this.bridgeStationIds = bridgeStationIds == null ? Collections.emptyList() : bridgeStationIds;
            this.liftTransfer = liftTransfer;
            this.rgvCalcFlag = rgvCalcFlag;
        }
    }

    private static class CachedNavigateMap {
        private final long cacheAtMs;
        private final List<List<NavigateNode>> navigateMap;
@@ -776,4 +1091,14 @@
            this.navigateMap = navigateMap;
        }
    }

    private static class CachedNavigateMapIndex {
        private final long cacheAtMs;
        private final NavigateMapIndex navigateMapIndex;

        private CachedNavigateMapIndex(long cacheAtMs, NavigateMapIndex navigateMapIndex) {
            this.cacheAtMs = cacheAtMs;
            this.navigateMapIndex = navigateMapIndex;
        }
    }
}