列出没有ForLoops的操作

本文关键字:操作 ForLoops | 更新日期: 2023-09-27 18:06:33

我有一个包含以下成员的类:

  • X
  • Y

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

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

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

我用for循环来实现它。

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

是否有任何方法可以使用任何。net版本(包括LINQ)来提高此任务的性能?

` `公共类RectBase{private int _rectId;private PointF _rectLocation;private size _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;
        }
    }
}

"

列出没有ForLoops的操作

问题不是消除for循环,至少在您考虑它的方式。在LINQ中重写这个只是要隐藏for循环,但它们仍然在那里。这是最根本的问题。你的算法,如所写,是O(n^2),这就是为什么当你从2万个元素增加到30万个元素时,你会看到一个可笑的时间爆炸。你在第一种情况下进行了400,000,000次比较,在第二种情况下进行了900,000,000次比较,并且它将继续像O(n^2)一样增长。

所以,你真正想问的问题是:对于这个问题,是否存在比O(n^2)具有时间复杂度的算法?

坦率地说,我不知道那个问题的答案。我怀疑的答案是否定的:你不可能知道一个点是否包含在某个矩形中,而不把它与所有的矩形进行比较,你必须检查所有的点。但也许有一种聪明的方法可以做到比如计算所有矩形的凸包,然后利用它?

这个问题是计算几何领域的一个例子。