Допустим, у нас есть отсортированная коллекция, такая какSortedSet или жеSortedList со многими (10M +) элементами. Происходит много запросов, поэтому производительность имеет значение. Из сравнений во время выполнения у меня сложилось впечатление, что LINQ to Objects не использует преимущества сортировки, поэтому не использует потенциальный прирост производительности.

Первый пример - подсчет элементов в диапазоне:

        var mySortedSet1 = new SortedSet<int>();
        // populate ...
        int rangeCount = (from n in mySortedSet1
                          where ((n >= 1000000000) && (n <= 2000000000))
                          select n).Count();

Не совсем уверен, что здесь делает LINQ to Objects, в худшем случае он проверяет каждый элемент, который будет O (n). Это можно сделать намного быстрее, воспользовавшись преимуществами сортировки с двоичным поиском нижней и верхней границы в O (log n).

Второй пример - SelectMany над списком наборов:

        var myListOfSortedSets = new List<SortedSet<int>>();
        // populate...

        var q = myListOfSortedSets.SelectMany(s => s).OrderBy(s => s);
        foreach (var n in q)
        {
            Console.WriteLine(n);
        }

Если LINQ toSQL Объекты должны были воспользоваться преимуществами сортировки, она могла эффективно объединить все отсортированные наборы в один большой отсортированный список в O (n). .OrderBy для результата может быть проигнорировано, поскольку список уже отсортирован.

Вместо этого SelectMany объединяет все отсортированные наборы в один большой (теперь несортированный) список, для которого потребуется другая O (n log n) сортировка. Это можно легко проверить, удалив .OrderBy и соблюдая порядок, в котором элементы записываются на консоль.

Мой вопрос:уже есть альтернативная, более эффективная реализация LINQ для SortedSet / SortedList?

i4o выглядит очень интересно, но кажется, что для повышения производительности запросов к исходной коллекции требуются вторичные коллекции индексов. Я просто хочу, чтобы запросы в моих отсортированных коллекциях выполнялись быстрее, используя преимущества сортировки.