nest产生以懒惰评估返回IEnumerable <IEnumerable >
我写了一个类似于String.Split
的LINQ扩展方法String.Split
。
> new List(){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> SplitBetween(this IEnumerable source, Func separatorSelector, bool includeSeparator = false) { var l = new List(); foreach (var x in source) { if (separatorSelector(x)) { if (includeSeparator) { l.Add(x); } yield return l; l = new List(); } else { l.Add(x); } } yield return l; }
在LINQ的精神下,我认为这种方法应该做懒惰的评估。 但是, 我的实现对外部IEnumerable进行了懒惰的评估,但没有超过内部的IEnumerable 。 我怎样才能解决这个问题?
演示外部行为是如何懒惰的。 假设ThrowingEnumerable
是一个IEnumerable
,当有人试图迭代它时会爆炸(参见Skeet的Edulinq)。
(new List(){1,2,3,10,1}) .Concat(Extensions.ThrowingEnumerable()) .SplitBetween(x=>x>=10) .First().ToList(); [1,2,3]
但内心的行为并不是懒惰的
(new List(){1,2,3,10,1}) .Concat(Extensions.ThrowingEnumerable()) .SplitBetween(x=>x>=10) .ElementAt(2).First(); BOOM
我们期待在这里1。
编辑:你的方法没有任何问题,只是当你枚举它时,投掷可枚举的东西真的会“繁荣”。 这就是它的意义所在。 它没有定义适当的GetEnumerator
。 所以你的代码没有真正的问题。 在第一种情况下,通过执行First
,您只是枚举直到获得第一个结果集(仅{ 1, 2, 3 }
)并且不枚举抛出可枚举(这意味着Concat
未被执行)。 但是在第二个例子中,你在分割后要求2
处的元素,这意味着它将枚举可枚举的引用并且将“繁荣”。 这里的关键是理解ElementAt
枚举集合直到索引要求并且本身不是懒惰(它不能)。
我不确定是否完全懒惰是去这里的方式。 问题在于,懒惰地分裂成外部和内部序列的整个过程在一个枚举器上运行,这可以根据枚举器状态产生不同的结果。 例如,您只枚举外部序列,内部序列不再是您所期望的。 或者,如果只列举外部序列的一半和一个内部序列,那么其他内部序列的状态是什么? 你的方法是最好的。
下面的方法是懒惰的(自那以后仍然会有所保证)因为它不使用中间的具体实现, 但可能比原始方法慢,因为它不止一次遍历列表 :
public static IEnumerable> SplitBy(this IEnumerable source, Func 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(at)); 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
,并且完全是lazy / iterator-ish:
public static IEnumerable> SplitBy(this IEnumerable source, Func 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 (); } } static IEnumerable YieldTill (this IEnumerator x, Func 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; } }
简短,甜美,简单。 我添加了一个额外的标志来表示你是否想要返回空集(默认情况下它会忽略)。 没有那个标志,代码就更简洁了。
感谢您提出这个问题,这将在我的扩展方法库中存在! 🙂
public static IEnumerable> SplitBetween(this IEnumerable source, Func separatorSelector, bool includeSeparators = false) { var state = new SharedState (source, separatorSelector, includeSeparators); state.LastList = state.NewList = new InnerList (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 { public SharedState(IEnumerable source, Func separatorSelector, bool includeSeparators) { this.source = source; this.separatorSelector = separatorSelector; this.includeSeparators = includeSeparators; this.iterator = source.GetEnumerator(); this.data = source as IList ; if (data == null) { cache = new List (); data = cache; } } public readonly IEnumerable source; readonly IEnumerator iterator; public readonly IList data; readonly List cache; public readonly Func separatorSelector; public readonly bool includeSeparators; public int WaveIndex = -1; public bool IsEnd = false; public InnerList NewList; public InnerList 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 (this, WaveIndex + 1); } } } } class InnerList { public InnerList(SharedState state, int startIndex) { this.state = state; this.StartIndex = startIndex; } readonly SharedState state; public readonly int StartIndex; public int? LastIndex; public IEnumerable 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]; } } }
这是一个解决方案,我想你做的是你要求的。
问题是你只有一个带yield的方法,你在枚举外部IEnumerable
时手动创建内部集合。 第二个问题是你的“测试”方式甚至在下面的矿代码中都失败了。 但是,正如David B在他的评论中指出的那样,你必须通过所有元素来定义外部IEnumerable
的元素数量。 但是你可以推迟内部IEnumerable
的创建和数量。
public static IEnumerable> SplitBetween(this IEnumerable source,Func separatorSelector, bool includeSeparators=false) { IList 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 SplitBetweenInner (IList source, int startIndex, int endIndex) { //throw new Exception("BOOM"); for(int i = startIndex; i <= endIndex; i++) yield return source[i]; }
请注意,它的行为与您的代码略有不同(当最后一个元素满足分隔条件时,它不会创建另一个空List - 这取决于定义什么是正确的,但我发现更好,因为行为是相同的,如果元素出现在源列表的开头)
如果您测试代码,您将看到内部IEnumerable
执行被延迟。
如果取消注释throwexception行:
(new List(){3,4,2,21,3,2,17,16,1}).SplitBetween(x=>x>=10, true).Count();
返回4
(new List(){3,4,2,21,3,2,17,16,1}).SplitBetween(x=>x>=10, true).First().Count();
抛出BOOM
这个不会使用List<>
,也不会使用BOOM。
public static IEnumerable> SplitBetween(this IEnumerable source, Func separatorSelector, bool includeSeparators=false) { if (source == null) throw new ArgumentNullException("source"); return SplitBetweenImpl(source, separatorSelector, includeSeparators); } private static IEnumerable SplitBetweenInner (IEnumerator e, Func separatorSelector) { var first = true; while(first || e.MoveNext()) { if (separatorSelector((T)e.Current)) yield break; first = false; yield return e.Current; } } private static IEnumerable> SplitBetweenImpl (this IEnumerable source, Func 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(){1, 2, 3, 10, 1}; foreach(var col in list.Concat(Ext.ThrowingEnumerable ()) .SplitBetween (x=>x>=10).Take(1)) { Console.WriteLine("------"); foreach(var i in col) Console.WriteLine(i); } }
输出:
------ 1 2 3
TEST2
var list = new List(){1, 2, 3, 10, 1} foreach(var col in list.Concat(Ext.ThrowingEnumerable ()) .SplitBetween (x=>x>=10).Take(2))
输出:
------ 1 2 3 ------ 1 *Exception*
这里引发exception是因为ThrowingEnumerable
-enumeration的第一个元素将与1
进入同一组。
TEST3:
var list = new List(){1, 2, 3, 10, 1, 17}; foreach(var col in list.Concat(Ext.ThrowingEnumerable ()) .SplitBetween (x=>x>=10, true).Take(4))
输出:
------ 1 2 3 ------ 10 ------ 1 ------ 17
这里没问题,因为Exception元素将进入它自己的组,因此不会因Take(4)
而迭代: