How to partially initialize an array?

Question

I am working on optimizing for speed a method to calculate a triangle number for ProjectEuler - Problem 12.

I need to somehow be able to initialize the first element in an array:

private static ulong[] numbersArray = new ulong[5000];

One way to calculate a triangle number would be:

public static ulong GetTriangleFormula(ulong n)
{
    return n * (n + 1) / 2;
}

But it has a computational complexity somewhere between O(n) and O(n^2) so I was thinking I could trade memory for run speed by computing the numbers recursively and storing the results in a Dictionary/array. Since the triangle numbers will be calculated successively in the final solution it should work.

Computing the n-th triangle number should become a simple sum of numbersArray[n - 2] and n.

Using a Dictionary the computation was much slower for successive triangle number computation from 1 to 1000:

private static Dictionary<ulong, ulong> numbers = new Dictionary<ulong, ulong>() { { 1, 1 } };
public static ulong GetTriangleDictionaryRecursive(ulong n)
{
    if (!numbers.ContainsKey(n))
        numbers[n] = n + GetTriangleDictionaryRecursive(n - 1);
    return numbers[n];
}

I added {1, 1} to the Dictionary so that i wouldn't have to always check at the beginning of the GetTriangleDictionaryRecursive method for the base case:

if(n == 1) return 1;

But the results were that it was about 40 times slower than the formula method.

So now i am trying to write a method using an array of type ulong[] but I do not know how I can initialize only the first element with value 1 (the others being default for ulong 0).

public static ulong GetTriangleArrayRecursive(ulong n)
{
    if (numbersArray[n - 1] == 0)
        numbersArray[n - 1] = n + GetTriangleArrayRecursive(n - 1);
    return numbersArray[n - 1];
}

Thanks for your help! :)

Am I missing something? Why not just do numbersArray[0] = 1; right after you allocate it? — tenfour
– tenfour, Commented Nov 16, 2011 at 11:07
I was thinking the same, numbersArray[0] = 1; will intialise the first 1 in the array to 1.. I think you overcomplicated the question — IAmGroot
– IAmGroot, Commented Nov 16, 2011 at 11:17
@tenfour: didn't think about that cause I didn't know of static contructors or that I could just use a method to return the initialized array :D — Răzvan Flavius Panda
– Răzvan Flavius Panda, Commented Nov 16, 2011 at 11:38
@SWeko: unless the number of triangle numbers needed for the solution is higher than about 1000000, the formula solution is still faster than the array solution xD — Răzvan Flavius Panda
– Răzvan Flavius Panda, Commented Nov 16, 2011 at 12:26

Jon Skeet · Accepted Answer · 2011-11-16 11:14:10Z

1

I have no idea whether or not it's appropriate for the Euler problem, but in general if I want to do more work than a single simple expression for initialization, I do it like this:

private static readonly ulong[] numbersArray = CreateNumbersArray();

private static ulong[] CreateNumbersArray()
{
    ulong[] ret = new ulong[5000];
    ret[0] = 1;
    return ret;
}

Or you can do it in a static constructor:

private static readonly ulong[] numbersArray;

static FooClass()
{
    numbersArray = new ulong[5000];
    numbersArray[0] = 1;
}

Are you really sure it's appropriate to make this a static variable, by the way?

answered Nov 16, 2011 at 11:14

Jon Skeet

1.5m892 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Răzvan Flavius Panda Over a year ago

thanks! :) I am making the array static so it will store the triangle numbers already computed (the TriangleNumber class of which it is part is also static)

Jon Skeet Over a year ago

@RăzvanPanda: Have you considered passing the state around from method to method instead? Or creating an instance and making it instance state?

Răzvan Flavius Panda Over a year ago

I don't understand what you mean. I am using the array for storing the triangle numbers. The first time the n-th triangle number is computed it is stored in numbersArray[n-1] and since the array is static, the 2nd time I call GetTriangleArrayRecursive with the same parameter n the result is returned just by reading it from numbersArray[n-1].

Jon Skeet Over a year ago

@RăzvanPanda: But why not introduce a parameter for the array?

Răzvan Flavius Panda Over a year ago

Someone explained and I finally understood what you meant. I preferred static to a parameter thinking that I might need to use the data in another place. :)

Collectives™ on Stack Overflow

How to partially initialize an array?

1 Answer 1

5 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Related