StackOverflowException with large lists

Question

There is very simple task I want to do, that somehow makes the program crash.

I have a list of number contained within, all unique. Past a certain number, I want to invert the order.

Example : 5, 16, 11, 3, 8, 4 -> 5, 16, 11, 4, 8, 3 when using 3 as the pivot point.

Below is one of the many methods I tried.

private List<int> ShiftPath(List<int> oldPath, int shift)
{
    List <int> newPath = new List<int>();
    int counter = 0;
    // Start reordering
        // Forwards
    while (oldPath[counter] != shift)
    {
        newPath.Add(oldPath[counter]);
        counter++;
    }
        // Backwards
    counter = oldPath.Count - 1;
    while (oldPath[counter] != shift)
    {
        newPath.Add(oldPath[counter]);
        counter--;
    }
        // New endpoint
    newPath.Add(shift); 

    // Update

    return newPath;
}

Now this works. It may not be the optimal solution, but it works. I've been using this methods for quite a while, but now I've reached a point where the number of items in the list becomes extremely big (above 6,000). Eventually, I get an StackOverFlowException when trying to add something to newPath.

I'm 100% sure there is no infinite loop like VS claims. I've tried other methods such as getting the range of items directly, for and foreach loops instead of while, all crash eventually. It seems that the amount of data is just too big. And it's just going to get bigger (upwards to 20,000).

Proof (?) : even this will make the program throw an exception : List <int> newPath = new List<int>(oldPath);

Any idea on what is causing this/how to fix it?

-From a beginner.

Answer 1

The stack overflow must not be in the code you're showing us, as there is no recursion there. Look for where your code does recursion. Better yet, what's the stack trace you get when you get your StackOverflowException? That will tell you where in your recursion that your code is going into an infinite recursive loop.

A plain old infinite loop will not cause StackOverflowException. For that to occur, you need to have recursion that doesn't end, until your stack is exhausted.

Answer 2

A StackOverflowException doesn't occur because you have too many items in a List (that would be OutOfMemoryException), it happens when you make too many method calls, usually because of recursion.

As a side note, 6,000 ints in a List is nothing. I just ran some test code and it adds up to 67 million integers to the list before I get an OutOfMemoryException.

Answer 3

I would probably solve this like:

List<int> reverseMe = new List<int>();
List<int> reversedList = new List<int>();

reverseMe.Add(5);
reverseMe.Add(16);
reverseMe.Add(11);
reverseMe.Add(3);
reverseMe.Add(8);
reverseMe.Add(4);

int pivotPoint = 3;

for (int c = 0; c < reverseMe.Count; c++)
{
    if (c >= pivotPoint)
    {
        reversedList.Add(reverseMe[reverseMe.Count - c + pivotPoint - 1]);
    }
    else
    {
        reversedList.Add(reverseMe[c]);
    }
}

This uses double the original list's space, but with 20k that's not really a problem, and to me at least it is far more readable - and shouldn't hit any StackOverflow exceptions

Revising my algorithm to be (not as tested as the first, and not a lot of thought went into the best way to calculate the for condition)

int temp;
for (int c2 = pivotPoint; c2 < reverseMe.Count - ((reverseMe.Count - pivotPoint) / 2); c2++)
{
    temp = reverseMe[reverseMe.Count - c2 + pivotPoint - 1];
    reverseMe[reverseMe.Count - c2 + pivotPoint - 1] = c2;
    reverseMe[c2] = temp;
}

Answer 4

I have to concur with @Eddie - it looks like you're not showing us the code that's causing the stack overflow--the code that you're showing us won't cause a stack overflow.

Another solution, using .NET 3.5:

class Program
{
    static void Main(string[] args)
    {
        const int where = 5;
        var aList = new List<int>();
        for (var i=0; i < 100; i++)
            aList.Add(i);

        var reversed = aList.Take(where).Concat(Enumerable.Reverse(aList)
            .Take(aList.Count - where));

        Console.WriteLine(String.Join(",",
            reversed.Select(i => i.ToString()).ToArray()));
        Console.ReadLine();
    }
}

Answer 5

Thank you for your answers, it helped my identify the problem

I do have a recursion before that. However I am positive it is not infinite (which is why I didn't think it was the problem, especially since it wasn't where the overflow occurred). It can roughly be described as :

Search(parameters)
--SomeParameters.ShiftPath
--Was the shifting useful?
----Yes -> Exit recursion
----No -> Can we shift more?
------Yes -> Search(new parameters)
------No -> Backtrack

(The effects of the search is heavily dependent on the data given by the thousands of other lines of codes - the code did work for smaller problems though.)

Because it can go very very deep before finding an answer, I guess that is what causes the overflow right? So I think I will try another method such as this, using the heap instead :

While(as long as needed)
--ArrayOfParameters.Last().ShiftPath
--Was the shifting useful?
----Yes -> Exit loop
----No -> Can we shift more?
-------Yes -> Add current parameters to ArrayofParameters
-------No -> Backtrack - Delete ArrayOfParameters.Last()