我有一个 HashMap 形式的可达性矩阵。键是行号，值是可达性矩阵的非零列的列表。我想从这个矩阵生成先行词集。它是通过读取每列的非零条目来开发的。该矩阵有 5000 行。如果我想使用for循环来检查每个键是否存在于每个键的值集中，则迭代次数为5000*5000。我想避免这种情况。有没有一种有效的算法可以避免这么多次迭代。
最佳答案
我认为最好的方法是迭代矩阵中的值，而不是矩阵中可能存在的值。由于矩阵是按行而不是按列组织的，这意味着以相同的方式导航:
final Map<Integer, List<Integer>> reverseReachabilityMatrix = new HashMap<>();
for (final Map.Entry<Integer, List<Integer>> reachabilityMatrixRow :
reachabilityMatrix.entrySet()) {
final Integer rowNumber = reachabilityMatrixRow.getKey();
final List<Integer> columnNumbers = reachabilityMatrixRow.getValue();
for (final Integer columnNumber : columnNumbers) {
if (!reverseReachabilityMatrix.containsKey(columnNumber)) {
reverseReachabilityMatrix.put(columnNumber, new ArrayList<>());
}
reverseReachabilityMatrix.get(columnNumber).add(rowNumber);
}
}
(其中 reverseReachabilityMatrix 只是同一矩阵的按列表示)。
(注意: reverseReachabilityMatrix 中的结果列表不会按任何有意义的顺序排列。如果您需要它们，那么您需要以某种方式调整上面的内容。例如，您可以使用 for (int rowNumber = 1; rowNumber <= numRows; ++rowNumber)而不是按照其内部顺序迭代 HashMap。)
顺便说一句，虽然我保留了 HashMap<Integer, List<Integer>>为了与您已经拥有的内容保持一致，我必须说 HashMap<Integer, List<Integer>>这里似乎不是正确的数据结构，原因有两个:
- 如果您的行号是 1 到 n，并且大多数行至少有一个非零条目，那么使用数组或ArrayList结构。这不会改变渐近复杂度，但它应该会对实际运行时间产生明显的影响。
- 看起来像
contains这将是这里的一个常见操作；您会经常想要检查给定行号的可达性列表是否包含给定列号。所以一个Set，例如TreeSet，似乎更合适。 (对于ArrayList，contains方法必须迭代整个列表。)
关于java - 从矩阵的可达性矩阵中获取先行词集的最有效算法是什么，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37393034/