LINQ Leistung für große Sammlungen

Question

Ich habe eine große Sammlung von Zeichenfolgen (bis zu 1M) alphabetisch sortiert. Ich habe mit LINQ-Abfragen gegen diese Sammlung mit HashSet, SortedDictionary und Dictionary experimentiert. Ich bin statische Caching der Sammlung, es ist bis zu 50 MB groß, und ich rufe immer die LINQ-Abfrage gegen die zwischengespeicherte Sammlung. Mein Problem ist, wie folgt:

Unabhängig von Kollektionstyp, Leistung ist viel schlechter als SQL (bis zu 200 ms). Wenn eine ähnliche Abfrage für die zugrunde liegenden SQL-Tabellen ausgeführt wird, ist die Leistung viel schneller (5-10 ms). Ich habe meine LINQ-Abfragen wie folgt umgesetzt:

public static string ReturnSomething(string query, int limit) 
{ 
    StringBuilder sb = new StringBuilder(); 
    foreach (var stringitem in MyCollection.Where(
     x => x.StartsWith(query) && x.Length > q.Length).Take(limit)) 
    { 
     sb.Append(stringitem); 
    } 

    return sb.ToString(); 
} 

Es ist mein Verständnis, dass die HashSet, Wörterbuch, usw. implementieren Lookups anstelle der Standard-Enumeration Binärbaum-Suche. Was sind meine Optionen für leistungsstarke LINQ-Abfragen in die erweiterten Sammlungsarten?

Answer 1

In Ihrem aktuellen Code, den Sie machen keinen Gebrauch von einem der Besonderheiten der Dictionary/SortedDictionary/HashSet Sammlungen machen, sie verwenden Sie die gleiche Art und Weise, dass Sie eine List verwenden würden. Deshalb sehen Sie keinen Unterschied in der Leistung.

Wenn Sie ein Dictionary als Index verwenden, bei dem die ersten paar Zeichen des Strings der Schlüssel sind und eine Liste der Strings der Wert ist, können Sie aus dem Suchstring einen kleinen Teil der gesamten String-Sammlung auswählen mögliche Übereinstimmungen

Ich schrieb die Klasse unten, um dies zu testen. Wenn ich es mit einer Million Strings bevölkere und mit einer achtstelligen Zeichenfolge suche, durchläuft es alle möglichen Übereinstimmungen in etwa 3 ms. Das Suchen mit einer einzelnen Zeichenfolge ist der schlimmste Fall, aber es findet die ersten 1000 Übereinstimmungen in ungefähr 4 ms. Das Finden aller Übereinstimmungen für eine Zeichenfolge mit einem Zeichen dauert ungefähr 25 ms.

Die Klasse erstellt Indizes für 1, 2, 4 und 8 Zeichenschlüssel. Wenn Sie sich Ihre spezifischen Daten ansehen und nach was Sie suchen, sollten Sie in der Lage sein, auszuwählen, welche Indizes erstellt werden sollen, um sie für Ihre Bedingungen zu optimieren.

public class IndexedList { 

    private class Index : Dictionary<string, List<string>> { 

     private int _indexLength; 

     public Index(int indexLength) { 
      _indexLength = indexLength; 
     } 

     public void Add(string value) { 
      if (value.Length >= _indexLength) { 
       string key = value.Substring(0, _indexLength); 
       List<string> list; 
       if (!this.TryGetValue(key, out list)) { 
        Add(key, list = new List<string>()); 
       } 
       list.Add(value); 
      } 
     } 

     public IEnumerable<string> Find(string query, int limit) { 
      return 
       this[query.Substring(0, _indexLength)] 
       .Where(s => s.Length > query.Length && s.StartsWith(query)) 
       .Take(limit); 
     } 

    } 

    private Index _index1; 
    private Index _index2; 
    private Index _index4; 
    private Index _index8; 

    public IndexedList(IEnumerable<string> values) { 
     _index1 = new Index(1); 
     _index2 = new Index(2); 
     _index4 = new Index(4); 
     _index8 = new Index(8); 
     foreach (string value in values) { 
      _index1.Add(value); 
      _index2.Add(value); 
      _index4.Add(value); 
      _index8.Add(value); 
     } 
    } 

    public IEnumerable<string> Find(string query, int limit) { 
     if (query.Length >= 8) return _index8.Find(query, limit); 
     if (query.Length >= 4) return _index4.Find(query,limit); 
     if (query.Length >= 2) return _index2.Find(query,limit); 
     return _index1.Find(query, limit); 
    } 

} 

Answer 2

Wenn Sie eine "beginnt mit" machen, kümmern Sie sich nur um ordinale Vergleiche, und Sie können die Sammlung sortiert haben (wieder in Ordnungsreihenfolge), dann würde ich vorschlagen, dass Sie die Werte in einer Liste haben. Sie können dann binäre Suche, um den ersten Wert zu finden, der mit dem rechten Präfix beginnt, dann gehen Sie die Liste linear nach unten und geben Ergebnisse, bis der erste Wert nicht mit dem rechten Präfix beginnt.

