1

循環依存関係を持つ可能性のあるアイテムを再帰するより良い方法を探しています。現在、再度処理しないようにするために、既に処理された項目のリストを渡していますが、これはおそらく最善の方法ではありません。

これが私が現在行っていることです：

        /// <summary>
    /// caching dependencies in order to increase performance
    /// </summary>
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies
        = new Dictionary<string, IEnumerable<OwnedItem>>();

        /// <summary>
    /// recursively find OwnedItem this oi depends upon
    /// in order to correctly handle cyclic dependencies, already considered
    /// dependencies need to be supplied as well (can be null or empty)
    /// </summary>
    /// <param name="oi"></param>
    /// <param name="parentDeps"></param>
    /// <returns></returns>
    private static IEnumerable<OwnedItem> GetDependencies(
        OwnedItem oi,
        IEnumerable<OwnedItem> parentDeps)
    {
        if (null == oi)
        {
            return Enumerable.Empty<OwnedItem>();
        }
        if (dependencies.ContainsKey(oi.UniqueId))
        {
            return dependencies[oi.UniqueId];
        }
        var comparer = new TCObjectComparer<OwnedItem>();
        var result = new HashSet<OwnedItem>(comparer);
        result.Add(oi);
        result.UnionWith(parentDeps ?? Enumerable.Empty<OwnedItem>());
        foreach (var oi2 in oi.AllUsedOwnedItemsToBeIncluded.Except(
                result, comparer))
        {
            result.UnionWith(GetDependencies(oi2, result));
        }
        dependencies[oi.UniqueId] = result;
        return result;
    }

アイテムは「OwnedItem」タイプでありIEnumerable<OwnedItem>、プロパティに直接依存関係のリスト ( ) を保持しますAllUsedOwnedItemsToBeIncludedが、基本的に、「アイテム」が循環依存関係が発生する可能性のある「アイテム」のリストを保持する場合は常にこれを適用する必要があります。辞書を使用すると、同じ計算を複数回実行するのを回避できます。それは必須ではありません。また、必要なインスタンスは 1 つだけTCObjectComparerですが、これも必須ではありません。助言がありますか？これを処理するための古典的なアルゴリズムが存在するに違いないと思いますが、見つかりません。

4

4 に答える 4

1

アルゴリズムをクラスに抽出して、コードを整理し、臭い静的フィールドを取り除くことができます。

private static IEnumerable<T> GetDependencies(T oi)
{
    return new FlattenedCircularTree<OwnedItem>(oi, o => o.AllUsedOwnedItemsToBeIncluded)
       .AllNodes();
}

一般的なアルゴリズムは次のように実装されます。

public sealed class FlattenedCircularTree<T>
{
    private readonly T _root;
    private readonly Func<T, IEnumerable<T>> _getChildren;
    private readonly HashSet<T> _visited = new HashSet<T>();
    private readonly List<T> _nodes = new List<T>();

    public FlattenedCircularTree(T root, Func<T, IEnumerable<T>> getChildren)
    {
        _root = root;
        _getChildren = getChildren;
    }

    public IEnumerable<T> AllNodes()
    {
        FindNodes(_root);
        return _nodes;
    }

    private void FindNodes(T current)
    {
        if (!_visited.Add(current))
            return;
        _nodes.Add(current);
        IEnumerable<T> children = _getChildren(current);
        if (children != null)
            foreach (T child in children)
                FindNodes(child);
    }
}
于 2016-06-03T13:14:14.167 に答える
0

Vincent のアルゴリズムの実装は次のとおりです。

    private static readonly TCObjectComparer<OwnedItem> comparer
        = new TCObjectComparer<OwnedItem>();

    /// <summary>
    /// caching dependencies in order to increase performance
    /// </summary>
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies
        = new Dictionary<string, IEnumerable<OwnedItem>>();

    /// <summary>
    /// recursively find OwnedItems this oi depends upon
    /// see http://stackoverflow.com/questions/37614469/how-to-recurse-over-items-having-cyclic-dependencies
    /// </summary>
    /// <param name="oi"></param>
    /// <returns></returns>
    private static IEnumerable<OwnedItem> GetDependencies(OwnedItem oi)
    {
        if (null == oi)
        {
            return Enumerable.Empty<OwnedItem>();
        }
        if (dependencies.ContainsKey(oi.UniqueId))
        {
            return dependencies[oi.UniqueId];
        }
        var resultExploredNodes = new HashSet<OwnedItem>(comparer);
        var nodesToExplore = new Queue<OwnedItem>();
        nodesToExplore.Enqueue(oi);
        while (nodesToExplore.Count > 0)
        {
            var node = nodesToExplore.Dequeue();
            resultExploredNodes.Add(node);
            // add nodes not already visited to nodesToExplore
            node.AllUsedOwnedItemsToBeIncluded
                .Except(resultExploredNodes, comparer)
                .ForEach(n => nodesToExplore.Enqueue(n));
        }
        dependencies[oi.UniqueId] = resultExploredNodes;
        return resultExploredNodes;
    }

繰り返しますが、キャッシングはパフォーマンスのためだけのものであり、アルゴリズムにとって必須ではありません。

于 2016-06-03T14:43:57.777 に答える