Performance of First() vs Last() on a SortedDictionary

Question

I'm using SortedDictionaries to simulate a Queue (due to some requirements that I have), and I'm calling Last() over the sorted dictionary to get the item that I need to dequeue.

I was just wondering about the performance of using a custom comparer and calling First() or keep calling Last().

After decompiling the .NET 3.5 assemblies, I found that the SortedDictionary class does have a Count property, so I'm guessing the framework just returns the item at position 0 when First is called, and the item at position [count-1] when Last is called, am I right?

@Oded: Those are extension methods. The interaction is non-trivial. — SLaks, Sep 14 '12 at 19:13

score 7 · Accepted Answer · answered Sep 14 '12 at 19:14

7

No.

Since SortedDictionary does not implement IList<TValue> (which has a this[int] indexer), Last() has no choice but to iterate through the whole thing.

answered Sep 14 '12 at 19:14

SLaks

868,454
176
1,908
1,964

ok, so you're saying that calling First() would certainly be way more efficient than calling Last? so, if I make my comparer work so that the first items that i need to dequeue are inserted at the start of the collection, and then call First(), would it be a decent gain? – GR7 Sep 14 '12 at 19:20
Yes; that should make a difference. – SLaks Sep 14 '12 at 20:01
Are you sure ? why would it then be called SORTED in the first place ? SortedDictionary is implemented upon some tree(red-black, B-tree whatever). So Last or first actualy are o(1)! see http://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary – Kousalik Mar 30 '14 at 21:20
or this http://stackoverflow.com/questions/935621/whats-the-difference-between-sortedlist-and-sorteddictionary – Kousalik Mar 30 '14 at 21:26
@Kousalik: That is true in theory, but there is no way for `Last()` to know that. (also, getting the last element in any BST is `O(log n)`, not `O(1)`) – SLaks Mar 30 '14 at 21:35
i think that it depends on the actual implementation, however this doesn't mean it has to iterate the whole thing. I wouldnt be suprised if there is explicit reference to last entry. It's Sorted. It's not just another name for tree. There are many ways how to keep the the Last() on o(1). It's about the litle bit higher effort on Add() and Remove(). – Kousalik Mar 30 '14 at 21:45
@Kousalik: Again, that's true in theory, but the LINQ `Last()` method has no way of knowing anything about that. http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs#75722fd194dc2e0e – SLaks Mar 30 '14 at 22:01
Now I see the LINQ tag ... but the question doesn't say a word about it. What I can see is question about System.collections.generic.SortedDictionary being used as Queue. Now I am confused. – Kousalik Mar 30 '14 at 22:15
1

@Kousalik: The question is specifically asking about the LINQ `First()` and `Last()` methods, which are not tied to any specific collection implementation. – SLaks Mar 30 '14 at 22:29

score 5 · Answer 2 · answered Sep 14 '12 at 19:22

The Last method is an extension method in the Enumerable class. The implementation of Last first tries to cast the IEnumerable (your SortedDictionary) to IList<T>. If it can, then it uses the Count property to directly access the last element. If it can't, then it has to iterate over all elements to get to the last one. SortedDictionary doesn't implement IList<T>, so Last will iterate over all elements.

Performance of First() vs Last() on a SortedDictionary

2 Answers2