StackOverflowException avec de grandes listes

Question

Il y a une tâche très simple que je veux faire, qui fait en quelque sorte planter le programme.

J'ai une liste de nombre contenu à l'intérieur, tous uniques. Passé un certain nombre, je veux inverser la commande.

Exemple: 5, 16, 11, 3, 8, 4 -> 5, 16, 11, 4, 8, 3 3 lors de l'utilisation en tant que point de pivotement.

Voici une des nombreuses méthodes que j'ai essayées.

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; 
} 

Maintenant, cela fonctionne. Ce n'est peut-être pas la solution optimale, mais cela fonctionne. J'utilise cette méthode depuis un certain temps, mais maintenant j'ai atteint un point où le nombre d'éléments dans la liste devient extrêmement important (plus de 6000). Finalement, je reçois une exception StackOverFlowException lorsque j'essaie d'ajouter quelque chose à newPath.

Je suis sûr à 100% qu'il n'y a pas de boucle infinie comme les revendications VS. J'ai essayé d'autres méthodes telles que l'obtention directe de la gamme d'éléments, les boucles for et foreach au lieu de while, toutes finissent par tomber en panne. Il semble que la quantité de données est juste trop grande. Et ça va juste grossir (jusqu'à 20 000).

Preuve: même cela fera le programme lancer une exception: (?) Liste <int> Newpath = nouvelle liste <int> (OldPath);

Une idée de ce qui est à l'origine de ceci/comment le réparer?

-Depuis un débutant.

Answer 1

Le dépassement de pile ne doit pas figurer dans le code que vous nous montrez, car il n'y a pas de récursion. Recherchez où votre code récursive. Mieux encore, quelle est la trace de pile que vous obtenez lorsque vous obtenez votre StackOverflowException? Cela vous dira où dans votre récursivité que votre code va dans une boucle récursive infinie. Une ancienne boucle infinie simple ne provoquera pas StackOverflowException. Pour que cela se produise, vous devez avoir une récursivité qui ne se termine pas, jusqu'à ce que votre pile soit épuisée.

Answer 2

Un StackOverflowException ne se produit pas parce que vous avez trop d'éléments dans un List (ce serait OutOfMemoryException), il arrive quand vous faites trop d'appels de méthode, généralement à cause de la récursivité.

En note, 6 000 int s dans un List est rien. Je viens d'exécuter un code de test et il ajoute jusqu'à 67 millions d'entiers à la liste avant d'obtenir un OutOfMemoryException.

Answer 3

je ne serais probablement résoudre cela comme:

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]); 
    } 
} 

Il utilise double de l'espace de liste originale, mais avec 20k ce n'est pas vraiment un problème, et pour moi au moins, il est beaucoup plus lisible - et ne devrait pas a frappé des exceptions StackOverflow

mon algorithme de révision être (pas testé que le premier, et pas beaucoup de pensée entra dans la meilleure façon de calculer l'état pour)

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

Je suis d'accord avec @Eddie - on dirait que vous ne nous montrez pas le code qui provoque le débordement de la pile - le code que vous nous montrez ne provoquera pas de débordement de pile.

Une autre solution, en utilisant .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

Merci pour vos réponses, il a aidé mon identifier le problème

J'ai une récursion avant. Cependant, je suis certain que ce n'est pas infini (c'est pourquoi je ne pensais pas que c'était le problème, d'autant plus que ce n'était pas le lieu du débordement). Il peut être grossièrement décrit comme:

Recherche (paramètres)
--SomeParameters.ShiftPath
--la le décalage utile?
---- Oui -> Sortie récursive
---- Non -> Pouvons-nous déplacer plus?
------ Oui -> Rechercher (nouveaux paramètres)
------ Non -> BackTrack

(Les effets de la recherche est fortement dépendante des données fournies par les milliers d'autres lignes de codes - le code a bien fonctionné pour les petits problèmes cependant.)

Parce qu'il peut aller très très profond avant de trouver une réponse, je suppose que c'est ce qui provoque le débordement droit? Je pense que je vais essayer une autre méthode comme celle-ci, en utilisant le tas à la place.

while (aussi longtemps que nécessaire)
--ArrayOfParameters.Last() ShiftPath
--la le décalage utile?
---- Oui -> Boucle de sortie
---- Non -> Pouvons-nous déplacer plus?
------- Oui -> Ajouter des paramètres actuels à ArrayofParameters
------- Non -> Backtrack - Supprimer ArrayOfParameters.Last()