13

SplitBetweenに類似した LINQ 拡張メソッドを作成しましたString.Split。

> new List<int>(){3,4,2,21,3,2,17,16,1}
> .SplitBetween(x=>x>=10)

[3,4,2], [3,2], [], [1]

ソース：

// partition sequence into sequence of contiguous subsequences
// behaves like String.Split
public static IEnumerable<IEnumerable<T>> SplitBetween<T>(this IEnumerable<T> source, 
                                                          Func<T, bool> separatorSelector, 
                                                          bool includeSeparator = false)
{
    var l = new List<T>();
    foreach (var x in source)
    {
        if (separatorSelector(x))
        {
            if (includeSeparator)
            {
                l.Add(x);
            }
            yield return l;
            l = new List<T>();
        }
        else
        {
            l.Add(x);
        }
    }
    yield return l;
}

LINQ の精神では、このメソッドは遅延評価を行うべきだと思います。ただし、私の実装では、外側の IEnumerable に対して遅延評価を行いますが、内側の IEnumerable に対しては行いません。どうすればこれを修正できますか?

外側の動作がいかに怠惰であるかのデモンストレーション。AssumeThrowingEnumerable<int>は、IEnumerable<int>誰かが反復しようとすると爆発する です (Skeet の Edulinq を参照してください)。

(new List<int>(){1,2,3,10,1})
.Concat(Extensions.ThrowingEnumerable<int>())
.SplitBetween(x=>x>=10)
.First().ToList();

[1,2,3]

しかし、内面の振る舞いは怠け者ではありません

(new List<int>(){1,2,3,10,1})
.Concat(Extensions.ThrowingEnumerable<int>())
.SplitBetween(x=>x>=10)
.ElementAt(2).First();

BOOM

ここでは 1 を期待します。

4

4 に答える 4

3

編集:あなたのアプローチには何も問題はありませんが、列挙可能なものを列挙すると実際に「ブーム」になります。それがその目的です。GetEnumeratorそれに適切な定義がありません。したがって、コードには実際の問題はありません。を実行する最初のケースでFirstは、最初の結果セット (ちょうど{ 1, 2, 3 } ) が取得されるまで列挙するだけであり、スローする列挙型を列挙しません (つまりConcat、実行されていません)。しかし、2 番目の例では、分割後に要素を要求しています。2つまり、投げる列挙型も列挙され、「ブーム」になります。ここで重要なのは、インデックスが要求するまでElementAt コレクションを列挙し、本質的に怠惰ではないことを理解することです (それはできません)。

完全に怠け者がここに行く方法であるかどうかはわかりません。問題は、外側と内側のシーケンスに遅延分割するプロセス全体が 1 つの列挙子で実行され、列挙子の状態に応じて異なる結果が得られることです。たとえば、外側のシーケンスのみを列挙すると、内側のシーケンスは期待どおりにはなりません。または、外側のシーケンスの半分と内側のシーケンスを 1 つだけ列挙すると、他の内側のシーケンスの状態はどうなるでしょうか? あなたのアプローチは最高です。

以下のアプローチは、中間の具体的な実装を使用しないという点で怠惰です（それが保証されているため、それでもブームになります）が、リストを複数回トラバースするため、元のアプローチよりも遅くなる可能性があります。

public static IEnumerable<IEnumerable<T>> SplitBy<T>(this IEnumerable<T> source, 
                                                     Func<T, bool> separatorPredicate, 
                                                     bool includeEmptyEntries = false,
                                                     bool includeSeparators = false)
{
    int prevIndex = 0;
    int lastIndex = 0;
    var query = source.Select((t, index) => { lastIndex = index; return new { t, index }; })
                      .Where(a => separatorPredicate(a.t));
    foreach (var item in query)
    {
        if (item.index == prevIndex && !includeEmptyEntries)
        {
            prevIndex++;
            continue;
        }

        yield return source.Skip(prevIndex)
                           .Take(item.index - prevIndex + (!includeSeparators ? 0 : 1));
        prevIndex = item.index + 1;
    }

    if (prevIndex <= lastIndex)
        yield return source.Skip(prevIndex);
}

何よりも、あなたのオリジナルのアプローチが最高です。完全に怠惰なものが必要な場合は、以下の私の答えが当てはまります。次のようなことのみを意味していることに注意してください。

foreach (var inners in outer)
    foreach (var item in inners)
    { 
    }

そしてそうではない

var outer = sequence.Split;
var inner1 = outer.First;
var inner2 = outer.ElementAt; //etc

