Выход гнезда для возврата IEnumerable <IEnumerable <T>> с ленивой оценкой
Я написал метод расширения LINQ SplitBetween, аналогичный 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. Как я могу это исправить?
Демонстрация того, как внешнее поведение лениво. Предположим, что ThrowingEnumerable<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.
Ответы
Ответ 1
Изменить: В вашем подходе нет ничего плохого, за исключением того, что перечислимый перечислимый будет действительно "бум", когда вы его перечислите. То, для чего это предназначено. У него нет правильного GetEnumerator, определенного на нем. Таким образом, ваш код не представляет реальной проблемы. В первом случае, выполнив First, вы только перечисляете до получения первого набора результатов (только { 1, 2, 3 }) и не перечисляете перечислимый перечислимый (что означает, что Concat не выполняется). Но во втором примере вы запрашиваете элемент в 2 после раскола, что означает, что он также перечислит переброс и будет "бум". Ключевым моментом здесь является понимание того, что ElementAt перечисляет коллекцию до тех пор, пока индекс не будет запрошен и не будет по своей сути ленивым (это не может быть).
Я не уверен, что полностью лениво - это путь сюда. Проблема в том, что весь процесс расщепления лениво во внешнюю и внутреннюю последовательности работает на одном перечислителе, который может давать разные результаты в зависимости от состояния перечислителя. Например, вы перечисляете только внешнюю последовательность, внутренние последовательности больше не будут такими, какие вы ожидаете. Или, если вы перечисляете только половину внешней последовательности и одну внутреннюю последовательность, каково будет состояние других внутренних последовательностей? Ваш подход лучший.
Нижеприведенный подход является ленивым (по-прежнему будет стремиться с тех пор, как это оправдано) тем, что он не использует промежуточных конкретных реализаций , но может быть медленнее, чем ваш исходный подход, потому что он перебирает список более одного раза:
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;
}
}
Короткий, сладкий и простой. Я добавил дополнительный флаг, чтобы обозначить, хотите ли вы возвращать пустые множества (по умолчанию он игнорирует). Без этого флага код еще более краткий.
Спасибо за этот вопрос, это будет в моей библиотеке методов расширения!:)
Ответ 2
Вот решение, которое, я полагаю, делает то, о чем вы просите.
Проблема заключалась в том, что у вас был только один метод с доходностью, и вы вручную создавали внутреннюю коллекцию , тогда как был указан внешний IEnumerable. Вторая проблема заключалась в том, что ваш способ "тестирования" не срабатывает даже по моему коду ниже. Однако, как указал Дэвид Б в своем комментарии, вы должны проходить через все элементы, чтобы определить количество элементов внешнего IEnumerable. Но вы можете отложить создание и совокупность внутренних IEnumerable s.
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();
throws BOOM
Ответ 3
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];
}
}
}
Ответ 4
Этот не будет использовать 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
Test2
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.
Test3:
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):
