Solved

Big-O of ReadOnlyCollection<T>.Last?

Posted on 2009-07-02
6
510 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
Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

 
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

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Expression Evaluater 3 38
How come this regular expression allows "e"? 14 45
MYSQL responding very slow 3 26
Code works but breaks when I add one section 4 20
It seems a simple enough task, yet I see repeated questions asking how to do it: how to pass data between two forms. In this article, I will show you the different mechanisms available for you to do just that. This article is directed towards the .N…
This article shows how to deploy dynamic backgrounds to computers depending on the aspect ratio of display
Nobody understands Phishing better than an anti-spam company. That’s why we are providing Phishing Awareness Training to our customers. According to a report by Verizon, only 3% of targeted users report malicious emails to management. With compan…

828 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