Nehmen wir an, wir haben eine sortierte Sammlung wieSortedSet oderSortedList mit vielen (10M +) Elementen. Es wird viel abgefragt, daher ist die Leistung wichtig. Durch Laufzeitvergleiche habe ich den Eindruck, dass LINQ to Objects die Sortierung nicht ausnutzt und daher potenzielle Leistungssteigerungen nicht ausnutzt.

Erstes Beispiel - Zählen der Elemente in einem Bereich:

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

Nicht ganz sicher, was LINQ to Objects hier intern macht, im schlimmsten Fall prüft es jedes einzelne Element, das O (n) wäre. Dies kann sehr viel schneller geschehen, indem die Sortierung mit einer binären Suche nach der unteren und oberen Schranke in O (log n) ausgenutzt wird.

Zweites Beispiel - SelectMany über Liste der Sätze:

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

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

Wenn LINQ zuSQL Objekte sollten die Sortierung nutzen, es könnte effektiv alle sortierten Sätze zu einer großen sortierten Liste in O (n) zusammenführen. Die .OrderBy für das Ergebnis könnte dann ignoriert werden, da die Liste bereits sortiert ist.

Stattdessen verknüpft SelectMany alle sortierten Sätze zu einer großen (jetzt unsortierten) Liste, für die eine weitere O (n log n) -Sortierung erforderlich ist. Dies kann leicht überprüft werden, indem die .OrderBy-Datei entfernt und die Reihenfolge eingehalten wird, in der die Elemente in die Konsole geschrieben werden.

Meine Frage ist:Gibt es bereits eine alternative, effizientere Implementierung von LINQ für SortedSet / SortedList?

i4o Sieht sehr interessant aus, scheint jedoch sekundäre Indexsammlungen zu erfordern, um die Abfrageleistung für die ursprüngliche Sammlung zu verbessern. Ich möchte nur, dass Abfragen für meine sortierten Sammlungen schneller ausgeführt werden, indem die Sortierung genutzt wird.