聚合值直到达到限制

Question

我需要类似于 AggregateWhile 方法的东西。标准 System.Linq.Enumerable class 不提供它。到目前为止，我一直能够利用标准的 LINQ 方法来解决我遇到的每一个问题。所以我想知道在这种情况下这是否仍然可行，或者我是否真的需要使用非标准方法扩展 LINQ。

假设的 AggregateWhile 方法将遍历序列并应用累加器。一旦谓词 return 为假，聚合就完成了。结果是最多不元素的聚合，包括谓词失败的元素。

举个例子。我们有一个 List { 1, 2, 3, 4, 5 } 和一个将两个输入数字加在一起的累加器，以及一个声明累加必须小于 12 的谓词。AggregateWhile 会 return 10 因为那是 1 的结果+ 2 + 3 + 4 加上最后的 5 会使总数超过限制。在代码中：

var list = new List<int> { 1, 2, 3, 4, 5 };
int total = list.AggregateWhile( (x, y) => x + y, a => a < 12 ); // returns 10

我需要一个纯函数式的解决方案，所以关闭一个临时变量不是一个选项。

Answer 1

这不行吗？

int total = list.Aggregate(0, (a, x) => (a + x) > 12 ? a : a + x);

使用 Tuple<bool, int> 作为累加器类型，在第一次溢出时中断：

int total = list.Aggregate(new Tuple<bool, int>(false, 0),
    (a, x) => a.Item1 || (a.Item2 + x) > 12
    ? new Tuple<bool, int>(true, a.Item2)
    : new Tuple<bool, int>(false, a.Item2 + x)
).Item2;

但不幸的是，它并不是那么好。

开始使用 F#。 ;)

let list = [ 1; 2; 3; 4; 5; 1 ]
let predicate = fun a -> a > 12 
let total = list |> List.fold (fun (aval, astate) x ->
    if astate || predicate (aval + x)
    then (aval, true)
    else (aval + x, false)) (0, false)

Tuple 拆包，没有 new 臃肿。当您编写代码时，类型推断会变得轻而易举。

Answer 2

你可以自己写函数，或者用你的累加器携带一个标志：

int total = list.Aggregate(new { value = 0, valid = true }, 
                          (acc, v) => acc.value + v < 12 && acc.valid ?
                                      new { value = acc.value + v, valid = true } :
                                      new { value = acc.value, valid = false },
                            acc => acc.value);

太丑了，写一个新的AggregateWhile会更好：

public static TSource AggregateWhile<TSource>(this IEnumerable<TSource> source, 
                                         Func<TSource, TSource, TSource> func,
                                         Func<TSource, bool> predicate)
{
   using (IEnumerator<TSource> e = source.GetEnumerator()) {
       TSource result = e.Current;
       TSource tmp = default(TSource);
       while (e.MoveNext() && predicate(tmp = func(result, e.Current))) 
            result = tmp;
       return result;
   }
}

（为简洁起见没有错误检查）

Answer 3

您可以编写自己的扩展方法。这不像普通的 Linq 方法那么完美，我作弊是因为我已经知道您的要求以使其更简单。实际上，您可能需要 a 的可选起始值，可能需要 T 或其他东西的不同输入和输出类型：

public static class Linq
{
  public static T AggregateWhile<T>(this IEnumerable<T> sequence, Func<T, T, T> aggregate, Func<T, bool> predicate)
  {
     T a;
     foreach(var value in sequence)
     {
        T temp = aggregate(a, value);
        if(!predicate(temp)) break;
        a = temp;
     }
     return a;
  }
}

Answer 4

前阵子我问了这个问题，当时我遇到了一个问题，后来我重新定义为不需要 AggregateWhile。但现在我遇到了一个稍微不同的问题，它无疑需要 AggregateWhile 或一些直接替代品。

@sloth 和@rkrahl 提出的解决方案很有帮助。但它们的不足之处在于聚合逻辑（在本例中为加法）重复了两次。对于这个问题的微不足道的例子来说，这似乎没什么大不了的。但是对于我的实际问题，计算复杂所以写两次是不能接受的。

这是我更喜欢的解决方案（缺乏实际的 AggregateWhile 方法）：

class Program
{
    static void Main( string[] args ) { new Program(); }

    public Program()
    {
        var list = new int[] { 1, 2, 3, 4, 5 };
        int total = list
            .Aggregate( new Accumulator( 0 ), ( a, i ) => a.Next( i ), a => a.Total );
    }
}

class Accumulator
{
    public Accumulator( int total )
    {
        this.total = total;
    }

    public Accumulator Next( int i )
    {
        if ( isDone )
            return this;
        else {
            int total = this.total + i;
            if ( total < 12 )
                return new Accumulator( total );
            else {
                isDone = true;
                return this;
            }
        }
    }
    bool isDone;

    public int Total
    {
        get { return total; }
    }
    readonly int total;
}

理想的解决方案是完全实现和测试 AggregateWhile 对应于三个 Aggregate 重载的方法。除此之外，上述模式的优点是它可以利用 .NET 框架中已经存在的（有点缺乏）功能。

Answer 5

这是一个 AggregateWhile 和一个 seed:

public static TAccumulate AggregateWhile<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> func,
    Func<TAccumulate, bool> predicate)
{
    if (source == null)
        throw new ArgumentNullException(nameof(source));

    if (func == null)
        throw new ArgumentNullException(nameof(func));

    if (predicate == null)
        throw new ArgumentNullException(nameof(predicate));

    var accumulate = seed;
    foreach (var item in source)
    {
        var tmp = func(accumulate, item);
        if (!predicate(tmp)) break;
        accumulate = tmp;
    }
    return accumulate;
}

聚合值直到达到限制

Aggregate values until a limit is reached

c#

linq

linq-to-objects