Friday programming quiz

[KP Lee]

I like Lambda expressions about as much as the help text for it is descriptive. (IE not much) I'll happily fail your quiz since I didn't sign up for your class and I'm really guessing at how this all works. In your example there were 10 items in the array. Your code:

inputs.Where(x => Math.Abs(x - inputs.Average()) == inputs.Select(y => Math.Abs(y - inputs.Average())).Min()).First();

inputs.Average() loops 10 times, summing all parties and dividing by 10 to provide the average value. y in Math.Abs(y - inputs.Average()) is obviously an interation of inputs values. How it became the iteration value is because it is in the "Select" method, I think. However this expression has to be calculated 100 times (10 y's times Average's 10 loops) to find the Min() value. Math.Abs(x - inputs.Average()) will start on that 100 loop too, so that's 10,000 calculations. (I think that C# isn't smart enough to realize all these function calls on the right side produce a constant so every time the left equation is run, the right equation is re-run.) Aah, but you've put in First() so it will short-circuit the loop when 14 is found. Since 14 is the last value, that's 10,000 loops. :-D 7 Functions executed: Where (1) Math.Abs(2) Average(2) Min(1) First(1) I am never impressed with cute code. Lambda is almost always cute. 10 lines of straightforward code are more valuable than 1 line of cute. The following code

  int avg = inputs.Average();
  int dif1, dif2, val1;
  val1 = inputs\[0\];
  if (val1 > avg) dif1 = val1 - avg;
  else dif1 = avg - val1;
  foreach(int i in inputs) {
      if (i > avg) dif2 = i - avg;
      else dif2 = avg - i;
      if (dif2 < dif1) {
          dif1 = dif2;
          val1 = i;
      }
  }

is more verbose, but even with archane variable names, to me, this seems easier to grasp without scratching your head and going: Now, what was that again???? When it is done, you have the average, the closest value to average, and the distance from average in three variables. However, show me the lambda code to do the same thing in 2*N loops my code uses instead of N^4 loops. OK, Math.Abs is easier to read, than if/else, but I think the code cost is about the same. Go ahead and use Abs, there's no advantage in using my 2 lines of code other than showing the function is fairly easy to replicate. Average is too valuable encapsulation to re-invent that wheel. With a 400 item array, 400^4 = 2

[sknake]

I gave it a shot and came up with an answer using a few less calls:

int avg = inputs.OrderBy(i => Math.Abs(i - inputs.Average())).First();

[PhilLenoir]

Hear,hear! I may be an old f*rt but readability of code is paramount for maintenance. If terse and difficult to understand code is also less efficient then it fails twice. Having said that, the competition rules were set bt the creator and I'm just an aging SQL hack! :P

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[PhilLenoir]

Johnny: Good sentiment, but I've only seen one alternate solution and lots of comment ... so maybe it works as a lounge post!

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[Johnny J]

I was just pulling your leg - I have no objections to your post... ;)

Why can't I be applicable like John? - Me, April 2011
-----
Beidh ceol, caint agus craic againn - Seán Bán Breathnach
-----
Da mihi sis crustum Etruscum cum omnibus in eo!
-----
Just because a thing is new don’t mean that it’s better - Will Rogers, September 4, 1932

[PhilLenoir]

Not MY post Johnny and I was just :P

Life is like a s**t sandwich; the more bread you have, the less s**t you eat.

[alanevans]

int closest = inputs.Last(); Or have I missed the point? ;P

[alanevans]

Great answer. Can use let rather than that new []{} however: int closest = (from i in inputs
let avg = inputs.Average()
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();
That is actually wrong, but this works and average is called just once:

        int closest = (from c in "A" //just to get it to loop once
                       let avg = inputs.Average()
                       select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
          ).Single();

Does anyone know of a nicer way to cause just one loop in linq than my 'from c in "A"' trick?

[Adar Wesley]

This little change you suggest puts the perfomance back to O(N^2) and not linear. inputs.Average() gets called for each element in the inputs array. Daniel's solution is the correct one. --- Adar Wesley

[Member_5893260]

Here's a good couple of questions to give programmers you're thinking of hiring -- if they can answer these, it's a good bet you've found yourself someone who can think a bit...: 1. In C, what does this do (and no, it doesn't matter what types the variables are as long as they're the same type)?   a^=b^=a^=b; 2. In SQL, given the following tables (relationships being obvious), write a query which returns the names of the people who play *every* sport:   People   PersonID int   PersonName varchar(50)   Sports   SportID int   SportName varchar(50)   PeopleSports   PersonID int   SportID int

[Robbie Couret]

Could be simplified to:

int closest = inputs.First(x => Math.Abs(x - inputs.Average()) == inputs.Min(y => Math.Abs(y - inputs.Average())));

but I don't like to perform the same calculation twice, so I'd be more comfortable with:

double avg = inputs.Average();
int closest = inputs.First(x => Math.Abs(x - avg) == inputs.Min(y => Math.Abs(y - avg)));

[John Petrak2]

int closest = inputs.OrderBy(x => Math.Abs(inputs.Average() - x)).First();

[Harley L Pebley]

Here are two alternate implementations. Two might be cheating a bit, but it satisfies the "only one semi-colon" rule. :-) As others have pointed out, the answer you gave is pretty slow. To those who say LINQ can't be fast, algorithm choice makes a huge difference. I ran tests for the three implementations over the original input set, the values 1-99 and -499 to 499. To help average out timing inconsistencies, the tests were run 10,000 times. Values are in ms.

