How linq function OrderByDescending and OrderBy for string length works internally? Is it faster than doing it with loop?

Question

My question is raised based on this question, I had posted an answer on that question..here

This is the code.

var lines = System.IO.File.ReadLines(@"C:\test.txt");
var Minimum = lines[0];//Default length set
var Maximum = "";

foreach (string line in lines)
{    
    if (Maximum.Length < line.Length)
    {
        Maximum = line;
    }

    if (Minimum.Length > line.Length)
    {
        Minimum = line;
    }
}

and alternative for this code using LINQ (My approach)

var lines = System.IO.File.ReadLines(@"C:\test.txt");
var Maximum = lines.OrderByDescending(a => a.Length).First().ToString();
var Minimum = lines.OrderBy(a => a.Length).First().ToString();

LINQ is easy to read and implement..

I want to know which one is good for performance. And how Linq work internally for OrderByDescending and OrderBy for ordering by length?

Answer 1

You can read the source code for OrderBy.

Stop doing micro-optimizing or premature-optimization on your code. Try to write code that performs correctly, then if you face a performance problem later then profile your application and see where is the problem. If you have a piece of code which have performance problem due to finding the shortest and longest string then start to optimize this part.

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3% - Donald Knuth

File.ReadLines is returning an IEnumerable<string>, It means that if you do a foreach over it it will return data to you one by one. I think the best performance improvement you can do here is to improve the reading of file from the disk. If it is small enough to load the whole file into memory use File.ReadAllLines, if it is not try reading the file in big chunks that fits in memory. Reading a file line by line will cause performance degradation due to I/O operation from disk. So the problem here is not how LINQ or loop perform, The problem is in number of disk reads.

Answer 2

In my opinion, you need to understand some points for deciding what is the best way.

First, let's think that we want to solve the problem with LINQ. Then, to write the most optimized code, you must understand Deferred Execution. Most Linq methods, such as Select, Where, OrderBy, Skip, Take and some others uses DE. So, what is Deferred Execution? It means that, these methods will not be executed unless the user doesn't need them. These methods will just create iterator. And this iterator is ready to be executed, when we need them. So, how can user make them execute? The answer is, with the help of foreach which will call GetEnumerator or other Linq methods. Such as, ToList(), First(), FirstOrDefault(), Max() and some others.

These process will help us to gain some performance.
Now, let's come back to your problem. File.ReadLines will return IEnumerable<string>, which it means that, it will not read the lines, unless we need them. In your example, you have twice called sorting method for this object, which it means that it will sort this collection over again twice. Instead of that, you can sort the collection once, then call ToList() which will execute the OrderedEnumerable iterator and then get first and last element of the collection which physically inside our hands.

var orderedList = lines
   .OrderBy(a => a.Length) // This method uses deferred execution, so it is not executed yet
   .ToList(); // But, `ToList()` makes it to execute.

var Maximum = orderedList.Last();
var Minimum = orderedList.First();

BTW, you can find OrderBy source code, here.

It returns OrderedEnumerable instance and the sorting algorithm is here:

public IEnumerator<TElement> GetEnumerator() 
{
    Buffer<TElement> buffer = new Buffer<TElement>(source);
    if (buffer.count > 0) 
    {
        EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
        int[] map = sorter.Sort(buffer.items, buffer.count);
        sorter = null;
        for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
    }
}

And now, let's come back to another aspect which effects the performance. If you see, Linq uses another element to store sorted collection. Of course, it will take some memory, which tells us it is not the most efficent way.

I just tried to explain you how does Linq work. But, I am very agree with @Dotctor as a result to your overall answer. Just, don't forget that, you can use File.ReadAllLines which will not return IEnumerable<stirng>, but string[]. What does it mean? As I tried to explain in the beginning, difference is that, if it is IEnumerable, then .net will read line one by one when enuemrator enumerates over iterator. But, if it is string[], then all lines in our application memory.

Answer 3

With the second method, you are not only sorting the lines twice... You are reading the file twice. This because File.ReadLines returns a IEnumerable<string>. This clearly shows why you shouldn't ever ever enumerate a IEnumerable<> twice unless you know how it was built. If you really want to do it, add a .ToList() or a .ToArray() that will materialize the IEnumerable<> to a collection... And while the first method has a memory footprint of a single line of text (because it reads the file one line at a time), the second method will load the whole file in memory to sort it, so will have a much bigger memory footprint, and if the file is some hundred mb, the difference is big (note that technically you could have a file with a single line of text long 1gb, so this rule isn't absolute... It is for reasonable files that have lines long up to some hundred characters :-) )

Now... Someone will tell you that premature optimization is evil, but I'll tell you that ignorance is twice evil.

If you know the difference between the two blocks of code then you can do an informed choice between the two... Otherwise you are simply randomly throwing rocks until it seems to work. Where seems to work is the keyword here.

Answer 4

The most efficient approach is to avoid LINQ here, the approach using foreach needs only one enumeration.

If you want to put the whole file into a collection anyway you could use this:

List<string> orderedLines = System.IO.File.ReadLines(@"C:\test.txt")
    .OrderBy(l => l.Length)
    .ToList();
string shortest = orderedLines.First();
string longest  = orderedLines.Last();

Apart from that you should read about LINQ's deferred execution.

Also note that your LINQ approach does not only order all lines twice to get the longest and the shortest, it also needs to read the whole file twice since File.ReadLines is using a StreamReader(as opposed to ReadAllLines which reads all lines into an array first).

MSDN:

When you use ReadLines, you can start enumerating the collection of strings before the whole collection is returned; when you use ReadAllLines, you must wait for the whole array of strings be returned before you can access the array

In general that can help to make your LINQ queries more efficient, f.e. if you filter out lines with Where, but in this case it's making things worse.

As Jeppe Stig Nielsen has mentioned in a comment, since OrderBy needs to create another buffer-collection internally(with ToList the second), there is another approach that might be more efficient:

string[] allLines = System.IO.File.ReadAllLines(@"C:\test.txt"); 
Array.Sort(allLines, (x, y) => x.Length.CompareTo(y.Length));
string shortest = allLines.First();
string longest  = allLines.Last();

The only drawback of Array.Sort is that it performs an unstable sort as opposed to OrderBy. So if two lines have the same length the order might not be maintained.