0

Or let me give a specific example.

Suppose I'm writing a method that returns all subsets of a List<int>. Let n = .Count. I know that there will be n^2 subsets (let's say stored as List<int>s) and each will be between size 1 to n. I know therefore that allocating

n^2 * n * sizeof(int) + [some extra space]

should open enough space.

I expect that each new List<int>(capacity: n) I create for a subset will be allocated quickly.

Is there a way to do this pre-allocation, or is my thinking all wrong?

user2967799
  • 221
  • 7
  • 12
  • You should really look to change the downstream code such that you don't need every single subset materialized all at once. Given how fast that scales with the size of the original list, for very small lists you won't care about this at all, and for very large lists you won't have the space no matter how you try to allocate it. This would only ever have a chance of being useful for a very small range of values, and if you're at that point, you'll likely exceed it soon. – Servy Mar 18 '23 at 16:28
  • Does this answer your question? [C# - What is List initial capacity used for?](https://stackoverflow.com/questions/25429652/c-sharp-what-is-listt-initial-capacity-used-for) – Charlieface Mar 18 '23 at 22:01
  • @Servy It's a LeetCode problem: no way to change downsteam code :) – user2967799 Mar 19 '23 at 15:17

2 Answers2

2

Technically you can create all your lists and fill them with the number of items you will fill into them, but you can fill them with junk and then just override the values.

But, you should not invest too much effort into optimizing a code that's not (yet) having performance issues. You should implement your program in the most natural way and make sure it works. Measure the time. Do stress tests. If you have a performance issue, then you will have far more information about the issue when you have it than beforehand, when you plan your code. You may try to optimize a problem that would never exist anyways.

So, if you are worried about your method's performance, then you should also implement the "creation" and "addition" to the sublist that you are to return. At first, you can implement the creation as a new List and the addition as a call to the .Add() method. Later on, if you end up having performance issues, then you will change these methods so, the "creation" will just return the already created list and the "addition" will just change the value at an index.

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
0

The List<T> constructor accepts an optional capacity parameter that tells the list how many elements to preallocate.

Jonathan Wood
  • 65,341
  • 71
  • 269
  • 466