Методы контроля переполнения стека? - PullRequest
Новая
       4

Методы контроля переполнения стека?

2 голосов
/ 20 августа 2011

По сути, моя программа попытается сгенерировать список всех возможных строчных 5-буквенных слов. Включая все комбинации, которые явно не являются реальными словами, такими как jshcc или mmdzq .

Я делаю это, собирая огромное количество вызовов функции, которая выполняет слово.

Но это слишком много, и я получаю ошибку переполнения стека.

Как кто-то может это контролировать?

Ответы [ 2 ]

5 голосов
/ 20 августа 2011

В основном, конвертировать из рекурсии в итерацию.Как правило, это включает создание Stack<T> в качестве «логического» стека или чего-то подобного.

Однако я бы ожидал, что метод, генерирующий список всех возможных 5-буквенных слов, будет иметь стек только около5 глубоких - по одному на каждую букву.Каждый уровень стека будет отвечать за один уровень буквы - так что «верх» стека будет перебирать каждую возможную последнюю букву;следующий кадр стека будет проходить через каждую возможную четвертую букву, вызывая метод рекурсивно для перебора всех возможных последних букв и т. д. Примерно так (код на C #, но, надеюсь, вы сможете понять его и применить к 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);
        }
    }
}

Теперь, если у вас нет какой-либо фильтрации, это сгенерирует 11 881 376 слов - что при 24 байтах каждое (на x86) составляет около 285 МБ - плюс все пространство для списка и т. Д. Это не должноубить достаточно большую машину, но - это достаточно много памяти.Вы уверены, что вам все это нужно?

0 голосов
/ 21 августа 2011

В качестве простого решения я бы использовал итерационный метод с несколькими циклами для генерации этих слов: 

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