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

但我觉得这是作弊，不会被优化为尾递归。

有任何想法吗？我应该使用完全不同的策略吗？这根本不需要是一个超级高效的算法，我只是很好奇。我正在使用.NET 4.0，顺便说一句。

谢谢！

PS如果你想知道我的终止条件，别担心。我用根目录预播字典。

4

2 回答 2

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

有了这个，您可以记住您对昂贵资源（数据库）的所有访问，只需更改其中的一行PathGenerator，如下所示：

var finder = database;

对此：

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

即使您确实获得了正确的代码布局，您也会遇到的第一个主要问题是 C# 编译器并不能很好地支持尾递归。C#中的尾递归

使用那里的信息，您可能可以使其工作。但这充其量是不雅的。

于 2012-09-28T21:44:56.083 回答