# Any performance difficulties related to List<Type>?

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?

-
Unless I'm very mistaking, both an array and List<T> have O(1) lookup time so there will be no difference in performance. If there is anything we can say with respect to performance then you should probably give more information about what it is exactly you use this for afterwards and how these collections are used. –  Jeroen Vannevel Apr 25 at 14:10
In C#, methods are named in PascalCase. Private methods have no official standard since only your team sees them, but most people still name them in PascalCase. Really, only fields and variables are named in camelCase. –  Magus Apr 25 at 14:34
@Magus: both are a form of CamelCasing. But yes, I agree although I use the _ prefix myself for most fields. –  Jeroen Vannevel Apr 25 at 14:37
@JeroenVannevel: While that's true, the C# documentation refers to them separately, making the distinction I did. And saying that one is part of the other does not change the fact that it is more specific to refer to them separately, as I did. As to underscoring fields, that becomes less important if your syntax highlighting colors them differently. –  Magus Apr 25 at 14:40
If you're going to use such short names, at least be consistent: b for base is fine, but c for point? –  David Harkness Apr 25 at 15:21

## 3 Answers

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.

-
Nice answer! Wouldn't ReadOnlyList<T> address your last point? –  Mat's Mug Apr 25 at 17:23
The answer, in a word, is "no," and this is a very common misconception/misunderstanding. A ReadOnlyList<T> cannot be added to or removed from -- the list itself is fixed; it's a list that you can only read from. However, if T is a reference, then I can still call mutator functions on T. Say it was ReadOnlyList<StringBuilder> rol. I could call rol[0].Append("Hey, I just changed something!"), and that would be OK -- because I didn't modify the list, I modified an object the list happens to point at. –  Travis Snoozy Apr 25 at 17:27
By contrast, C++ has true read-only containers -- but you have to carefully mark up each of your class' member functions with the "const" keyword (at the end of the signature), to tell the compiler which members are "observers." Any member that is not an "observer" is automatically considered a "mutator," and the compiler will not let you call those methods if you are passed a type* const, const type&, or a const type (or containers holding the same). –  Travis Snoozy Apr 25 at 17:31
+1 for great answer.... shame I can't add another +1 for good mathjax bling too. –  rolfl Apr 26 at 11:47
I give a +1 for you, too @rolfl :) –  Enes Unal Apr 26 at 16:58

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);
}
});

-
+1, for the sake of less nested foreaches. –  Magus Apr 25 at 15:11
+1 for simplicity and parallel foreach. –  Enes Unal Apr 26 at 16:56

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.

-