0

エントリのデータベーステーブルに基づいてディレクトリのフルパスを見つける関数を書いています。各レコードには、キー、ディレクトリ名、および親ディレクトリのキーが含まれています（使い慣れている場合は、MSIのディレクトリテーブルです）。私は反復的な解決策を持っていましたが、それは少し厄介に見え始めました。エレガントな末尾再帰ソリューションを作成できると思いましたが、もうわかりません。

私のコードを紹介してから、私が直面している問題について説明します。

Dictionary<string, string> m_directoryKeyToFullPathDictionary = new Dictionary<string, string>();
...
private string ExpandDirectoryKey(Database database, string directoryKey)
{
    // check for terminating condition
    string fullPath;
    if (m_directoryKeyToFullPathDictionary.TryGetValue(directoryKey, out fullPath))
    {
        return fullPath;
    }

    // inductive step
    Record record = ExecuteQuery(database, "SELECT DefaultDir, Directory_Parent FROM Directory where Directory.Directory='{0}'", directoryKey);
    // null check
    string directoryName = record.GetString("DefaultDir");
    string parentDirectoryKey = record.GetString("Directory_Parent");

    return Path.Combine(ExpandDirectoryKey(database, parentDirectoryKey), directoryName);
}

これは、問題が発生したことに気付いたときのコードの外観です（マイナーな検証/マッサージが削除されています）。可能な限りメモ化を使用して短絡させたいのですが、再帰ExpandDirectoryKey呼び出しの出力を格納するために辞書への関数呼び出しを行う必要があります。そこにも電話があることに気づきましたが、それは。Path.Combineで回避できると思います... + Path.DirectorySeparatorChar + ...。

上記の関数の最後で次のように呼び出すことができるように、ディレクトリをメモ化して値を返すヘルパーメソッドを使用することを考えました。

return MemoizeHelper(
    m_directoryKeyToFullPathDictionary,
    Path.Combine(ExpandDirectoryKey(database, parentDirectoryKey)),
    directoryName);

しかし、それは不正行為であり、末尾再帰として最適化されないように感じます。

何か案は？まったく異なる戦略を使用する必要がありますか？これは非常に効率的なアルゴリズムである必要はまったくありません。私は本当に興味があります。私は.NET4.0を使用しています。

ありがとう！

PS私の終了条件について疑問に思っている場合でも、心配しないでください。辞書にルートディレクトリを事前にシードします。

4

2 に答える 2

2

コードのレイアウトを正しく取得したとしても、最初に遭遇する大きな問題は、C＃コンパイラが実際には末尾再帰を適切にサポートしていないことです。C＃での末尾再帰

そこにある情報を使用して、おそらくそれを機能させることができます。しかし、それはせいぜいエレガントではないでしょう。

于 2012-09-28T21:44:56.083 に答える
2

あなたはあなたが好奇心を持っていると言いました、そして私もそうです、あなたがこのアプローチについてどう思うか見てみましょう。私の主張を説明するために、あなたの問題を一般化しています。Record次のようなタイプがあると仮定します。

class Record
{
    public int Id { get; private set; }
    public int ParentId { get; private set; }
    public string Name { get; private set; }

    public Record(int id, int parentId, string name)
    {
        Id = id;
        ParentId = parentId;
        Name = name;
    }
}

そして、この関数によって表される「データベース」：

static Func<int, Record> Database()
{
    var database = new Dictionary<int, Record>()
     {
         { 1, new Record(1, 0, "a") },
         { 2, new Record(2, 1, "b") },
         { 3, new Record(3, 2, "c") },
         { 4, new Record(4, 3, "d") },
         { 5, new Record(5, 4, "e") },
     };
     return x => database[x];
 }

次のように再帰を「表す」方法を紹介しましょう。

public static class Recursor
{
    public static IEnumerable<T> Do<T>(
        T seed, 
        Func<T, T> next, 
        Func<T, bool> exit)
    {
        return Do(seed, next, exit, x => x);
    }

    public static IEnumerable<TR> Do<T, TR>(
        T seed, 
        Func<T, T> next, 
        Func<T, bool> exit, 
        Func<T, TR> resultor)
    {
        var r = seed;
        while (true)
        {
            if (exit(r))
                yield break;
            yield return resultor(r);
            r = next(r);
        }
    }
}

ご覧のとおり、これは再帰をまったく実行していませんが、再帰の「ように見える」部分の観点からアルゴリズムを表現することができます。パス生成関数は次のようになります。

static Func<int, string> PathGenerator(Func<int, Record> database)
{
    var finder = database;

    return id => string.Join("/",
        Recursor.Do(id,                       //seed
                    x => finder(x).ParentId,  //how do I find the next item?
                    x => x == 0,              //when do I stop?
                    x => finder(x).Name)      //what do I extract from next item?
                .Reverse());                  //reversing items
}

この関数は、を使用しRecursorてアルゴリズムを表し、生成されたすべての部分を収集してパスを構成します。Recursorは蓄積せず、蓄積の責任を発信者に委任するという考え方です。次のように使用します。

var f = PathGenerator(Database());
Console.WriteLine(f(3));           //output: a/b/c

また、メモ化が必要でした。これを紹介しましょう。

public static class Memoizer
{
    public static Func<T, TR> Do<T, TR>(Func<T, TR> gen)
    {
        var mem = new Dictionary<T, TR>();
        return (target) =>
        {
            if (mem.ContainsKey(target))
                return mem[target];
            mem.Add(target, gen(target));
            return mem[target];
        };
    }
}

これにより、高価なリソース（データベース）へのすべてのアクセスを、次のように1行変更するだけでメモ化できますPathGenerator。

var finder = database;

これに：

var finder = Memoizer.Do<int, Record>(x => database(x));
于 2012-09-29T17:18:20.650 に答える