When using Take(...) on a List<T>, is the entire list returned before Take(...) is applied?

Question

I have a List of elements of type

    public class FriendList 
    {
        public List<string> friends { get; set; } // List of friends names
        public DateTime timestamp { get; set; } // date/time on the data file
    }

and I need a procedure that gets the top 2 ordered by timestamp (and then does some other stuff with them). So what I started writing is

    public void CompareLastTwo ( )
    {
        if ( this._fhist.Count < 2 )
        {
            Console.WriteLine("Need at least two instances of Facebook profile data in the Data folder");
        }

        FriendList latest, secondLatest; 
        if ( this._fhist[0].timestamp > this._fhist[1].timestamp )
        {
            latest = this._fhist[0];
            secondLatest = this._fhist[1];
        }
        else
        {
            latest = this._fhist[1];
            secondLatest = this._fhist[0];
        }

        for ( int i = 2, n = this._fhist.Count; i < n; ++i )
        {
            if ( this._fhist[i].timestamp > latest.timestamp )
            {
                secondLatest = latest;
                latest = this._fhist[i];
            }
            else if ( this._fhist[i].timestamp > secondLatest.timestamp && this._fhist[i].timestamp <= latest.timestamp )
            {
                secondLatest = this._fhist[i];
            }
        }

        // ... 

    }

but then I realized from looking at How to get first N elements of a list in C#? that I can do

List<FriendList> latestTwoFriendLists = this._fhist.OrderBy(L => L.timestamp).Take(2);

which is more compact, but is it as efficient???? Or does the process of computing the right side of the equation get an entire ordered list before Takeing first 2?

Answer 1

OrderBy will sort the entire collection when Take requests first item.

So the entire LINQ query will be O(n*log(n)), not O(n) like your existing code.

Answer 2

Generally speaking, OrderBy does not have to sort all items in this case, if it is implemented as lazy sort. Standard linq sort is not lazy so it will sort everything. Your solution is as fast as it can be, You would not find better. Just make it standalone function to clean things up, like this:

 public class FriendList
        {
            public List<string> friends { get; set; } // List of friends names
            public DateTime timestamp { get; set; } // date/time on the data file
        }

        public static Tuple<T, T> GetTwoBiggest<T>(IEnumerable<T> array, Comparison<T> comp)
        {
            var enumerator = array.GetEnumerator();

            if (!enumerator.MoveNext()) { throw new ArgumentException("We need collection with at least two items"); }
            T max1 = enumerator.Current;

            if (!enumerator.MoveNext()) { throw new ArgumentException("We need collection with at least two items"); }
            T max2 = enumerator.Current;

            if (comp(max1, max2) < 0)
            {
                T tmp = max1;
                max1 = max2;
                max2 = tmp;
            }

            while (enumerator.MoveNext())
            {
                T actual = enumerator.Current;
                if (comp(actual, max1) > 0)
                {
                    max2 = max1;
                    max1 = actual;
                }
                else if (comp(actual, max2) > 0)
                {
                    max2 = actual;
                }
            }

            return new Tuple<T, T>(max1, max2);
        }

        private void button6_Click(object sender, EventArgs e)
        {
            List<FriendList> list = new List<FriendList>()
            {
                new FriendList() { timestamp = new DateTime(2015,1,1) },
                new FriendList() { timestamp = new DateTime(2015,10,2) },
                new FriendList() { timestamp = new DateTime(2015,5,3) },
                new FriendList() { timestamp = new DateTime(2015,2,4) },
                new FriendList() { timestamp = new DateTime(2015,3,5) },
                new FriendList() { timestamp = new DateTime(2015,7,6) },
                new FriendList() { timestamp = new DateTime(2015,11,7) },
                new FriendList() { timestamp = new DateTime(2015,8,8) },
            };

            var twoBiggest = GetTwoBiggest(list, (a, b) => a.timestamp.CompareTo(b.timestamp));

            Console.WriteLine(twoBiggest.Item1.timestamp);
            Console.WriteLine(twoBiggest.Item2.timestamp);
        }