39

私はおそらくこれを自分で書くことができますが、それを達成しようとしている特定の方法は私をうんざりさせています。私は、.NET 3.5 で導入された他のものと同様の汎用拡張メソッドを作成しようとしています。これは、入れ子になった IEnumerables の IEnumerable (など) を取り、それを 1 つの IEnumerable にフラット化します。誰にもアイデアはありますか?

具体的には、平坦化アルゴリズムに取り組むことができるように、拡張メソッド自体の構文に問題があります。

4

13 に答える 13

47

ここに役立つ拡張機能があります。オブジェクトの階層内のすべてのノードを走査し、条件に一致するノードを選択します。階層内の各オブジェクトには、子オブジェクトを保持するコレクション プロパティがあると想定しています。

拡張子は次のとおりです。

/// Traverses an object hierarchy and return a flattened list of elements
/// based on a predicate.
/// 
/// TSource: The type of object in your collection.</typeparam>
/// source: The collection of your topmost TSource objects.</param>
/// selectorFunction: A predicate for choosing the objects you want.
/// getChildrenFunction: A function that fetches the child collection from an object.
/// returns: A flattened list of objects which meet the criteria in selectorFunction.
public static IEnumerable<TSource> Map<TSource>(
  this IEnumerable<TSource> source,
  Func<TSource, bool> selectorFunction,
  Func<TSource, IEnumerable<TSource>> getChildrenFunction)
{
  // Add what we have to the stack
  var flattenedList = source.Where(selectorFunction);

  // Go through the input enumerable looking for children,
  // and add those if we have them
  foreach (TSource element in source)
  {
    flattenedList = flattenedList.Concat(
      getChildrenFunction(element).Map(selectorFunction,
                                       getChildrenFunction)
    );
  }
  return flattenedList;
}

例 (単体テスト):

まず、オブジェクトとネストされたオブジェクト階層が必要です。

単純なノード クラス

class Node
{
  public int NodeId { get; set; }
  public int LevelId { get; set; }
  public IEnumerable<Node> Children { get; set; }

  public override string ToString()
  {
    return String.Format("Node {0}, Level {1}", this.NodeId, this.LevelId);
  }
}

ノードの 3 レベルの深い階層を取得するメソッド

private IEnumerable<Node> GetNodes()
{
  // Create a 3-level deep hierarchy of nodes
  Node[] nodes = new Node[]
    {
      new Node 
      { 
        NodeId = 1, 
        LevelId = 1, 
        Children = new Node[]
        {
          new Node { NodeId = 2, LevelId = 2, Children = new Node[] {} },
          new Node
          {
            NodeId = 3,
            LevelId = 2,
            Children = new Node[]
            {
              new Node { NodeId = 4, LevelId = 3, Children = new Node[] {} },
              new Node { NodeId = 5, LevelId = 3, Children = new Node[] {} }
            }
          }
        }
      },
      new Node { NodeId = 6, LevelId = 1, Children = new Node[] {} }
    };
  return nodes;
}

最初のテスト: 階層をフラット化、フィルタリングなし

[Test]
public void Flatten_Nested_Heirachy()
{
  IEnumerable<Node> nodes = GetNodes();
  var flattenedNodes = nodes.Map(
    p => true, 
    (Node n) => { return n.Children; }
  );
  foreach (Node flatNode in flattenedNodes)
  {
    Console.WriteLine(flatNode.ToString());
  }

  // Make sure we only end up with 6 nodes
  Assert.AreEqual(6, flattenedNodes.Count());
}

これは次のように表示されます。

Node 1, Level 1
Node 6, Level 1
Node 2, Level 2
Node 3, Level 2
Node 4, Level 3
Node 5, Level 3

2 番目のテスト: NodeId が偶数のノードのリストを取得する

[Test]
public void Only_Return_Nodes_With_Even_Numbered_Node_IDs()
{
  IEnumerable<Node> nodes = GetNodes();
  var flattenedNodes = nodes.Map(
    p => (p.NodeId % 2) == 0, 
    (Node n) => { return n.Children; }
  );
  foreach (Node flatNode in flattenedNodes)
  {
    Console.WriteLine(flatNode.ToString());
  }
  // Make sure we only end up with 3 nodes
  Assert.AreEqual(3, flattenedNodes.Count());
}

これは次のように表示されます。

Node 6, Level 1
Node 2, Level 2
Node 4, Level 3
于 2008-10-23T11:48:45.207 に答える
20

うーん...ここで何をしたいのか正確にはわかりませんが、「1レベル」のオプションは次のとおりです。