Quiz inputs

100 items

1000 items

Quiz solution

284

84,573

Unknown. I stopped it after about 6 hours.

Alternate 1

80

1,945

167,099

Alternate 2

75

479

7,246

Alternate 1

int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = inputs
.Select(i => new {val = i, dist = Math.Abs(i - inputs.Average())})
.OrderBy(a => a.dist)
.First().val;

Alternate 2

int[] inputs = {1, 2, 3, 5, -1, 7, 145, -33, 22, 14};
int closest = (from x in new []{1}
let avg = inputs.Average()
from i in inputs
select new { val = i, dist = Math.Abs(i-avg)})
.OrderBy(a => a.dist)
.First().val

[KP Lee]

I'm not familiar with linq nor lambda, but I really like this solution over the original suggested one. Am I right that t is an implied class that contains 2 fields? 1. It doesn't take work to understand the logic. 2. Rather than N^4 loops, this has N^2. (Like you said, not efficient, but much better than the original.)

[KP Lee]

It is an alternative. Daniel Grunwald's solution posted just ahead of yours is better.

[KP Lee]

That's definitely the fastest and most efficient method to get a correct answer in this specific case. Other than that, ya, you missed the point. ;P

[Samuel Cragg]

Actually, if I was doing it again I would use Daniel Grunwald trick to calculate the average only once:

int closest = (from avg in new [] { inputs.Average() }
from i in inputs
orderby Math.Abs(i - avg)
select i).FirstOrDefault();

Using the lambda format (as per the rules :) ) I believe this translates to:

int closest = new[] { inputs.Average() }
.SelectMany(avg => inputs.OrderBy(i => Math.Abs(i - avg)))
.FirstOrDefault();

I believe this solution will iterate over the original collection twice - once for the average, once for the ordering, but have no idea what the big O number is for the ordering.

[RyanDonahue]

We saw fairly eye to eye.. Here was my first go:

int closest = inputs.FirstOrDefault(num => Math.Abs((Math.Abs(num) - (int)inputs.Average())) == inputs.Min(diff => Math.Abs(Math.Abs(diff) - (int)(inputs.Average()))));

And with some visual optimization

int closest = inputs.FirstOrDefault(num => Math.Abs(num - inputs.Average()) == inputs.Min(diff => Math.Abs(diff - inputs.Average())));

[EDIT] And thinking a bit more about it

int closest = inputs.Select(input => new
{
input,
diff = Math.Abs(input - inputs.Average())
}).OrderBy(x => x.diff).FirstOrDefault().input;

[KP Lee]

I really can't judge LINQ, nor lambda statements because I don't have the experience with them. The original rule was "you must use nothing but a single LINQ lambda statement." Someone else complained that the original poster used two lambda statements. As far as I can tell, the original poster used two lambda variables in a single statement. My complaint about the original statement was that it was too hard to read. Then I complained about the efficiency of the original which would loop between N^3 and N^4 times. That was after taking the time to really understand what the first statement said. I came up with a set of C# commands that would find the answer in N*2 loops. Using two if statements and either one or three more statements per loop. Once I get over the "You define the variable, then you assign a statement's value to it" prejudice, your lambda statement is very readable, more elegant than my solution and with internal optimizations going on, your N*3 loops may be as fast or faster than my N*2 loops. I may even find the "Define the statement, then assign the variable" process enjoyable in time. Daniel still gets credit for first finding a good lambda expression. :)

[alanevans]

Good point, I just wanted to use let and drop the new[]. I believe I have manged it now if you look back at my post.