1

我的代码中有如下一行：

potentialCollisionsX.Intersect(potentialCollisionsY).Distinct().ToList();

其中，通过分析，我确定它占用了我大约 56% 的时间。我需要弄清楚如何提供有效的实现。我试过

        List<Extent> probableCollisions = new List<Extent>();
        for (int j = 0; j < potentialCollisionsX.Count; j++)
        {
            if (potentialCollisionsY.Contains(potentialCollisionsX[j]) && !probableCollisions.Contains(potentialCollisionsX[j]))
            {
                probableCollisions.Add(potentialCollisionsX[j]);
            }
        }

但这只会降低到 42%。优化或替代想法将不胜感激。

编辑：有人要求提供有关 Extent 类的信息，我想不出比提供类定义更好的方法来向他们提供信息。

    private enum ExtentType { Start, End }
    private sealed class Extent
    {
        private ExtentType _type;
        public ExtentType Type
        {
            get
            {
                return _type;
            }
            set
            {
                _type = value;
                _hashcode = 23;
                _hashcode *= 17 + Nucleus.GetHashCode();
            }
        }
        private Nucleus _nucleus; //Nucleus is the main body class in my engine
        public Nucleus Nucleus
        {
            get
            {
                return _nucleus;
            }
            set
            {
                _nucleus = value;
                _hashcode = 23;
                _hashcode *= 17 + Nucleus.GetHashCode();
            }
        }

        private int _hashcode;

        public Extent(Nucleus nucleus, ExtentType type)
        {
            Nucleus = nucleus;
            Type = type;
            _hashcode = 23;
            _hashcode *= 17 + Nucleus.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return Equals(obj as Extent);
        }
        public bool Equals(Extent extent)
        {
            if (this.Nucleus == extent.Nucleus) //nucleus.Equals does an int comparison
            {
                return true;
            }
            return false;
        }
        public override int GetHashCode()
        {
            return _hashcode;
        }
    }

Edit2：似乎使用哈希集可以使我的这部分代码达到我需要的性能，因此感谢您的帮助！

4

5 回答 5

2

Intersect无论如何都会返回不同的元素，从而使调用变得Distinct()不必要。这至少会占用你的一些时间。

另外，你真的需要打电话ToList吗？然后你对结果做了什么？

顺序重要吗？如果没有，您应该考虑使用 aHashSet<T>而不是 aList<T>作为您的“手动”代码。（并且可能还创建一个HashSet<T>for potentialCollisionsY。）这将使Contains调用更快，至少在集合足够大的情况下......

顺便说一句，不要相信文档Intersect-操作顺序是错误的（至少在 .NET 3.5 中）

于 2009-11-05T09:11:04.417 回答
2

好的，我看到了 Extent 类的定义。首先，它违反了 if obj1.Equals(obj2)==truethen的规则obj1.GetHashCode()==obj2.GetHashCode()。但这不是重点，可以修复（如果你不这样做，依赖散列的算法，比如 aHashSet将会失败）。

现在，如果可以对 Extent 对象执行的唯一操作是比较相等性，则不可能获得高于O(N*M)的最坏情况性能（其中 N 是第一个集合的大小，并且M 是第二个集合的大小）。那是因为您最终必须将每个元素与每个元素进行比较。

这可以通过使用GetHashCode()具有不同哈希码的对象本身也不同的事实来做得更好。其他人建议使用HashSet该类，这将是一个解决方案。在这种情况下，最好的情况是O(N+M)，最坏的情况是O(N+N*M)。平均而言，尽管您应该获胜，除非该GetHashCode()方法实现得很差并且为许多对象返回相同的哈希码。

我自己更喜欢更稳定的解决方案。如果可以对范围类进行可靠排序（也就是说，如果您可以比较两个范围对象以查看哪个更大，哪个更小），那么您可以对两个列表进行排序并且性能可以降低到O(sorting+ M+N)。这个想法是，当列表被排序时，您可以同时浏览它们并在那里寻找相等的元素。

现在排序性能是棘手的事情。如果您只实现比较操作（如在IComparable接口中），您将能够在时间O(N*logN+M*logM)对两个列表进行排序。标准List.Sort()方法应该为您做到这一点。总而言之，总性能将是O(N*logN+M*logM+N+M)。但是您应该注意，这使用了 QuickSort 算法，该算法在几乎排序的列表上表现不佳。最坏的情况是一个完全排序的列表，在这种情况下它是O(N*M)。如果您的列表已经接近排序，您应该考虑另一种排序算法（并自己实现）。

可靠速度的最终结果是，如果您可以将每个 Extent 转换为整数（或更一般地，某个字符串），并且具有以下属性：如果字符串相等，则 Extents 也相等，如果字符串不相等，则范围也不相等。字符串的问题是它们可以使用基数排序、基数树等算法在线性时间进行排序。然后排序只需要O(N+M)的时间。事实上，如果你构建了一个基数树，你只需要对第一个列表进行排序，就可以直接在其中搜索字符串（每次搜索都需要O(1)时间）。总而言之，总性能将是O(N+M)，这是最好的。

不过，您应该始终牢记一件事-大型算法具有很大的常数。基数方法在纸面上可能看起来最好，但实施起来非常棘手，而且通常比处理少量数据的简单方法慢。只有当您的列表包含数千和数万范围内的元素时，您才应该开始考虑这一点。此外，这些算法需要创建大量新对象，并且每次new()操作的成本也变得很大。您应该仔细考虑以尽量减少所需的分配数量。

于 2009-11-05T10:00:13.610 回答
1

如果您无法提出更好的解决方案，请考虑使用非托管代码作为最后的手段。

于 2009-11-05T09:10:02.297 回答
1

试试这个：

HashSet<Extent> result = new HashSet<Extent>();
HashSet<Extent> potentialSetY = new HashSet<Extent>(potentialCollisionsY);
foreach (Extent ex in potentialCollisionsX)
    if (potentialSetY.Contains(ex))
        result.Add(ex);

哈希集擅长Contains快速做，但不保持顺序

如果您需要保持顺序，这里有一些更复杂的东西：有序哈希集。它使用普通的哈希集语义（好吧，一个字典，但它是同一件事），但在枚举之前它根据插入顺序重新排序项目。

// Unchecked code

public class OrderedHashSet<T> : IEnumerable<T> {
    int currentIndex = 0;
    Dictionary<T, index> items = new Dictionary<T, index>();

    public bool Add(T item) {
        if (Contains(item))
            return false;
        items[item] = currentIndex++;
        return true;
    }

    public bool Contains(T item) {
        return items.ContainsKey(item);
    }

    public IEnumerator<T> GetEnumerator() {
        return items.Keys.OrderBy(key => items[key]).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

现在只需在上面的示例中更改HashSet为，它应该可以工作。OrderedHashSet

于 2009-11-05T09:27:01.203 回答
0

两种方法：

如果项目不存在，则将它们放入哈希图中，否则在哈希图中将它们标记为重复。这是 O(n)。然后，您遍历哈希图中的所有项目，并查看它们是否被标记为重复 - O(n) 再次。

另一种方法：

对两个列表进行排序。这是一个 O(n lg n) 操作，但至关重要的是，您可能可以愉快地保持两个列表始终排序，因此在专门寻找交集等时不会花费成本。

然后按顺序浏览这两个列表，找到不同的和重复的 etc 条目。这是 O(n)。

于 2009-11-05T10:21:33.367 回答