public static IEnumerable<TElement> Flatten<TElement,TSequence> (this IEnumerable<TSequence> sequences)
    where TSequence : IEnumerable<TElement> 
{
    foreach (TSequence sequence in sequences)
    {
        foreach(TElement element in sequence)
        {
            yield return element;
        }
    }
}

それがご希望でない場合は、ご希望の署名をいただけますか? ジェネリック フォームが必要なく、LINQ to XML コンストラクターと同じようなことをしたいだけの場合、それはかなり単純ですが、反復子ブロックの再帰的な使用は比較的非効率的です。何かのようなもの:

static IEnumerable Flatten(params object[] objects)
{
    // Can't easily get varargs behaviour with IEnumerable
    return Flatten((IEnumerable) objects);
}

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in candidate)
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

ただし、文字列を一連の文字として扱うことに注意してください。ユースケースによっては、特殊なケースの文字列をフラット化するのではなく、個別の要素にする必要がある場合があります。

それは役に立ちますか?

于 2008-09-26T19:47:25.600 に答える
12

エラー処理と単一ロジックのアプローチを含む完全な例を共有したいと思います。

再帰的な平坦化は次のように簡単です。

LINQ バージョン

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        return !source.Any() ? source :
            source.Concat(
                source
                .SelectMany(i => selector(i).EmptyIfNull())
                .SelectManyRecursive(selector)
            );
    }

    public static IEnumerable<T> EmptyIfNull<T>(this IEnumerable<T> source)
    {
        return source ?? Enumerable.Empty<T>();
    }
}

非 LINQ バージョン

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        foreach (T item in source)
        {
            yield return item;

            var children = selector(item);
            if (children == null)
                continue;

            foreach (T descendant in children.SelectManyRecursive(selector))
            {
                yield return descendant;
            }
        }
    }
}

設計上の決定

私はすることを決めました:

  • null のフラット化を禁止しますIEnumerable。これは、例外のスローを削除することで変更できます。
    • 最初のバージョンのsource = source.EmptyIfNull();前に追加return
    • 第2版​​のif (source != null)前に追加foreach
  • セレクターによって null コレクションを返すことを許可します。このようにして、子リストが空でないことを保証するために呼び出し元から責任を取り除きます。これは次の方法で変更できます。
    • 最初のバージョンでの削除- null がセレクターによって返された場合に失敗することに.EmptyIfNull()注意してくださいSelectMany
    • 2 番目のバージョンでの削除- nullパラメータで失敗することにif (children == null) continue;注意してくださいforeachIEnumerable
  • 子フィルター セレクターパラメーター を渡すのではなく.Where、呼び出し元側または子セレクター内で句を使用して子をフィルター処理できるようにします。
    • 両方のバージョンで遅延呼び出しであるため、効率には影響しません
    • 別のロジックをメソッドと混合することになり、ロジックを分離したままにすることを好みます

サンプル使用

画面上のすべてのコントロールを取得するために、LightSwitch でこの拡張メソッドを使用しています。

public static class ScreenObjectExtensions
{
    public static IEnumerable<IContentItemProxy> FindControls(this IScreenObject screen)
    {
        var model = screen.Details.GetModel();

        return model.GetChildItems()
            .SelectManyRecursive(c => c.GetChildItems())
            .OfType<IContentItemDefinition>()
            .Select(c => screen.FindControl(c.Name));
    }
}
于 2013-06-21T14:26:22.450 に答える
7

「1レベル以上」を許可するように変更されたJon Skeetの回答を次に示します。

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in Flatten(candidate))
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

免責事項: C# はわかりません。

Python でも同じです:

#!/usr/bin/env python

def flatten(iterable):
    for item in iterable:
        if hasattr(item, '__iter__'):
            for nested in flatten(item):
                yield nested
        else:
            yield item

if __name__ == '__main__':
    for item in flatten([1,[2, 3, [[4], 5]], 6, [[[7]]], [8]]):
        print(item, end=" ")

それは印刷します:

1 2 3 4 5 6 7 8 
于 2008-11-21T21:04:12.953 に答える
6

それが [SelectMany][1] の目的ではありませんか?

enum1.SelectMany(
    a => a.SelectMany(
        b => b.SelectMany(
            c => c.Select(
                d => d.Name
            )
        )
    )
);
于 2008-09-26T19:48:49.357 に答える
3

関数:

public static class MyExtentions
{
    public static IEnumerable<T> RecursiveSelector<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> selector)
    {
        if(nodes.Any() == false)
        {
            return nodes; 
        }

        var descendants = nodes
                            .SelectMany(selector)
                            .RecursiveSelector(selector);

        return nodes.Concat(descendants);
    } 
}

使用法:

var ar = new[]
{
    new Node
    {
        Name = "1",
        Chilren = new[]
        {
            new Node
            {
                Name = "11",
                Children = new[]
                {
                    new Node
                    {
                        Name = "111",
                        
                    }
                }
            }
        }
    }
};

var flattened = ar.RecursiveSelector(x => x.Children).ToList();
于 2015-05-19T12:08:29.877 に答える
1

yield は VB では使用できず、LINQ は遅延実行と簡潔な構文の両方を提供するため、使用することもできます。

<Extension()>
Public Function Flatten(Of T)(ByVal objects As Generic.IEnumerable(Of T), ByVal selector As Func(Of T, Generic.IEnumerable(Of T))) As Generic.IEnumerable(Of T)
   If(objects.Any()) Then
      Return objects.Union(objects.Select(selector).Where(e => e != null).SelectMany(e => e)).Flatten(selector))
   Else
      Return objects 
   End If
End Function
public static class Extensions{
  public static IEnumerable<T> Flatten<T>(this IEnumerable<T> objects, Func<T, IEnumerable<T>> selector) where T:Component{
    if(objects.Any()){
        return objects.Union(objects.Select(selector).Where(e => e != null).SelectMany(e => e).Flatten(selector));
    }
    return objects;
  }
}

以下を含むように編集:

于 2010-09-17T19:04:47.123 に答える
1

SelectMany拡張メソッドはすでにこれを行っています。

シーケンスの各要素を IEnumerable<(Of <(T>)>) に投影し、結果のシーケンスを 1 つのシーケンスにフラット化します。

于 2008-10-23T12:16:57.257 に答える
1

先祖を指す子、つまりループがある場合、提供されたすべてのソリューションが機能しなくなるため、ゼロから実装する必要がありました。私と同じ要件がある場合は、これを見てください(特別な状況で私のソリューションが壊れるかどうかも教えてください):

使い方:

var flattenlist = rootItem.Flatten(obj => obj.ChildItems, obj => obj.Id)

コード:

public static class Extensions
    {
        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this IEnumerable<T> source,
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T : class
        {
            if (source == null)
                throw new ArgumentNullException("source");
            if (childrenSelector == null)
                throw new ArgumentNullException("childrenSelector");
            if (keySelector == null)
                throw new ArgumentNullException("keySelector");
            var stack = new Stack<T>( source);
            var dictionary = new Dictionary<object, T>();
            while (stack.Any())
            {
                var currentItem = stack.Pop();
                var currentkey = keySelector(currentItem);
                if (dictionary.ContainsKey(currentkey) == false)
                {
                    dictionary.Add(currentkey, currentItem);
                    var children = childrenSelector(currentItem);
                    if (children != null)
                    {
                        foreach (var child in children)
                        {
                            stack.Push(child);
                        }
                    }
                }
                yield return currentItem;
            }
        }

        /// <summary>
        /// This would flatten out a recursive data structure ignoring the loops. The     end result would be an enumerable which enumerates all the
        /// items in the data structure regardless of the level of nesting.
        /// </summary>
        /// <typeparam name="T">Type of the recursive data structure</typeparam>
        /// <param name="source">Source element</param>
        /// <param name="childrenSelector">a function that returns the children of a     given data element of type T</param>
        /// <param name="keySelector">a function that returns a key value for each   element</param>
        /// <returns>a faltten list of all the items within recursive data structure of T</returns>
        public static IEnumerable<T> Flatten<T>(this T source, 
            Func<T, IEnumerable<T>> childrenSelector,
            Func<T, object> keySelector) where T: class
        {
            return Flatten(new [] {source}, childrenSelector, keySelector);
        }
    }
于 2014-07-14T22:59:05.430 に答える
0
static class EnumerableExtensions
{
    public static IEnumerable<T> Flatten<T>(this IEnumerable<IEnumerable<T>> sequence)
    {
        foreach(var child in sequence)
            foreach(var item in child)
                yield return item;
    }
}

もしかしてこんな?それとも、潜在的に無限に深い可能性があるということですか?

于 2008-09-26T19:42:53.007 に答える
-1

基本的に、再帰関数の外にあるマスター IENumerable が必要であり、次に再帰関数 (疑似コード) 内にある必要があります。

private void flattenList(IEnumerable<T> list)
{
    foreach (T item in list)
    {
        masterList.Add(item);

        if (item.Count > 0)
        {
            this.flattenList(item);
        }
    }
}

IEnumerable にネストされた IEnumerable の意味がよくわかりませんが、その中には何がありますか? ネストのレベルはいくつですか? 最終型は?明らかに私のコードは正しくありませんが、考えさせられることを願っています。

于 2008-09-26T19:47:06.680 に答える