Могу ли я положиться на порядок SortedDictionary в Linq, и делает ли он это эффективно?

Question

При использовании SortedDictionary в Linq и итерации по KeyValuePair, которую он предоставляет, могу ли я быть уверен, что сложный запрос linq выполнит его в порядке возрастания? Вот краткий, хотя и немного запутанный пример:

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"

Вопрос (ы):

1. Кажется, это работает, но я могу положиться на это поведение?
2. Это эффективно, или группа скинула это?
3. Правильно ли работает добавление sortedDict.Reverse ()? (кажется)
4. Как PLinq справится с этим - и будет ли он по-прежнему согласованным?

Если это не гарантировано, я знаю, как я могу вытянуть «приоритет» в группировку и упорядочить ее по факту. Но я бы предпочел не ...

Answer 1

1. Да, вы можете доверять порядку SortedDictionary. Иначе было бы бессмысленно:)

2. Было бы немного более эффективно без предложения let. Просто сделай:

   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() };
   

   Тем не менее, вы все еще довольно часто просматриваете словарь. Разве вам не нужна обратная карта от ключа к приоритетам, содержащим этот ключ? Это можно было бы построить гораздо эффективнее. Как вы говорите, пример довольно запутанный. Если бы вы могли рассказать нам, чего вы пытаетесь достичь в своем реальном коде, мы могли бы придумать что-то лучшее. (Если это именно такая ситуация, я, конечно, могу над этим поработать - я бы предпочел не делать этого, а потом выяснить, что реальность сильно отличается!)

3. Вызов Reverse () действительно будет работать, но он буферизует все данные. Если вы хотите сделать это в обратном порядке, я предлагаю вам дать SortedDictionary подходящий IComparer для начала.

4. Parallel LINQ "интересен", когда речь идет о заказе. Может быть, сейчас все по-другому, но я какое-то время назад развлекался , когда я строил на нем множество Мандельброта ...

Answer 2

Вот ответ о том, какие методы linq сохраняют порядок.

Наблюдая за запросом, похоже, что у вас есть:

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

Все это каким-то образом сохранит порядок.

Answer 3

1. Да, вы можете. SortedDictionary не может быть отсортирован. Он гарантированно останется отсортированным, даже если он выдаст исключения
2. Эффективен по мере сортировки. Вы могли бы сделать это более эффективно с знанием предметной области, какие типы используются и т. Д., Но это было бы значительно и не стоило бы в 99,99% случаев
3. да:)
4. похоже я ошибся, у plinq проблемы с заказом. см. сообщение Джона об этом