java - 从矩阵的可达性矩阵中获取前因集的最有效算法是什么

Question

我有一个 HashMap 形式的可达性矩阵。键是行号，值是可达性矩阵的非零列列表。我想从这个矩阵生成前提集。它是通过读取每列的非零条目开发的。矩阵有 5000 行。如果我想使用 for 循环来检查每个键是否存在于每个键的值集中，那么迭代次数为 5000*5000。我想避免这种情况。有没有什么有效的算法可以避免这么多次迭代。

Answer 1

我认为最好的方法是迭代矩阵中是的值，而不是可能在矩阵中的值。由于矩阵是按行而不是按列组织的，这意味着以相同的方式导航它:

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 方法必须遍历整个列表。)