Techniques to control stack overflows?
Basically, my program will try to generate the list of all possible lowercas开发者_如何转开发e 5-letter words. Including all combinations that clearly are not real words like jshcc or mmdzq.
I do that by stacking up a massive amount of calls for a function, which does the word work.
But that's simply too much, and I get a stack overflow error.
How would someone control that?
Basically, convert from recursion to iteration. Typically that involves creating a Stack<T>
as a "logical" stack, or something similar.
However, I'd have expected a method generating a list of all possible 5-letter words to only have a stack about 5 deep - one for each letter. Each stack level would be responsible for one level of letter - so the "top" of the stack would iterate through each possible last letter; the next stack frame down would iterate through every possible fourth letter, calling the method recursively to iterate through all possible last letters etc. Something like this (C# code, but hopefully you can understand it and apply it to VB):
const string Letters = "abcdefghijklmnopqrstuvwxyz";
public static List<string> GenerateValidWords(int length)
{
List<string> words = new List<string>();
GenerateValidWords(0, new char[length], words);
return words;
}
private static void GenerateValidWords(int depth, char[] current,
List<string> words)
{
foreach (char letter in letters)
{
current[depth] = letter;
if (depth == current.Length - 1)
{
string word = new string(current);
if (IsValid(word))
{
words.Add(word);
}
}
else
{
GenerateValidWords(depth + 1, current, words);
}
}
}
Now if you don't have any sort of filtering, that's going to generate 11,881,376 words - which at 24 bytes each (on x86) is about 285MB - plus all the space for the list etc. That shouldn't kill a suitably big machine, but it is quite a lot of memory. Are you sure you need all of these?
As a simple solution, I would use an iterative method with multiple loops in order to generate these words:
Dim words As New List(Of String)
Dim first As Integer = Asc("a")
Dim last As Integer = Asc("z")
For one As Integer = first To last
For two As Integer = first To last
For three As Integer = first To last
For four As Integer = first To last
For five As Integer = first To last
words.Add(Chr(one) & Chr(two) & Chr(three) & Chr(four) & Chr(five))
Next
Next
Next
Next
Next
MsgBox(words.Count)
精彩评论