c# - 没有 For 循环的列表操作

Question

我有一个类(class)，成员如下:

• X
• 是
• 宽度
• 高度

可以使用这些参数创建一个矩形。

现在我的问题是我有这个类的列表，List<MyClass> .

我需要将列表中的每个对象与所有剩余对象进行比较，如果 currentObject.Location(X, Y)落在 rectangle(X, Y, Width, Height)其他对象，我需要从列表中删除其他对象。

我用 for 循环实现了它。

但主要问题是:性能。 我的最小列表数是 300000。

是否有任何程序可以使用包括 LINQ 在内的任何 .Net 版本来提高此任务的性能？

`公共(public)类RectBase { 私有(private) int _rectId； 私有(private) PointF _rectLocation； 私有(private)SizeF _rectSize;

    public RectBase()
    {
        _rectId = -911;
        _rectLocation = new PointF(0, 0);
        _rectSize = new SizeF(0, 0);
    }
    public RectBase(int id, PointF loc, SizeF size)
    {
        _rectId = id;
        _rectLocation = loc;
        _rectSize = size;
    }
    public bool IsIntersected(RectBase otherRectObject)
    {
        RectangleF currentRect = new RectangleF(_rectLocation, _rectSize);
        if (currentRect.Contains(otherRectObject.RectLocation))
            return true;
        else
            return false;
    }
    public int RectId
    {
        get { return _rectId; }
        set { _rectId = value; }
    }
    public PointF RectLocation
    {
        get { return _rectLocation; }
        set { _rectLocation = value; }
    }
    public SizeF RectSize
    {
        get { return _rectSize; }
        set { _rectSize = value; }
    }
}


public class RectProcessor
{
    List<RectBase> _rectList;
    int maxCount = 300000;

    public RectProcessor()
    {
        _rectList = new List<RectBase>();
        FillList();
    }

    private void FillList()
    {
        //  Adding the items to the list with dummy values
        for (int i = 0; i < maxCount; i++)
        {
            int id = i+1;
            PointF loc = new PointF(id, id);
            SizeF sz = new SizeF(id, id);

            RectBase obj = new RectBase(id, loc, sz);

            _rectList.Add(obj);
        }
    }

    private void RemoveIntersectedObjects()
    {
        List<RectBase> filteredList = new List<RectBase>();
        bool isIntersected = false;

        for (int i = 0; i < maxCount; i++)
        {
            for (int j = 0; j < maxCount; j++)
            {
                if (_rectList[i].IsIntersected(_rectList[j]))
                {
                    isIntersected = true;
                    break;
                }
            }
            if (!isIntersected)
            {
                filteredList.Add(_rectList[i]); 
            }
            isIntersected = false;
        }
    }
}

`

Answer 1

问题不在于消除 for 循环，至少在您考虑它的方式上如此。在 LINQ 中重写它只会隐藏 for 循环，但它们仍会存在。这就是根本问题。您编写的算法是 O(n^2)，这就是为什么当您从 20,000 个元素增加到 300,000 个元素时，您会看到一个荒谬的时间爆炸。您在第一种情况下进行了 400,000,000 次比较，在第二种情况下进行了 90,000,000,000 次比较，并且它将继续像 O(n^2) 一样增长。

所以，你真正想问的问题是:对于这个问题，有没有时间复杂度优于O(n^2)的算法？

坦率地说，我不知道这个问题的答案。我怀疑答案是否定的:如果不将某个点与所有矩形进行比较，您将无法知道某个点是否包含在某个矩形中，并且您必须检查所有点。但也许有一种聪明的方法可以做到这一点，例如计算所有矩形的凸包并以某种方式使用它？

本题以computational geometry字段为例.