0

The way I normally find the Min/Max in the database is using 

var employeeWithMinSalary = employees.OrderBy(x=>x.Salary).First()
var employeeWithMaxSalary = employees.OrderByDescending(x=>x.Salary).First()

However, the performance is O(n * Log(n)).

Is there any other way to Optimize the performance to O(n) using Linq only? (No other libraries)

Pavel
  • 97
  • 2
  • 9
  • 2
    List.Max and List.Min. – jdweng Aug 23 '19 at 16:42
  • 1
    There is a decent discussion here [link](https://stackoverflow.com/questions/1101841/how-to-perform-max-on-a-property-of-all-objects-in-a-collection-and-return-th) which may be beneficial to read. – Karen Payne Aug 23 '19 at 16:58
  • @KarenPayne that discussion is for raw linq. I dont think that methodology would be good with EF – Marie Aug 23 '19 at 17:05
  • It might be easier to query the max value then grab the record(s) that matches that – Marie Aug 23 '19 at 17:07
  • 2
    Did you put on index on the `Salary` column? A `select top(1) ...` should be fast on an indexed column. – Dirk Aug 23 '19 at 17:09
  • 1
    @Dirk Yep. With an index this operation is O(1). – David Browne - Microsoft Aug 23 '19 at 18:34
  • 1
    And even without an Index, it might be O(n). For instance on SQL Server you might get a plan with a "TOP N Sort" query operator that finds the top 1 row with a single pass through the table. – David Browne - Microsoft Aug 23 '19 at 21:53
  • FYI you can combine the queries using an empty `GroupBy` but I am not sure if that will be optimized into one pass for both on the SQL side. – NetMage Aug 23 '19 at 22:07

1 Answers1

-1

It's not necessary to sort a list to find the Min/Max value from a list. The best sorting algorithm has an average complexity of O(N*logN). Both Max and Min operations shouldn't take more than O(N), even though the list is unsorted.

You can implement the solution posted here or implementing the following code:

   private static Employee MaxBySalary(List<Employee> employees)
    {
        Employee employee = null;
        employees.ForEach(x => employee = ( employee != null && employee.Salary > x.Salary) ? employee : x );
        return employee;
    }

    private static Employee MinBySalary(List<Employee> employees)
    {
        Employee employee = null;
        employees.ForEach(x => employee = (employee != null && employee.Salary < x.Salary) ? employee : x);
        return employee;
    }

Both approaches have O(N) complexity

David Donari
  • 599
  • 7
  • 17
  • Can I get the whole entity using MIn/Max? – Pavel Aug 23 '19 at 16:52
  • @Pavel Do you need the whole record? Your title/question say and imply value – Marie Aug 23 '19 at 17:06
  • 2
    @DavidDonari Do those work with Entity Framework? If not it is going to dump the entire database into memory to find the value. – Marie Aug 23 '19 at 17:11
  • Code-only answers are discouraged. Please click on [edit] and add some words summarising how your code addresses the question. [From Review](https://stackoverflow.com/review/low-quality-posts/23872526) – Nick Aug 24 '19 at 04:38
  • @Nick thanks for your suggestions. Please check now – David Donari Aug 25 '19 at 14:50
  • 1
    @DavidDonari it looks much better. I wish I understood the subject matter well enough to judge its technical merit too. – Nick Aug 26 '19 at 06:52