开发者

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)
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