ArrayList Capacity, what is better? c#

Question

I have an input which is about 450 today, and it might increase in the future. (Sometimes it is run with less than 450, maybe 100 or 20)

Is it better for me to:

• not set capacity
• set capacity low (100)
• set capacity sligthly less than 450
• set capacity sligthly above 450
• set capacity moderatly above 450
• set capacity to something way above expected (80% more?, twice?)

using n as number of increases (not actual complexity) I'm, thiniking that setting it to less than expected n=440 or something will give me "complexity" n + 2n = (3n)

whereas if i put it slightly above (n=460) will give just n

also if i set n = 800 gives me a high n (almost 2n) ( high but then i use TrimToSize to make it better?

What is the best choice?

Answer 1

_{I'll be honest, I glossed over all the talk of n as I believe it detracts from the real point, which is relative efficiency.}

The "best choice" is to use System.Collections.Generic.List<T>, initialize it to something sensible and then don't worry about it until profiling tells you it's a problem.

The use of the generic list gives you strong typing support, and with value types, avoids boxing issues.

If the list size is constantly changing, or the list doesn't live for very long, trimming it won't offer much improvement (if any). If you know certain things about the sizes involved, you can save a few re-allocations by using the overloaded constructor that takes an initial capacity:

var list = new List<int>(450);

After the initial capacity is hit, the list will continue to resize using it's own internal logic to decide how much more to grab (the default if you don't specify a size is to double the size: starts at 4, then 8, 16, 32, etc).

Answer 2

• with these numbers (< 1000) , it won't matter very much.

• without an initial Capacity you will grow 8, 16, 32, 64 etc. log(n) re-allocations.

So just use any value that is somewhat near the target. 400 is as good as 800 here. You will have maybe 1 re-allocation, and an overshoot in space of almost N is unavoidable.

Answer 3

ArrayList is for .net 1.1

you can use List<T> is a generic class.

It supports storing values of a specific type without boxing to and unboxing from object. ArrayList simply stores object references.

1. Using List avoid Boxing/unboxing operation, which saves your memory n time.

Answer 4

Is there a reason why you can not use a Generic List? This will expand / contract to the number of elements you need to store. If you must use an array then I would set it to double the max value that you can expect (i.e. 800) since this is a relatively small number. For numbers this will be a small amunt of memory to allocate.