In der Tat könnte man wahrscheinlich zum ersten Wert eine andere binäre Suche tun, die nicht mit dem Präfix beginnt, so würden Sie einen Start- und einen Endpunkt haben. Dann müssen Sie nur das Längenkriterium auf diesen passenden Teil anwenden. (Ich hoffe, dass, wenn es sich um sinnvolle Daten handelt, die Präfix-Übereinstimmung die meisten Kandidatenwerte loswerden wird.) Die Suche nach dem ersten Wert, der nicht mit dem Präfix beginnt, ist die Suche nach dem lexikographisch-ersten Wert, der nicht - z Suchen Sie mit "ABC" nach "ABD".

Nichts davon verwendet LINQ, und es ist alles sehr spezifisch für Ihren speziellen Fall, aber es sollte funktionieren. Lassen Sie mich wissen, wenn das alles keinen Sinn ergibt.

Answer 3

Gerade in Ihrem Code sucht, würde ich sagen, dass Sie den Vergleich Vorteil von Kurzschlüssen nehmen neu anordnen sollten, wenn Booleschen Operatoren:

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit)) 

Der Vergleich der Länge immer ein O sein wird (1) Operation (da die Länge als Teil der Zeichenfolge gespeichert wird, zählt sie nicht jedes Zeichen jedes Mal), während der Aufruf von StartsWith eine O (N) -Operation sein wird, wobei N die Länge der Abfrage ist (oder die Länge der Zeichenfolge, je nachdem, welcher Wert kleiner ist).

Indem Sie den Vergleich der Länge vor dem Aufruf von Starts, wenn dieser Vergleich fehlschlägt, können Sie sich zusätzliche Zyklen speichern, die bis hinzufügen könnte, wenn Elemente eine große Zahl von Verarbeitung.

Ich glaube nicht, dass eine Nachschlagetabelle Ihnen hier helfen wird, da Nachschlagetabellen gut sind, wenn Sie den gesamten Schlüssel vergleichen, nicht Teile des Schlüssels, wie Sie es mit dem Aufruf von StartsWith machen.

Vielmehr könnten Sie besser dran mit einer Baumstruktur sein, die geteilt wird, basierend auf den Buchstaben in den Wörtern in der Liste.

jedoch an diesem Punkt, Sie sind neu zu erstellen wirklich genau das, was SQL Server (im Fall von Indizes) tut, und das wäre nur eine Verdoppelung des Aufwand auf Ihrer Seite sein.

Answer 4

Ich wette, Sie haben einen Index für die Spalte, so SQL Server kann den Vergleich in O (log (n)) -Operationen statt O (n).Um das Verhalten des SQL-Servers zu imitieren, verwenden Sie eine sortierte Auflistung und suchen Sie alle Zeichenfolgen s, so dass s> = Abfrage und dann auf Werte, bis Sie einen Wert finden, der nicht mit s beginnt und dann einen zusätzlichen Filter für die Werte. Dies ist eine Bereichsüberprüfung (Oracle) oder eine Indexsuche (SQL Server).

Dies ist ein Beispiel Code, der sehr wahrscheinlich in Endlosschleifen geht oder einmalige Fehler hat, weil ich es nicht getestet habe, aber Sie sollten die Idee bekommen.

// Note, list must be sorted before being passed to this function 
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) { 
    int low = 0, high = list.Count - 1; 
    while (high > low) { 
     int mid = (low + high)/2; 
     if (list[mid] < query) 
      low = mid + 1; 
     else 
      high = mid - 1; 
    } 

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length) 
     yield return list[low]; 
     low++; 
    } 
} 

Answer 5

Wenn Sie versuchen, eine Liste von Strings mit einem bestimmten Präfix zu optimieren aufzublicken Sie vielleicht einen Blick auf der Umsetzung eines Trie (nicht zu verwechseln mit einer regelmäßigen tree) Datenstruktur in C# zu nehmen.

Tries bieten sehr schnelle Präfix-Lookups und haben einen sehr geringen Speicher-Overhead im Vergleich zu anderen Datenstrukturen für diese Art von Operation.

Über LINQ zu Objekten im Allgemeinen. Es ist nicht ungewöhnlich, eine Geschwindigkeitsreduzierung im Vergleich zu SQL zu haben. Das Netz ist littered with articles, das seine Leistung analysiert.

Answer 6

Ich denke, das Problem ist, dass Linq keine Möglichkeit hat, die Tatsache zu verwenden, dass Ihre Sequenz bereits sortiert ist. Insbesondere kann es nicht wissen, dass die Anwendung der StartsWith Funktion die Bestellung beibehält.

ich die List.BinarySearch Methode zusammen mit einem IComparer<string> verwenden würde vorschlagen, dass nur Vergleich der ersten Abfrage Zeichen tut (dies schwierig sein könnte, da nicht klar ist, ob der Query-String immer der erste oder der zweite Parameter sein wird, ()).

Sie könnten sogar den Standard-String-Vergleich verwenden, da BinarySearch eine negative Zahl zurückgibt, die Sie ergänzen können (mit ~), um den Index des ersten Elements zu erhalten, das größer als Ihre Abfrage ist.

Sie müssen dann von dem zurückgegebenen Index (in beide Richtungen!) Starten, um alle Elemente zu finden, die Ihrer Abfragezeichenfolge entsprechen.