And again, how to handle a huge collection in C#

0

Issue

The first part of my ‘task’ was to find all addends (partition) of a number (in my case 365) with all possible permutations of those sequences.

For example: for number 3 we have three possible addend sequences (3) (1;2) (1;1;1) but my method gives (3) (1;2) (2;1) (1;1;1) as I needed.

IEnumerable<int[]> SplitAddends(int n) {
    for (int i = 1; i < n; i++) {
        var part = SplitAddends(n - i);
        foreach (var array in part) {
            var newArray = new int[array.Length + 1];
            newArray[0] = i; 
            Array.Copy(array, 0, newArray, 1, array.Length);

            yield return newArray;
        }
    }
    yield return new []{n};        
} 

This method gives a result in less than 1 ms and it’s correct. The problem is the second part of this task. I need to do some calculations with each element.
For example:

void ExampleMethod(int N) {
    var partition = SplitAddends(N); // < 1ms execution time
    foreach (var variant in partition) { // problematic line
        var someResult = 0f;
        foreach (var item in variant) {
            someResult += SomeEquation(item);
        }
        SendToCompare(someResult);
    }
}

It takes several seconds for numbers like 15-25 (for N=20 partition has 524288 sequences) and it takes hours for numbers like 35-50.

I’ve already tried things like Parallel.ForEach, while(partition.MoveNext()) and changing the type of collection. Even partition.Count() takes years for execution.

I know about one workaround for that. The calculations may be put inside of SplitAppends method and be executed in a top layer of stack but this way seems tricky.

Solution

So I found the problem. The ‘yield’ doesn’t give me any result at the time when the method is called. Only when I’m using the yielding elements. That’s why this method is finished in 1 ms and ‘foreach’ takes so long. And the problem has ~O(2^N) difficulty, that’s why we can’t use if for N=360.

Answered By – Mortaly

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave A Reply

Your email address will not be published.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More