Solved

Big-O of ReadOnlyCollection<T>.Last?

Posted on 2009-07-02
6
506 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
DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

 
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

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Setting ACL permissions after creating user with DC replication lag possible? 5 38
Error in page 3 45
Syntax Error 2 43
Visual Studio TFS - how do I check in my code? 2 28
Many of us here at EE write code. Many of us write exceptional code; just as many of us write exception-prone code. As we all should know, exceptions are a mechanism for handling errors which are typically out of our control. From database errors, t…
A long time ago (May 2011), I have written an article showing you how to create a DLL using Visual Studio 2005 to be hosted in SQL Server 2005. That was valid at that time and it is still valid if you are still using these versions. You can still re…
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…
A short film showing how OnPage and Connectwise integration works.

911 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

21 Experts available now in Live!

Get 1:1 Help Now