java - 配对不同集合中的元素 : how to avoid deep neSTLed for loops?

Question

在尝试解决我遇到的图形拓扑问题时，我发现自己写了一段我见过的最可怕的代码。在进入细节之前，让我先把问题说清楚:我有大量的嵌套循环/条件，我想知道是否有办法避免它。

我有以下对象供我使用:

1. 数据集，它是来自特定实验的数据点的集合。这些数据点包含与 Set 有(1 -> 许多)关系的 Element。 (大约大小为 2-5K 个元素)

2. 一个数据库，它是所有Element和Set的引用，无论它们是在实验中观察到的还是不是。此对象还具有用于数据检索的方法……(大约 30K 个元素，10K 个集合)

3. 根据数据集 (#1) 评估的 Set 的集合。

我想做的是构建一个以 Element 为节点，以 Set 成员关系为边的图。

示例: 取两个元素，e1 和 e2。假设 e1 是集合的成员:S1、S2 和 S4；而 e2 是 S1、S3 和 S4 的成员。在这种情况下，e1 和 e2 之间应该有两条边，分别表示集合 S1 和 S4。

请注意，Dataset 对象通常包含 Database 中存在的一小部分 Element，因此在上面的示例中有一个大量不应出现在图中的其他元素(因为它们不在 Dataset 中)，即使它们属于所讨论的集合。

考虑到这个问题，我的“简单”(阅读:天真)解决方案(伪代码)是循环:

1. 数据集 --> for (data d : dataset)
2. 集合 d 是 --> for(set s : database.getSetsWith(d))
的成员
3. s 的元素 --> for (elem e : s.getElements())
4. 数据集中剩余的元素 --> for(data dx : dataset - d)

AND 创建 (d, dx) 对，如果这两个元素是集合 s 的一部分。

此解决方案由 4 个嵌套的 for 循环和深入到最终配对的条件检查组成。它丑陋、缓慢，而且容易出现问题。但我不确定我还能做些什么。

建议？

---

引用:

• https://softwareengineering.stackexchange.com/questions/213910/maximum-nesting-for-loops-and-conditionals

• https://softwareengineering.stackexchange.com/questions/199196/why-are-nested-loops-considered-bad-practice

Answer 1

此过程的复杂性(代码方面和理论上的复杂性)是输入和输出数据结构的函数。如果您的 Dataset 和 Set 类(正确地)实现了 java.util.Set，那么从代码清晰的角度来看可能会有所帮助，并且它会打开如果您的 Element 类提供满足 Collections API 期望的 equals(Object) 以及相应的 hashCode() 方法，则有几扇门. (如果引用相等性适合您的 Element，那么您就不需要其他任何东西了。)

有了这些东西，这就不那么复杂了，而且看起来和感觉起来也更干净了:

1. 创建一个 java.util.HashSet，其中包含您的 Dataset 的所有元素(称之为 dataElements)。
2. 从 dataElements 中删除任何元素 e。
3. 对于e所属的每个集合s，
   1. 创建 java.util.HashSet 副本，s1，s
   2. 在s1中形成s1和dataElements的交集
   3. 对于 s1 中的每个剩余元素 e1，在 e 和 e1 之间创建一条(无向)边。
4. 如果dataElements不为空，返回步骤(2)

在代码中，也许看起来像这样:

HashSet<Element> dataElements = new HashSet<>(dataset);
Iterator<Element> dataIterator = dataElements.iterator();

while (dataIterator.hasNext()) {
    Element e = dataIterator.next();

    dataIterator.remove();
    for (com.my.Set<Element> s : database.getSetsWith(e)) {
        HashSet<Element> s1 = new HashSet<>(s);

        s1.retainAll(dataElements);
        for (Element e1 : s1) {
            // create edge (e, e1, s) ...
        }
    }
}

即使您的类没有实现java.util.Set，您也可以做类似的事情——这部分主要是为了方便制作副本(通过HashSet构造函数) .您的 Element 类确实需要提供合适的 equals() 和 hashCode() 方法，但是，如果这些方法由 Object 不行。

注意事项:

• 我提出的方法很自然地避免了产生不需要的重复边(假定由不同集合中的共同成员产生的边需要作为单独的边)。
• 检查散列中的成员资格非常快(O(0)，给定相当好的散列函数)，并且您需要进行大量成员资格检查。很少有其他类型的集合数据结构能够如此高效地执行成员资格检查。
• 该方法以复制某些数据结构为代价，减少了一层嵌套循环。 (制作副本以便算法可以自由销毁它们。)
• 该方法不涉及条件。

更正:该方法在算法的第 (4) 步仅涉及一个显式条件。这对应于最外层循环的 while() 条件。此外，增强的 for 循环具有相同类型的隐式条件。我假设循环终止条件不是困扰您的条件。