Friday programming quiz

[Daniel Grunwald]

int closest = inputs.OrderBy(i => Math.Abs(i - inputs.Average())).FirstOrDefault();

This is O(N²) as Average() gets called for every sort key that gets calculated. We can do better by storing the average in a variable. And we can use LINQ to introduce variables within an expression:

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

This is O(N log N), but note that instead of sorting, we just need to find the minimum. Sadly, all the Min() methods compare the element itself, not just a key. However, we can build a suitable implementation using Aggregate():

int closest = (from avg in new[] { inputs.Average() }
select inputs.Aggregate((a, b) => Math.Abs(a - avg) < Math.Abs(b - avg) ? a : b)
).Single();

This runs in linear time, and does pretty much the same as an implementation using a loop would do.

[jesarg]

It's a great solution; it's in the regular LINQ format instead of the lambda format, though. Also, it performs better than the sample solution.

[jesarg]

Ok, you just won the programming quiz with flying colors. Your last implementation is doing 5 million elements in sub-second. :) Thanks to everyone who participated, and hopefully, I'll be able to think of another great quiz in a week.

[jesarg]

Thanks; LINQ becomes a lot easier once you've used it for a few months, though; you probably just need more practice rather than a course. When I started out, it was confusing, but now it feels easier than loops. LINQ almost always performs worse than using regular loops, though; typically, a loop-based implementation is about 4 times faster when you have a ton of elements.

[YvesDaoust]

This quizz is clearly O(N): computing the average is O(N); computing the absolute deviations from the average is O(N); selecting the smallest element is also O(N). I am not LINQ proficient, but I am pretty sure LINQ implements averaging in linear time, as it would do to build the deviations vector. Finding the position of the minimum of the vector is also O(N). I have nothing against high-level langages, but IMO solving such an easy problem with an O(N^3) hammer is not so welcome.

[Bruno Tagliapietra]

maybe I've found an alternative inputs.Select(x => new { OriginalValue = x, Distance = Math.Abs(x - inputs.Average()) }).OrderBy(a => a.Distance).First().OriginalValue;

[prasun r]

Even if you say a lambda statement with only one semi colon, still we can have an anonymous method inside the lambda expression. So lot of clarification required in the challenge statement.

[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