C# lambda 表达式复杂性

本文关键字：复杂性 表达式 lambda | 更新日期: 2023-09-27 18:34:11

关于lambda表达式的简单问题

我想在以下代码中获取所有交易的平均值。我使用的公式是（（价格 1*qty 1+（price 2*qty 2）....+（price n*qty n）/（qty 1+qty 2+...+qty n）

在下面的代码中，我使用 sum 函数来计算 （price*qty） 的总和，复杂度将是 O（n），再次将所有数量相加，复杂度将是 O（n）。那么，有什么方法可以使用复杂性 O（n） 表示可以计算两个结果的单个 lambda 表达式找到两者的总和。

使用 for 循环，我可以计算 O（n） 复杂度的两个结果。

class Program
{
    static void Main(string[] args)
    {
        List<Trade> trades = new List<Trade>()
        {
            new Trade() {price=2,qty=2},
            new Trade() {price=3,qty=3}
        };
         ///using lambda
        int price = trades.Sum(x => x.price * x.qty);
        int qty = trades.Sum(x => x.qty);
        ///using for loop
        int totalPriceQty=0, totalQty=0;
        for (int i = 0; i < trades.Count; ++i)
        {
            totalPriceQty += trades[i].price * trades[i].qty;
            totalQty += trades[i].qty;
        }
        Console.WriteLine("Average {0}", qty != 0 ? price / qty : 0);
        Console.Read();
    }
}
class Trade
{
    public int price;
    public int qty;
}

编辑：我知道系数不算数。让我改写这个问题，说使用 lambda，我们将遍历列表中的每个元素两次，而使用 for 循环，我们将只遍历每个元素一次。是否有任何使用 lambda 的解决方案，因此它不必两次遍历列表元素？

C# lambda 表达式复杂性

如前所述，无论您迭代一次还是两次，Big-O 都是不变的。如果只想使用 Linq 迭代一次，则可以使用自定义聚合器（由于要简化为相同的属性，因此我们可以只使用 Trade 实例进行聚合）：

var ag = trades.Aggregate(new Trade(), 
                          (agg, trade) => 
                          { 
                            agg.price += trade.price * trade.qty; 
                            agg.qty += trade.qty; 
                            return agg; 
                          });
int price = ag.price;
int qty = ag.qty;

在这一点上，我个人只会使用 foreach 循环或您已经拥有的简单 lambda - 除非性能在这里至关重要（测量它！

Big-O 复杂度不考虑常数系数。O（n） + O（n） 仍然给出 O（n）。

如果您确定要在 lambda 中使用它，下面是一个使用 Aggregate 运算符的示例。它看起来很做作，我不推荐它而不是传统的 for 循环。

var result = trades.Aggregate(
    Tuple.Create(0, 0),
    (acc, trade) => 
        Tuple.Create(acc.Item1 + trade.price * trade.qty, acc.Item2 + trade.qty));
int totalPrice = result.Item1;
int totalQuantity = result.Item2;

为了扩展 Broken Glass 的答案，您还可以使用匿名类型作为聚合器，如下所示：

var result = trades.Aggregate( 
                 new { TotalValue = 0L, TotalQuantity = 0L }, 
                 (acc, trade) => new 
                 { 
                     TotalValue = acc.TotalValue + trade.price, 
                     TotalQuantity = acc.TotalQuantity + trade.qty
                 }
             );

这种方法有两个小的优点：

  1. 如果您正在对大量交易（或大宗交易）进行这种计算，您可能会溢出跟踪交易总价值和总份额的int。 此方法允许您将long指定为数据类型（因此溢出需要更长的时间）。

  2. 与仅返回Trade对象相比，从此聚合返回的对象将具有更有意义的属性。

最大的缺点是看起来有点奇怪。

相关文章：