列出没有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;
}
}
}
"
问题不是消除for
循环,至少在您考虑它的方式。在LINQ中重写这个只是要隐藏for
循环,但它们仍然在那里。这是最根本的问题。你的算法,如所写,是O(n^2)
,这就是为什么当你从2万个元素增加到30万个元素时,你会看到一个可笑的时间爆炸。你在第一种情况下进行了400,000,000次比较,在第二种情况下进行了900,000,000次比较,并且它将继续像O(n^2)
一样增长。
所以,你真正想问的问题是:对于这个问题,是否存在比O(n^2)
具有时间复杂度的算法?
这个问题是计算几何领域的一个例子。