Digamos que tenemos una colección ordenada comoSortedSet oLista clasificada Con muchos (10M +) elementos. Se están realizando muchas consultas, por lo que el rendimiento importa. De las comparaciones de tiempo de ejecución, tengo la impresión de que LINQ to Objects no se beneficia de la clasificación, por lo que no aprovecho las posibles ganancias de rendimiento.

Primer ejemplo - contando los elementos en un rango:

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

No exactamente seguro de lo que LINQ to Objects hace aquí internamente, en el peor de los casos, está comprobando cada elemento que sería O (n). Se puede hacer mucho más rápido aprovechando la clasificación con una búsqueda binaria para el límite inferior y superior en O (log n).

Segundo ejemplo - SelectMany sobre lista de conjuntos:

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

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

Si LINQ paraSQL Los objetos se aprovechaban de la clasificación, ya que podía fusionar con cremallera todos los conjuntos ordenados en una gran lista ordenada en O (n). El .OrderBy en el resultado podría ser ignorado ya que la lista ya está ordenada.

En su lugar, SelectMany concatena todos los conjuntos ordenados en una lista grande (ahora sin clasificar) que requerirá otra ordenación O (n log n). Esto se puede verificar fácilmente eliminando .OrderBy y observando el orden en que se escriben los elementos en la consola.

Mi pregunta es:¿Ya existe una implementación alternativa y más eficiente de LINQ a SortedSet / SortedList?

i4o parece muy interesante, pero parece requerir colecciones de índices secundarias para mejorar el rendimiento de las consultas en la colección original. Solo quiero que las consultas en mis colecciones ordenadas se ejecuten más rápido aprovechando la clasificación.