3

背景。 我的脚本在递归搜索大字符串中的特定文本时遇到 StackOverflowException。循环不是无限的；问题发生在 9,000-10,000 次合法搜索之间（对于特定搜索）——我需要它继续下去。我正在使用尾递归（我认为），这可能是我的问题的一部分，因为我认为 C# 做得不好。但是，我不确定如何避免在我的情况下使用尾递归。

问题）。为什么会发生 StackOverflowException？我的整体方法有意义吗？如果设计很糟糕，我宁愿从那里开始，而不仅仅是避免异常。但是如果设计是可以接受的，我能对 StackOverflowException 做些什么呢？

代码。 我编写的类在大量文本（约 6MB）中搜索联系人（来自指定列表的约 500 多个）。我使用的策略是搜索姓氏，然后在姓氏之前或之后不久的某处寻找名字。我需要在给定文本中找到每个联系人的每个实例。StringSearcher 类有一个递归方法，可以继续搜索联系人，只要找到一个就返回结果，但会跟踪搜索中断的位置。

我以下列方式使用这个类：

StringSearcher searcher = new StringSearcher(
    File.ReadAllText(FilePath),
    "lastname",
    "firstname",
    30
);

string searchResult = null;
while ((searchResult = searcher.NextInstance()) != null)
{
    // do something with each searchResult
}

总的来说，该脚本似乎有效。大多数联系人返回我期望的结果。但是，当主要搜索字符串非常常见（数千次点击）而辅助搜索字符串从不或很少出现时，似乎会出现此问题。我知道它没有卡住，因为 CurrentIndex 正在正常推进。

这是我正在谈论的递归方法。

public string NextInstance()
{
    // Advance this.CurrentIndex to the next location of the primary search string
    this.SearchForNext();

    // Look a little before and after the primary search string
    this.CurrentContext = this.GetContextAtCurrentIndex();

    // Primary search string found?
    if (this.AnotherInstanceFound)
    {
        // If there is a valid secondary search string, is that found near the
        // primary search string? If not, look for the next instance of the primary
        // search string
        if (!string.IsNullOrEmpty(this.SecondarySearchString) &&
            !this.IsSecondaryFoundInContext())
        {
            return this.NextInstance();
        }
        // 
        else
        {
            return this.CurrentContext;
        }
    }
    // No more instances of the primary search string
    else
    {
        return null;
    }
}

StackOverflowException 发生this.CurrentIndex = ...在以下方法中：

private void SearchForNext()
{
    // If we've already searched once, 
    // increment the current index before searching further.
    if (0 != this.CurrentIndex)
    {
        this.CurrentIndex++;
        this.NumberOfSearches++;
    }

    this.CurrentIndex = this.Source.IndexOf(
            this.PrimarySearchString,
            ValidIndex(this.CurrentIndex),
            StringComparison.OrdinalIgnoreCase
    );

    this.AnotherInstanceFound = !(this.CurrentIndex >= 0) ? false : true;
}

如果需要，我可以包含更多代码。让我知道这些方法或变量之一是否有问题。

*性能并不是一个真正的问题，因为这可能会在晚上作为计划任务运行。

4

2 回答 2

3

你有一个 1MB 的堆栈。当该堆栈空间用完并且您仍然需要更多堆栈空间时，StackOverflowException就会抛出一个。这可能是也可能不是无限递归的结果，运行时不知道。无限递归只是使用更多可用堆栈空间的一种有效方法（通过使用无限量）。你可以使用一个有限的数量，恰好超过可用的数量，你会得到同样的例外。

虽然还有其他方法可以使用大量堆栈空间，但递归是最有效的方法之一。每种方法都基于该方法的签名和局部变量添加更多空间。深度递归会占用大量堆栈空间，因此如果您希望深度超过几百级（甚至很多），您可能不应该使用递归。请注意，任何使用递归的代码都可以迭代编写，或者使用显式的Stack.

很难说，因为没有显示完整的实现，但根据我所看到的，您或多或少地编写了一个迭代器，但您没有使用 C# 构造（即IEnumerable）。

我的猜测是“迭代器块”将允许您使该算法更易于编写，更易于以非递归方式编写，并且从调用者方面更有效。

以下是如何将此方法构造为迭代器块的高级视图：

public static IEnumerable<string> SearchString(string text
    , string firstString, string secondString, int unknown)
{
    int lastIndexFound = text.IndexOf(firstString);

    while (lastIndexFound >= 0)
    {
        if (secondStringNearFirst(text, firstString, secondString, lastIndexFound))
        {
            yield return lastIndexFound.ToString();
        }
    }
}

private static bool secondStringNearFirst(string text
    , string firstString, string secondString, int lastIndexFound)
{
    throw new NotImplementedException();
}
于 2013-01-17T16:25:44.420 回答
3

似乎递归在这里不是正确的解决方案。通常对于递归问题，您有一些状态传递给递归步骤。在这种情况下，你真的有一个简单的while循环。下面我将您的方法主体放在一个循环中，并将递归步骤更改为continue. 看看有没有效果...

public string NextInstance()
{
    while (true)
    {
        // Advance this.CurrentIndex to the next location of the primary search string
        this.SearchForNext();

        // Look a little before and after the primary search string
        this.CurrentContext = this.GetContextAtCurrentIndex();

        // Primary search string found?
        if (this.AnotherInstanceFound)
        {
            // If there is a valid secondary search string, is that found near the
            // primary search string? If not, look for the next instance of the primary
            // search string
            if (!string.IsNullOrEmpty(this.SecondarySearchString) &&
                !this.IsSecondaryFoundInContext())
            {
                continue; // Start searching again...
            }
            // 
            else
            {
                return this.CurrentContext;
            }
        }
        // No more instances of the primary search string
        else
        {
            return null;
        }
    }
}
于 2013-01-17T16:27:02.217 回答