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

必要に応じて、さらにコードを含めることができます。それらのメソッドまたは変数の1つに問題があるかどうかを教えてください。

*これはスケジュールされたタスクとして夜間に実行される可能性が高いため、パフォーマンスは実際には問題ではありません。

4

2 に答える 2

3

1MBのスタックがあります。そのスタックスペースが不足し、さらにスタックスペースが必要な場合は、aStackOverflowExceptionがスローされます。これは無限再帰の結果である場合とそうでない場合があり、ランタイムにはわかりません。無限再帰は、（無限の量を使用することによって）使用可能なスタックスペースを使用するための効果的な方法の1つにすぎません。有限量を使用することができますが、それはたまたま利用可能な量を超えており、同じ例外が発生します。

多くのスタックスペースを使い果たす方法は他にもありますが、再帰は最も効果的な方法の1つです。各メソッドは、そのメソッドのシグネチャとローカルに基づいてスペースを追加しています。深い再帰があると、多くのスタックスペースが使用される可能性があるため、数百レベルを超える深さがあると予想される場合（さらにはそれでも多い場合）、おそらく再帰を使用しないでください。再帰を使用するコードは、繰り返し記述したり、明示的なを使用したりできることに注意してくださいStack。

完全な実装が示されていないため、言うのは難しいですが、私が見ることができることに基づいて、あなたは多かれ少なかれイテレータを書いていますが、C＃コンストラクトを1つ（つまり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 に答える