Can I rely on the order of a SortedDictionary in Linq, and is it doing this efficiently?

Question

When using a SortedDictionary in Linq and iterating over the KeyValuePair it provides, can I be assured that a complex linq query will execute it in ascending order? Here's a brief, although a bit confusing example:

Random r = new Random();
//build 100 dictionaries and put them into a sorted dictionary
//with "priority" as the key and it is a number 0-99.
SortedDictionary<int, Dictionary<int, double>> sortedDict = 
    new SortedDictionary<int, Dictionary<int, double>>();
for (int i = 0; i < 100; i++)
{
    Dictionary<int, double> dict = new Dictionary<int, double>();
    //create the dictionary and a random 10 k/v pairs
    for (int j = 0; j < 10; j++)
    {
        dict[r.Next(0, 100)] = r.NextDouble() * i * 10;
    }
    sortedDict[i] = dict;
}

IEnumerable<int> keys = Enumerable.Range(0, 100);

//the goal is to find the FIRST existence of the "key" inside one
//of the inner dictionaries going through the SortedDictionary IN ORDER
//this appears to work:
var qry = from key in keys
          from priority in sortedDict
          where priority.Value.ContainsKey(key)
          let value = priority.Value[key]
          group value by key into keyGroup
          let firstValue = keyGroup.First()
          select new { Key = keyGroup.Key, Value = firstValue };

// the result is as expected, a list of the numbers at most 0-99 and their
// value found in the dictionary with the lowest "priority"

The question(s):

1. It appears to work, but can I rely on this behavior?
2. Is this efficient, or does the group by throw it off?
3. Does adding "sortedDict.Reverse()" work properly too? (it appears to)
4. How would PLinq handle this - and would it still be consistent?

If this isn't guaranteed, I know how I can pull the "priority" into the grouping and order by it after the fact. But I'd rather not...

Answer 1

1. Yes you can. The SortedDictionary has no way to get unsorted. It is guaranteed to stay sorted, even if it throws exceptions
2. It is efficent as sorting gets. You could do it more efficently with domain knowlege of what types are used and so on, but it would be by much and is not worth it in 99,99% of the cases
3. yes:)
4. seems i was wrong, plinq has problems with ordering. see jon´s post for that

Answer 2

1. Yes, you can trust the order of SortedDictionary. It would be pointless otherwise :)

2. It would be slightly more efficient without the "let" clause. Just do:

   var qry = from key in keys
             from priority in sortedDict
             where priority.Value.ContainsKey(key)
             let value = priority.Value[key]
             group value by key into keyGroup
             select new { Key = keyGroup.Key, Value = keyGroup.First() };
   

   However, you're still scanning through the dictionary quite a lot with this. Don't you basically want a reverse map from key to priorities containing that key? That could be constructed much more efficiently. As you say, the example is pretty confusing. If you could tell us what you're trying to achieve in your real code, we may be able to come up with something better. (If it's exactly this situation, I can certainly work on that - I'd rather not do so and then find out that reality is very different though!)

3. Calling Reverse() will indeed work - but it will buffer all the data. If you want it in reverse order, I suggest you give the SortedDictionary an appropriate IComparer to start with.

4. Parallel LINQ is "interesting" when it comes to order. It may be different right now, but I had fun a while ago when I was plotting the Mandelbrot set using it...

Answer 3

Here's an answer about which linq methods preserve order.

Eyeballing the query, it looks like you have:

  keys.SelectMany(...)
    .Where(...)
    .GroupBy(...)
    .Select(g => g.First())
    .Select(...);

All of which will preserve ordering in some way.