c# lambda expression complexity

Question

A simple question regarding lambda expression

I wanted to get an average of all trades in following code. The formula I am using is ((price 1*qty 1+(price 2*qty 2)....+(price n*qty n)/(qty 1+qty 2+...+qty n)

In following code, I am using sum function to calculate total of (price*qty) and the complexity will be O(n) and once more time to add up all qty the complexity will be O(n). So, is there any way I can find a summation of both using complexity O(n) means a single lambda expression which can calculate both results.

Using for loop, I can calculate both results in O(n) complexity.

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;
}

Edit: I know that the coefficient does not count. Let me rephrase the question by saying that with lambda we are going to go through each element in the list twice while with for loop we are going to go through each element only once. Is there any solution with lambda so it does not have to go through list elements twice?

If you have two procedures that are O(n), running one after the other is still O(n). — recursive
– recursive, Commented May 15, 2012 at 18:41
I know that but I just wanted to draw attention about double looping through list element when we use lambda — mchicago
– mchicago, Commented May 15, 2012 at 18:49
You might also be interested in reading this article Parallel Aggregation. Just because you're adding a whole bunch of numbers up, doesn't mean you have to do it sequentially. — Roman
– Roman, Commented May 15, 2012 at 19:51

BrokenGlass · Accepted Answer · 2012-05-15 18:55:55Z

3

As mentioned the Big-O is unchanged, whether you iterate once or twice. If you wanted to use Linq to iterate just once you could use a custom aggregator (since you are reducing to the same properties we can just use an instance of Trade for aggregation):

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;

At this point personally I would just use a foreach loop or the simple lambdas you already have - unless performance is crucial here (measure it!)

edited May 15, 2012 at 18:55

answered May 15, 2012 at 18:47

BrokenGlass

161k28 gold badges297 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Douglas · Accepted Answer · 2012-05-15 18:52:18Z

3

Big-O complexity does not take consideration of constant coefficients. O(n) + O(n) still gives O(n).

If you’re determined you want to it in lambda, here’s an example using the Aggregate operator. It looks contrived, and I wouldn’t recommend it over a traditional for loop.

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;

edited May 15, 2012 at 18:52

answered May 15, 2012 at 18:41

Douglas

55.1k14 gold badges145 silver badges193 bronze badges

Comments

Roman · Accepted Answer · 2012-08-08 18:07:31Z

3

To expand on BrokenGlass's answer, you could also use an anonymous type as your aggregator like so:

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

There are two small upsides to this approach:

If you're doing this kind of calculation on a large number of trades (or on large trades), it's possible that you would overflow the int that keep track of total value of trades and total shares. This approach lets you specify long as your data type (so it would take longer to overflow).
The object you get back from this aggregation will have more meaningful properties than you would if you simply returned a Trade object.

The big downside is that it's kinda weird to look at.

edited Aug 8, 2012 at 18:07

answered May 15, 2012 at 19:01

Roman

20.3k6 gold badges73 silver badges85 bronze badges

2 Comments

BrokenGlass Over a year ago

I would modify and return the existing accumulator though instead of creating a new one for each trade - all of these would have to be garbaged collected(!) - since that is not possible with anonymous types you are out of luck there, the only alternative being creating an entirely new type to hold your accumulated values

Douglas Over a year ago

@BrokenGlass: From the perspective of practical efficiency, yes, you’re right. However, creating a new value each time is closer to the functional roots from which LINQ was derived. Altering the object that was passed in to the accumulator function is a bit of a hack. The cleanest approach would probably be to declare a struct.

Collectives™ on Stack Overflow

c# lambda expression complexity

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related