Any performance difficulties related to List<Type>?

Question

I'm using the following structure:

class Map
{
    public List<List<Point>> points;
    public List<Base> bases;
}

Point and Base are over-normal sized classes (has more than 30 attributes).

And I'm iterating this Map class like this:

public static void calculateMatrix(Map map) 
{
    LineOfSight.LineOfSight los = new LineOfSight.LineOfSight();

    foreach (var b in map.bases)
    {
        foreach (var cc in map.points) 
        {
            foreach (var c in cc)
            {
                calculatePointValues(c, b, los);
            }
        }
    }
}

There is around 500*500 points List<List<T>> and around 10 bases.

This iterating is calling calculatePointValues method around 2.5 million.

And my application can be initiated around 30 seconds.

Shall I use Array instead of List<>? Shall I use for() instead of foreach?

Or, what should I do?

Answer 1

Your performance problem primarily stems from your algorithmic complexity; the loops themselves are reasonable, and any changes you make to either the types involved or using "for" instead of "foreach" instead of LINQ won't actually gain you too terribly much in terms of performance. The use of parallelization will result in a speedup by spreading the work out across more processors, but it won't actually reduce the total amount of work you're asking be done. If it is the absolute last resort, then tuning the aspects I've just mentioned might be all you can get in terms of speedup, but what's really interesting is the contents of calculatePointValues().

What you're showing, right now, is that you have an \$O(N^3)\$ algorithm complexity. That's a bad thing :). If you have to touch (# of bases * rows * columns) in order to calculate each {row,col} pair's value for each Base, and you must pre-calculate them (e.g., you can't calculate them on demand, as you need each point) then you might be in "absolute last resort" territory.

Now, I'm not an expert on either matrix math or graph theory. However, given that you have only one los object for all of the bases and all of the points, and bases all seem to be on the same map, it seems reasonable that there may exist an algorithmic rabbit you could pull out of your hat to reduce this to \$O((rows*cols) + base)\$ (a.k.a. \$O(N^2)\$).

Now, with all of that said, down to code.

Class Organization

CalculateMatrix() and CalculatePointValues() should probably be part of Map. I don't have a lot of programmatic structure to base that on (you've pasted skeleton code, really :)), but it seems silly to have a second class who consumes a Map to spit out auxiliary data about that Map. If this other class is supposed to be generic/be performing a re-usable algorithm, it should take more generic inputs. If it's performing functions on Maps, relevant to Maps and things that consume Maps, it should be part of Map.

I have a similar complaint for LineOfSight, which seems to be extra-nutty because its type has a nested type of the same name. LoS calculations seem like something that should belong with the Map.

Outputting to Nowhere

Your los object doesn't go anywhere. The result of all that churning is placed in a local variable that loses scope once the function ends, and that makes no sense at all.

Encapsulation

In Map, Don't use public containers, unless this Map class is hidden away inside another class for private use only. If you must expose these publicly, you should use interfaces (e.g., IList<IList<Point>>) instead of concrete container types, and make these properties, not public members.

Remember that C# doesn't have any good way to expose containers with non-modifiable contents. The containers themselves can be returned so that they are read-only (you can't modify which object references are or are not inside the container), but the contents within them can still be changed (you could mutate a Base or a Point using their reference, if they have mutator functions). Keep in mind that this breaks encapsulation, and try to make the contained classes (Point and Base, in these cases) immutable if possible.

Answer 2

As was said in the comments, I don't think List<T> makes any significant difference over an array.

But with a bit of LINQ you can reduce the nesting a bit:

foreach (var b in map.bases)
{
    foreach (var c in map.points.SelectMany(cc => cc))
    {
        CalculatePointValues(c, b, los);
    }
}

And it could be worth trying to profile it with some Parallel looping as well:

Parallel.ForEach(map.bases, b =>
    {
        foreach (var c in map.points.SelectMany(cc => cc))
        {
            CalculatePointValues(c, b, los);
        }
    });

Answer 3

I think speed will only increase a bit, if at all, if you use arrays (The List implementation you use may already use an array). But you will reduce memory consumption if you switch to an array based implementation if you reduce the number of objects used this way.

You should profile both implementations to compare speed and memory consumption.