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是初始集合的大小。根据我的理解，通过复制构造函数创建一个集合会引发对所有元素的等于测试，因为该集合需要确保集合的契约，即没有重复的元素。这意味着对于 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²) 问题，而且您不会得到比这更好的结果。