BYR Achieve · 镜像论坛

[问题]Java中BitSet与boolean数组的存取速度

2019/1/2镜像同步3 回复

判断有向图是否有环过程中，同样的算法逻辑，Boolean数组的时间7ms，BitSet时间328ms?不知道为啥。。附上代码片： Boolean数组：（bitset版就直接替换，其他都没变） public boolean canFinish(int numCourses, int[][] prerequisites) { int[] ans = new int[numCourses]; // prerequisites ArrayList<Integer>[] graph = new ArrayList[numCourses]; for(int i = 0; i < numCourses; i++){ graph[i] = new ArrayList<>(); } if(prerequisites.length == 0) return true; boolean[] visited = new boolean[numCourses]; boolean[] finished = new boolean[numCourses]; for(int[] pair : prerequisites){ int pre = pair[1]; graph[pre].add(pair[0]); } // topological sort for(int i = 0; i < numCourses; i++){ if(dfs(i, visited, finished, graph) == false){ return false; } } return true; } public boolean dfs(int pre, boolean[] visited, boolean[] finished, ArrayList<Integer>[] graph){ if(finished[pre]) return true; if(visited[pre]) return false; // cycle visited[pre] = true; List<Integer> list = graph[pre]; for(int i = 0; i < list.size(); i++){ if(dfs(list.get(i), visited, finished, graph) == false) return false; } visited[pre] = false; finished[pre] = true; return true; }

订阅后，新回复会通过你的通知中心匿名送达。