0

关于 lambda 表达式的一个简单问题

我想在以下代码中获得所有交易的平均值。我使用的公式是 ((price 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 的解决方案，所以它不必遍历列表元素两次？

4

3 回答 3

3

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;
于 2012-05-15T18:41:56.620 回答
3

如前所述，无论您迭代一次还是两次，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 循环或您已经拥有的简单 lambdas - 除非性能在这里至关重要（测量它！）

于 2012-05-15T18:47:52.760 回答
3

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

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。

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

于 2012-05-15T19:01:02.273 回答