?
Solved

Big-O of ReadOnlyCollection<T>.Last?

Posted on 2009-07-02
6
Medium Priority
?
528 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
6 Comments
 
LVL 39

Accepted Solution

by:
abel earned 2000 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
TCP/IP Network Protocol Cheat Sheet

TCP/IP is a set of network protocols which is best known for connecting the machines that make up the Internet. The truth is that TCP/IP is one of the oldest network protocols and its survival is mainly based on its simplicity and universality.

 
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

Visualize your virtual and backup environments

Create well-organized and polished visualizations of your virtual and backup environments when planning VMware vSphere, Microsoft Hyper-V or Veeam deployments. It helps you to gain better visibility and valuable business insights.

Question has a verified solution.

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

Summary Displaying images in RichTextBox is a common requirement with limited solutions available. Pasting through clipboard or embedding into RTF content only support static images.  This article describes how to insert Windows control objects int…
In my previous two articles we discussed Binary Serialization (http://www.experts-exchange.com/A_4362.html) and XML Serialization (http://www.experts-exchange.com/A_4425.html). In this article we will try to know more about SOAP (Simple Object Acces…
If you’ve ever visited a web page and noticed a cool font that you really liked the look of, but couldn’t figure out which font it was so that you could use it for your own work, then this video is for you! In this Micro Tutorial, you'll learn yo…
Add bar graphs to Access queries using Unicode block characters. Graphs appear on every record in the color you want. Give life to numbers. Hopes this gives you ideas on visualizing your data in new ways ~ Create a calculated field in a query: …

752 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