示例:假设谓词是i == 0
。
那么
[1]>[(1)]
[0]>[]
[1,0]>[(1)]
[0,1]>[(1)]
[0,0]>[]
[1,1,0]>[(1,1)]
[1,0,1]>[(1),(1)]
[1,1,0,0,1,0,1,1]>[(1,1),(1),(1,1,1)]
基本上,返回谓词为false的连续子段。
我想这会有用的
internal static IEnumerable<IEnumerable<T>> PartitionBy<T>(this IEnumerable<T> source, Func<T, bool> condition)
{
IEnumerator<T> mover = source.GetEnumerator();
for (; mover.MoveNext() ; )
{
var chunk = mover.MoveUntil(condition);
if (chunk.Any())
{
yield return chunk;
}
}
}
private static IEnumerable<T> MoveUntil<T>(this IEnumerator<T> mover, Func<T, bool> condition)
{
bool hitCondition = false;
do
{
if (condition(mover.Current))
{
hitCondition = true;
}
else
{
yield return mover.Current;
}
}
while (!hitCondition && mover.MoveNext());
}
但我看到了,例如用[1,1,0]它将返回[(1),(1)]我不完全明白为什么。如果我改变,我可以让它工作
var chunk = mover.MoveUntil(condition);
如果可能的话,我不想在内存中保存任何子段。
最佳答案
可以使用linq调用流化结果。以下实施:
不会创建临时的List
s来减少内存消耗,我认为对于内存来说应该是O(1)
,因为一次只处理一个子段。
不会有双枚举,谓词将在每条记录中调用一次。
对于运行时来说应该是O(n)
,因为像this answer suggests一样,GroupBy
操作应该是O(n)
,而其他LINQ调用是单通操作,所以也应该是O(n)
。
public static IEnumerable<IEnumerable<T>> PartitionBy<T>(this IEnumerable<T> a, Func<T, bool> predicate)
{
int groupNumber = 0;
Func<bool, int?> getGroupNumber = skip =>
{
if (skip)
{
// prepare next group, we don't care if we increment more than once
// we only want to split groups
groupNumber++;
// null, to be able to filter out group separators
return null;
}
return groupNumber;
};
return a
.Select(x => new { Value = x, GroupNumber = getGroupNumber(predicate(x))} )
.Where(x => x.GroupNumber != null)
.GroupBy(x => x.GroupNumber)
.Select(g => g.Select(x => x.Value));
}