つまり、同じ内部シーケンスでの複数の反復には適していません。この危険な構造を十分に認識している場合:

元の答え:

これは、中間の具体的なコレクションを使用せずToList、ソース上で列挙可能ではなく、完全に遅延/イテレータ風です。

public static IEnumerable<IEnumerable<T>> SplitBy<T>(this IEnumerable<T> source,
                                                     Func<T, bool> separatorPredicate,
                                                     bool includeEmptyEntries = false,
                                                     bool includeSeparator = false)
{
    using (var x = source.GetEnumerator())
        while (x.MoveNext())
            if (!separatorPredicate(x.Current))
                yield return x.YieldTill(separatorPredicate, includeSeparator);
            else if (includeEmptyEntries)
            {
                if (includeSeparator)
                    yield return Enumerable.Repeat(x.Current, 1);
                else
                    yield return Enumerable.Empty<T>();
            }
}

static IEnumerable<T> YieldTill<T>(this IEnumerator<T> x, 
                                   Func<T, bool> separatorPredicate,
                                   bool includeSeparator)
{
    yield return x.Current;

    while (x.MoveNext())
        if (!separatorPredicate(x.Current))
            yield return x.Current;
        else
        {
            if (includeSeparator)
                yield return x.Current;
            yield break;
        }
}

短く、甘く、シンプル。空のセットを返すかどうかを示す追加のフラグを追加しました (デフォルトでは無視されます)。そのフラグがなければ、コードはさらに簡潔になります。

この質問をありがとう、これは私の拡張メソッド ライブラリにあります! :)

于 2013-02-16T23:45:58.700 に答える
1 
  public static IEnumerable<IEnumerable<T>> SplitBetween<T>(this IEnumerable<T> source, Func<T, bool> separatorSelector, bool includeSeparators = false)
  {
    var state = new SharedState<T>(source, separatorSelector, includeSeparators);
    state.LastList = state.NewList  = new InnerList<T>(state, 0);
    for (; ; )
    {
      if (state.NewList != null)
      {
        var newList = state.NewList;
        state.NewList = null;
        yield return newList.Items();            
      }
      else if (state.IsEnd)
        break;
      else
        state.CheckNext();
    }
  }
  class SharedState<T>
  {
    public SharedState(IEnumerable<T> source, Func<T, bool> separatorSelector, bool includeSeparators)
    {
      this.source = source;
      this.separatorSelector = separatorSelector;
      this.includeSeparators = includeSeparators;

      this.iterator = source.GetEnumerator();

      this.data = source as IList<T>;
      if (data == null)
      {
        cache = new List<T>();
        data = cache;
      }
    }
    public readonly IEnumerable<T> source;
    readonly IEnumerator<T> iterator; 
    public readonly IList<T> data;
    readonly List<T> cache;
    public readonly Func<T, bool> separatorSelector;
    public readonly bool includeSeparators;
    public int WaveIndex = -1;
    public bool IsEnd = false;
    public InnerList<T> NewList;
    public InnerList<T> LastList;

    public void CheckNext()
    {
      WaveIndex++;
      if (!iterator.MoveNext())
      {
        if (LastList.LastIndex == null)
          LastList.LastIndex = WaveIndex;
        IsEnd = true;
      }
      else
      {
        var item = iterator.Current;
        if (cache != null)
          cache.Add(item);
        if (separatorSelector(item))
        {
          LastList.LastIndex = includeSeparators ? WaveIndex + 1 : WaveIndex;
          LastList = NewList = new InnerList<T>(this, WaveIndex + 1);
        }
      }
    }
  }

  class InnerList<T>
  {
    public InnerList(SharedState<T> state, int startIndex)
    {
      this.state = state;
      this.StartIndex = startIndex;
    }
    readonly SharedState<T> state;
    public readonly int StartIndex;
    public int? LastIndex;

    public IEnumerable<T> Items()
    {
      for (var i = StartIndex; ; ++i)
      {
        if (LastIndex != null && i >= LastIndex)
          break;
        if (i >= state.WaveIndex)
          state.CheckNext();
        if (LastIndex == null || i < LastIndex)
          yield return state.data[i];
      }
    }
  }
于 2012-07-13T01:19:51.310 に答える
1

これは を使用せList<>ず、BOOM にもなりません。

public static IEnumerable<IEnumerable<T>> SplitBetween<T>(this IEnumerable<T> source,
                                                          Func<T,bool> separatorSelector, 
                                                          bool includeSeparators=false) 
{
    if (source == null)
        throw new ArgumentNullException("source");

    return SplitBetweenImpl(source, separatorSelector, includeSeparators);
}

private static IEnumerable<T> SplitBetweenInner<T>(IEnumerator<T> e,
                                                   Func<T,bool> separatorSelector)
{
    var first = true;

    while(first || e.MoveNext())
    {
        if (separatorSelector((T)e.Current))
            yield break;    

        first = false;
        yield return e.Current;
    }
}

private static IEnumerable<IEnumerable<T>> SplitBetweenImpl<T>(this IEnumerable<T> source,
                                                               Func<T,bool> separatorSelector, 
                                                               bool includeSeparators) 
{
    using (var e = source.GetEnumerator())
        while(e.MoveNext())
        {
            if (separatorSelector((T)e.Current) && includeSeparators)
                yield return new T[] {(T)e.Current};
            else
                {
                yield return SplitBetweenInner(e, separatorSelector);
                if (separatorSelector((T)e.Current) && includeSeparators)
                    yield return new T[] {(T)e.Current};
                }
        }
}

テスト：

void Main()
{
    var list = new List<int>(){1, 2, 3, 10, 1};
    foreach(var col in list.Concat(Ext.ThrowingEnumerable<int>())
                           .SplitBetween<int>(x=>x>=10).Take(1))
    {
        Console.WriteLine("------");
        foreach(var i in col)
            Console.WriteLine(i);
    }
}

出力：

------
1
2
3

テスト2

var list = new List<int>(){1, 2, 3, 10, 1}
foreach(var col in list.Concat(Ext.ThrowingEnumerable<int>())
                       .SplitBetween<int>(x=>x>=10).Take(2))

出力：

------
1
2
3
------
1
*Exception*

ThrowingEnumerableここでは、 -enumerationの最初の要素が と同じグループに入るため、例外が発生し1ます。

テスト3:

var list = new List<int>(){1, 2, 3, 10, 1, 17};
foreach(var col in list.Concat(Ext.ThrowingEnumerable<int>())
                       .SplitBetween<int>(x=>x>=10, true).Take(4))

出力：

------
1
2
3
------
10
------
1
------
17

ここでは問題ありません。なぜなら、Exception要素はそれ自身のグループに入り、次の理由で繰り返されないからTake(4)です。

于 2012-07-13T06:09:29.290 に答える
1

ここに、あなたが求めていることを行うと思われる解決策があります。

問題は、yield を使用するメソッドが 1 つしかなく、外部コレクションが列挙されている間に内部コレクションを手動で作成していたことです。IEnumerable2番目の問題は、以下の私のコードでも「テスト」の方法が失敗することでした。ただし、David B がコメントで指摘したように、すべての要素を調べて、outer の要素数を定義する必要IEnumerableがあります。ただし、インナーIEnumerables の作成と設定を延期することはできます。

public static IEnumerable<IEnumerable<T>> SplitBetween<T>(this IEnumerable<T> source,Func<T,bool> separatorSelector, bool includeSeparators=false)
{
    IList<T> sourceList = source.ToList();
    var indexStart = 0;
    var indexOfLastElement = sourceList.Count - 1;
    for(int i = 0; i <= indexOfLastElement; i++)
        if (separatorSelector(sourceList[i]))
        {
            if(includeSeparators)
                yield return SplitBetweenInner(sourceList, indexStart, i);
            else
                yield return SplitBetweenInner(sourceList, indexStart, i - 1);

            indexStart = i + 1;
        }
        else if(i == indexOfLastElement)
            yield return SplitBetweenInner(sourceList, indexStart, i);        
}

private static IEnumerable<T> SplitBetweenInner<T>(IList<T> source, int startIndex, int endIndex)
{
    //throw new Exception("BOOM");
    for(int i = startIndex; i <= endIndex; i++)
        yield return source[i];
}

あなたのコードとは少し異なる動作をすることに注意してください（最後の要素が区切り条件を満たしている場合、別の空のリストを作成しません - ここで何が正しいかは定義次第ですが、動作が要素はソース リストの先頭に表示されます)

IEnumerableコードをテストすると、内部実行が延期されていることがわかります。

スロー例外行がコメント解除されている場合:

(new List<int>(){3,4,2,21,3,2,17,16,1}).SplitBetween(x=>x>=10, true).Count();

戻り値4

(new List<int>(){3,4,2,21,3,2,17,16,1}).SplitBetween(x=>x>=10, true).First().Count();

スローBOOM

于 2012-07-13T00:30:23.197 に答える