package com.zy.common.utils;
|
|
import com.alibaba.fastjson.JSON;
|
import com.alibaba.fastjson.JSONObject;
|
import com.zy.asrs.service.impl.BasMapEditorServiceImpl;
|
import com.zy.asrs.utils.MapExcelUtils;
|
import com.zy.common.model.NavigateNode;
|
import com.zy.core.enums.MapNodeType;
|
import org.junit.jupiter.api.Assumptions;
|
import org.junit.jupiter.api.Test;
|
import org.springframework.test.util.ReflectionTestUtils;
|
|
import java.io.IOException;
|
import java.nio.file.Files;
|
import java.nio.file.Path;
|
import java.util.ArrayList;
|
import java.util.Comparator;
|
import java.util.HashMap;
|
import java.util.LinkedHashMap;
|
import java.util.LinkedHashSet;
|
import java.util.List;
|
import java.util.Locale;
|
import java.util.Map;
|
import java.util.Set;
|
import java.util.stream.Collectors;
|
import java.util.stream.Stream;
|
|
import static org.junit.jupiter.api.Assertions.assertFalse;
|
|
class NavigatePerformanceBenchmarkTest {
|
|
private static final int CALC_MAX_DEPTH = 120;
|
private static final int CALC_MAX_PATHS = 500;
|
private static final int CALC_MAX_COST = 300;
|
|
@Test
|
void benchmarkExcelMaps() throws Exception {
|
// 手工压测入口，避免默认测试套件被性能测试拖慢。
|
Assumptions.assumeTrue(Boolean.getBoolean("manualBench"));
|
|
Path mapDir = Path.of("src/main/resources/map");
|
List<Path> mapFileList;
|
try (Stream<Path> stream = Files.list(mapDir)) {
|
mapFileList = stream
|
.filter(path -> path.getFileName().toString().endsWith(".xlsx"))
|
.sorted(Comparator.comparing(path -> path.getFileName().toString()))
|
.collect(Collectors.toList());
|
}
|
|
List<String> reportLineList = new ArrayList<>();
|
for (Path mapFile : mapFileList) {
|
reportLineList.addAll(benchmarkMapFile(mapFile));
|
}
|
|
reportLineList.forEach(System.out::println);
|
assertFalse(reportLineList.isEmpty(), "未生成任何地图性能报告");
|
}
|
|
private List<String> benchmarkMapFile(Path mapFile) throws IOException {
|
MapExcelUtils mapExcelUtils = new MapExcelUtils();
|
BasMapEditorServiceImpl editorService = new BasMapEditorServiceImpl();
|
|
HashMap<Integer, List<List<HashMap<String, Object>>>> rawDataMap = mapExcelUtils.readExcel(mapFile.toString());
|
List<Integer> levList = rawDataMap.keySet().stream().sorted().collect(Collectors.toList());
|
|
List<String> reportLineList = new ArrayList<>();
|
for (Integer lev : levList) {
|
@SuppressWarnings("unchecked")
|
List<List<HashMap<String, Object>>> storedData =
|
(List<List<HashMap<String, Object>>>) ReflectionTestUtils.invokeMethod(
|
editorService,
|
"convertRawExcelData",
|
rawDataMap.get(lev)
|
);
|
List<List<NavigateNode>> stationMap = buildStationMap(storedData);
|
Map<Integer, NavigateNode> stationNodeMap = collectStationNodeMap(stationMap);
|
if (stationNodeMap.size() < 2) {
|
continue;
|
}
|
|
BenchmarkSummary summary = benchmarkStationPairs(stationMap, stationNodeMap);
|
reportLineList.add(summary.format(mapFile.getFileName().toString(), lev));
|
}
|
return reportLineList;
|
}
|
|
private BenchmarkSummary benchmarkStationPairs(List<List<NavigateNode>> stationMap,
|
Map<Integer, NavigateNode> stationNodeMap) {
|
NavigateSolution navigateSolution = new NavigateSolution();
|
List<Integer> stationIdList = new ArrayList<>(stationNodeMap.keySet());
|
stationIdList.sort(Integer::compareTo);
|
|
BenchmarkSummary summary = new BenchmarkSummary(stationIdList.size());
|
warmup(navigateSolution, stationMap, stationNodeMap, stationIdList);
|
|
for (int i = 0; i < stationIdList.size(); i++) {
|
for (int j = i + 1; j < stationIdList.size(); j++) {
|
Integer startStationId = stationIdList.get(i);
|
Integer endStationId = stationIdList.get(j);
|
|
NavigateNode startNode = stationNodeMap.get(startStationId);
|
NavigateNode endNode = stationNodeMap.get(endStationId);
|
if (startNode == null || endNode == null) {
|
continue;
|
}
|
|
resetMapSearchState(stationMap);
|
long astarStartNs = System.nanoTime();
|
NavigateNode astarResult = navigateSolution.astarSearchJava(stationMap, startNode, endNode);
|
long astarElapsedNs = System.nanoTime() - astarStartNs;
|
int astarPathLen = calcBacktrackPathLength(astarResult, stationMap);
|
|
long allPathsStartNs = System.nanoTime();
|
List<List<NavigateNode>> candidatePathList = navigateSolution.allSimplePaths(
|
stationMap,
|
startNode,
|
endNode,
|
CALC_MAX_DEPTH,
|
CALC_MAX_PATHS,
|
CALC_MAX_COST
|
);
|
long allPathsElapsedNs = System.nanoTime() - allPathsStartNs;
|
|
summary.record(
|
startStationId,
|
endStationId,
|
astarElapsedNs,
|
allPathsElapsedNs,
|
astarPathLen,
|
candidatePathList == null ? 0 : candidatePathList.size()
|
);
|
}
|
}
|
return summary;
|
}
|
|
private void warmup(NavigateSolution navigateSolution,
|
List<List<NavigateNode>> stationMap,
|
Map<Integer, NavigateNode> stationNodeMap,
|
List<Integer> stationIdList) {
|
int warmupPairCount = Math.min(5, Math.max(0, stationIdList.size() - 1));
|
for (int i = 0; i < warmupPairCount; i++) {
|
Integer startStationId = stationIdList.get(i);
|
Integer endStationId = stationIdList.get(stationIdList.size() - 1 - i);
|
NavigateNode startNode = stationNodeMap.get(startStationId);
|
NavigateNode endNode = stationNodeMap.get(endStationId);
|
if (startNode == null || endNode == null) {
|
continue;
|
}
|
resetMapSearchState(stationMap);
|
navigateSolution.astarSearchJava(stationMap, startNode, endNode);
|
navigateSolution.allSimplePaths(
|
stationMap,
|
startNode,
|
endNode,
|
CALC_MAX_DEPTH,
|
CALC_MAX_PATHS,
|
CALC_MAX_COST
|
);
|
}
|
}
|
|
private Map<Integer, NavigateNode> collectStationNodeMap(List<List<NavigateNode>> stationMap) {
|
NavigateSolution navigateSolution = new NavigateSolution();
|
Set<Integer> stationIdSet = new LinkedHashSet<>();
|
for (List<NavigateNode> row : stationMap) {
|
for (NavigateNode node : row) {
|
Integer stationId = extractStationId(node);
|
if (stationId != null) {
|
stationIdSet.add(stationId);
|
}
|
}
|
}
|
|
Map<Integer, NavigateNode> stationNodeMap = new LinkedHashMap<>();
|
for (Integer stationId : stationIdSet) {
|
NavigateNode node = navigateSolution.findStationNavigateNode(stationMap, stationId);
|
if (node != null) {
|
stationNodeMap.put(stationId, node);
|
}
|
}
|
return stationNodeMap;
|
}
|
|
private Integer extractStationId(NavigateNode node) {
|
if (node == null || node.getNodeValue() == null || node.getNodeValue().trim().isEmpty()) {
|
return null;
|
}
|
try {
|
JSONObject valueObject = JSON.parseObject(node.getNodeValue());
|
return valueObject == null ? null : valueObject.getInteger("stationId");
|
} catch (Exception ignore) {
|
return null;
|
}
|
}
|
|
private void resetMapSearchState(List<List<NavigateNode>> stationMap) {
|
for (List<NavigateNode> row : stationMap) {
|
for (NavigateNode node : row) {
|
node.setFather(null);
|
node.setF(0);
|
node.setG(0);
|
node.setH(0);
|
node.setIsInflectionPoint(false);
|
node.setDirection(null);
|
}
|
}
|
}
|
|
private int calcBacktrackPathLength(NavigateNode endNode, List<List<NavigateNode>> stationMap) {
|
if (endNode == null) {
|
return 0;
|
}
|
int maxDepth = stationMap.size() * stationMap.get(0).size() + 5;
|
int length = 0;
|
Set<String> visited = new LinkedHashSet<>();
|
NavigateNode current = endNode;
|
while (current != null && visited.add(current.getX() + "_" + current.getY()) && length < maxDepth) {
|
length++;
|
current = current.getFather();
|
}
|
return length;
|
}
|
|
private List<List<NavigateNode>> buildStationMap(List<List<HashMap<String, Object>>> storedData) {
|
List<List<NavigateNode>> stationMap = new ArrayList<>();
|
for (int rowIndex = 0; rowIndex < storedData.size(); rowIndex++) {
|
List<HashMap<String, Object>> row = storedData.get(rowIndex);
|
List<NavigateNode> navigateNodeRow = new ArrayList<>();
|
for (int colIndex = 0; colIndex < row.size(); colIndex++) {
|
HashMap<String, Object> cell = row.get(colIndex);
|
NavigateNode node = new NavigateNode(rowIndex, colIndex);
|
String nodeType = cell == null ? null : stringValue(cell.get("type"));
|
String mergeType = cell == null ? null : stringValue(cell.get("mergeType"));
|
String nodeValue = cell == null ? null : stringValue(cell.get("value"));
|
|
if ("devp".equals(nodeType) || ("merge".equals(nodeType) && "devp".equals(mergeType))) {
|
node.setValue(MapNodeType.NORMAL_PATH.id);
|
JSONObject valueObject = JSON.parseObject(nodeValue);
|
node.setDirectionList(valueObject == null
|
? new ArrayList<>()
|
: valueObject.getJSONArray("direction").toJavaList(String.class));
|
} else {
|
node.setValue(MapNodeType.DISABLE.id);
|
}
|
|
node.setNodeType(nodeType);
|
node.setNodeValue(nodeValue);
|
navigateNodeRow.add(node);
|
}
|
stationMap.add(navigateNodeRow);
|
}
|
return stationMap;
|
}
|
|
private String stringValue(Object value) {
|
return value == null ? null : String.valueOf(value);
|
}
|
|
private static class BenchmarkSummary {
|
private final int stationCount;
|
private int pairCount;
|
private long astarTotalNs;
|
private long allPathsTotalNs;
|
private final List<Long> astarElapsedNsList = new ArrayList<>();
|
private final List<Long> allPathsElapsedNsList = new ArrayList<>();
|
private int maxCandidateCount;
|
private int maxAstarPathLen;
|
private int worstAstarStartStationId;
|
private int worstAstarEndStationId;
|
private long worstAstarElapsedNs;
|
private int worstAllPathsStartStationId;
|
private int worstAllPathsEndStationId;
|
private long worstAllPathsElapsedNs;
|
private int worstAllPathsCandidateCount;
|
|
private BenchmarkSummary(int stationCount) {
|
this.stationCount = stationCount;
|
}
|
|
private void record(int startStationId,
|
int endStationId,
|
long astarElapsedNs,
|
long allPathsElapsedNs,
|
int astarPathLen,
|
int candidateCount) {
|
pairCount++;
|
astarTotalNs += astarElapsedNs;
|
allPathsTotalNs += allPathsElapsedNs;
|
astarElapsedNsList.add(astarElapsedNs);
|
allPathsElapsedNsList.add(allPathsElapsedNs);
|
maxCandidateCount = Math.max(maxCandidateCount, candidateCount);
|
maxAstarPathLen = Math.max(maxAstarPathLen, astarPathLen);
|
|
if (astarElapsedNs > worstAstarElapsedNs) {
|
worstAstarElapsedNs = astarElapsedNs;
|
worstAstarStartStationId = startStationId;
|
worstAstarEndStationId = endStationId;
|
}
|
if (allPathsElapsedNs > worstAllPathsElapsedNs) {
|
worstAllPathsElapsedNs = allPathsElapsedNs;
|
worstAllPathsStartStationId = startStationId;
|
worstAllPathsEndStationId = endStationId;
|
worstAllPathsCandidateCount = candidateCount;
|
}
|
}
|
|
private String format(String mapFileName, Integer lev) {
|
return String.format(
|
Locale.ROOT,
|
"map=%s lev=%d stations=%d pairs=%d | A*=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d | allSimplePaths=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d candidates=%d | maxPathLen=%d maxCandidates=%d",
|
mapFileName,
|
lev,
|
stationCount,
|
pairCount,
|
toMillis(avg(astarTotalNs, pairCount)),
|
toMillis(percentile(astarElapsedNsList, 0.95d)),
|
toMillis(worstAstarElapsedNs),
|
worstAstarStartStationId,
|
worstAstarEndStationId,
|
toMillis(avg(allPathsTotalNs, pairCount)),
|
toMillis(percentile(allPathsElapsedNsList, 0.95d)),
|
toMillis(worstAllPathsElapsedNs),
|
worstAllPathsStartStationId,
|
worstAllPathsEndStationId,
|
worstAllPathsCandidateCount,
|
maxAstarPathLen,
|
maxCandidateCount
|
);
|
}
|
|
private double avg(long totalNs, int count) {
|
if (count <= 0) {
|
return 0.0d;
|
}
|
return (double) totalNs / count;
|
}
|
|
private double percentile(List<Long> valueList, double percentile) {
|
if (valueList == null || valueList.isEmpty()) {
|
return 0.0d;
|
}
|
List<Long> sortedList = new ArrayList<>(valueList);
|
sortedList.sort(Long::compareTo);
|
int index = (int) Math.ceil(percentile * sortedList.size()) - 1;
|
index = Math.max(0, Math.min(index, sortedList.size() - 1));
|
return sortedList.get(index);
|
}
|
|
private double toMillis(double nanos) {
|
return nanos / 1_000_000.0d;
|
}
|
}
|
}
|
