java - 比较循环中的元素。如何最好地避免与自己比较？

Question

我得到了一些代码来优化。其中一个位包含一些代码，该代码采用带有元素的集合，并且对于集合中的所有元素，将它们与所有其他元素进行比较。比较不是对称的，所以那里没有捷径。代码如下所示:

for(String string : initialSet)
{
    Set<String> copiedSet = new HashSet<>(initialSet);
    copiedSet.remove(string);

    for(String innerString : copiedSet)
    {
        /** 
          * Magic, unicorns, and elves! Compare the distance of the two strings by
          *  some very fancy method! No need to detail it here, just believe me it
          *  works, it isn't the subject of the question!
          */
    }
}

根据我的理解，复杂度如下所示:初始循环的复杂度为 O(n)，其中 n 是初始集合的大小。根据我的理解，通过复制构造函数创建一个集合会导致对所有元素进行 equals 测试，因为集合需要确保集合的契约，即没有重复的元素。这意味着对于 n 次插入，复杂度将从 0 增加到 n-1。在最坏的情况下，删除将再次需要检查 n 个元素。内部的 for 循环然后在 n-1 个元素上循环。

到目前为止我使用的方法很简单:

for(String string : set)
{
    for(String innerString : copiedSet)
    {
        if(! string.equals(innerString)
        {
            /** 
              * Magic, unicorns, and elves! Compare the distance of the two strings by
              *  some very fancy method! No need to detail it here, just believe me it
              *  works, it isn't the subject of the question!
              */
        }
    }
}

根据我的理解，这会导致复杂度约为 O(n^2)，从而抽象出 if 子句 中代码的复杂度。

因此，第二段代码至少要好一个顺序加上我上面概述的总和。但是，我正在使用一个危险的假设，即我假设 HashSet 的复制构造函数是如何工作的。简单的基准测试表明，第二次的结果确实更好，减少了大约 n 倍。我想利用您的知识来确认这些发现，并在可能的情况下更深入地了解复制构造函数的工作原理。此外，理想的情况是找到一个按时间复杂度列出函数的资源，但我想最后一个仍然是一厢情愿的想法!

Answer 1

复制构造函数的源代码是widely available ，所以你可以研究它以及clone()看看其中一个是否适合您。

但实际上，如果您只想避免将元素与自身进行比较，那么我认为您的第二个想法涉及魔法、 unicorn 和 Elvis Sprite ，这可能是所有想法中最好的。将 Set 中的每个元素与其中的每个其他元素进行比较本质上是一个 O(n²) 的问题，您不会比这更好。