Solved

Big-O of ReadOnlyCollection<T>.Last?

Posted on 2009-07-02
6
503 Views
Last Modified: 2013-11-11
Folks,

What's the Big-O of ReadOnlyCollection<T>.Last (Linq extension method)?
I'm hoping o(1), but I can't tell from the documentation.

It seems the linq extension is on IEnumerable...but perhaps it leverages the underlying IList for faster access?  I have no clue.
0
Comment
Question by:sfun28
  • 3
  • 3
6 Comments
 
LVL 39

Accepted Solution

by:
abel earned 500 total points
ID: 24773890
As you maybe well aware of, the ReadOnlyCollection is not nothing more then a wrapper around an IList (which you have to give with the constructor). All its operations are performed on this underlying datatype.

But.... the Last method is actually a static extension function (all ext. functions are static), which is part of System.Linq.Enumerable.

But... and now it gets tricky...: the Enumerable.Last method has a signature as follows:

  public static TSource Last<TSource>(this IEnumerable<TSource> source)
meaning that it is an extension function to anything that implements IEnumerable. So far from the documentation. Now let's have a look at the implementation. As it appears, the Enumerable knows about the IList interface and the first thing it tries is to cast the IEnumerable to an IList. If it succeeds, it returns (simplified) the following:

IList<TSource> list = source as IList<TSource>;return list[list.Count -1]
That is indeed an O(1) operation and actually, it's the answer to your question since the ReadoOnlyCollection must use an underlying IList type. But let's take it a tad further to see what happens if the IEnumerable does not also derive from IList. In that case, the method cannot do anything else then looping through all the until the end. This is O(n) performance and not really efficient. Luckily, most collection types, including System.Array (of which all array types derive) implement the IList interface and as a result, the performance of Last() is instantaneous: O(1). (I'm not certain whether the same holds for Mono's implementation).

For completeness, here's the reference that I used to look this up with Reflector:

public static TSource Last<TSource>(this IEnumerable<TSource> source)

{

    if (source == null)

    {

        throw Error.ArgumentNull("source");

    }

    IList<TSource> list = source as IList<TSource>;

    if (list != null)

    {

        int count = list.Count;

        if (count > 0)

        {

            return list[count - 1];

        }

    }

    else

    {

        using (IEnumerator<TSource> enumerator = source.GetEnumerator())

        {

            if (enumerator.MoveNext())

            {

                TSource current;

                do

                {

                    current = enumerator.Current;

                }

                while (enumerator.MoveNext());

                return current;

            }

        }

    }

    throw Error.NoElements();

}
 

 
 

 

Open in new window

0
 
LVL 1

Author Closing Comment

by:sfun28
ID: 31599435
Wow!!!  Thanks so much!  This was one of the most complete answers I've ever gotten.  Great idea to examine this in reflector...I wouldn't have thought about that.
0
 
LVL 39

Expert Comment

by:abel
ID: 24774576
compliments like that should be in the open, don't you think? if you don't mind, I copy it here so others can see it too (yes, I know, I'm egocentric! lol ;-)

(from grading comment)
Wow!!! Thanks so much! This was one of the most complete answers I've ever gotten. Great idea to examine this in reflector...I wouldn't have thought about that.
Tx for the great compliment and glad to have been of help! :)
0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 1

Author Comment

by:sfun28
ID: 24774578
Out of curiosity, is the code reference something you just copied/pasted from reflector?
0
 
LVL 39

Expert Comment

by:abel
ID: 24774653
Yes, I just pasted that from Reflector, nothing of it is my own. That also means, that the code is not exactly the same as the Shared Source Code from Microsoft that you get into when you are debugging. But the Shared Source Code is protected by copyright law, but reflected assembly is not.

There is a small mishap in my story. It doesn't change anything, but the story above might be understood as that IList and IList<T> are the same. System.Array implements IList and ReadOnlyCollection implements both IList<T> and IList. For the functionality in the code above this doesn't make any difference as an Array / IList can be cast to IList<T>.

-- Abel --


0
 
LVL 1

Author Comment

by:sfun28
ID: 24775659
Thanks!!!  Great explanation!
0

Featured Post

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

The object model of .Net can be overwhelming at times – so overwhelming that quite trivial tasks often take hours of research. In this case, the task at hand was to populate the datagrid from SQL Server database in Visual Studio 2008 Windows applica…
In my previous article (http://www.experts-exchange.com/Programming/Languages/.NET/.NET_Framework_3.x/A_4362-Serialization-in-NET-1.html) we saw the basics of serialization and how types/objects can be serialized to Binary format. In this blog we wi…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now