Prestazioni LINQ per grandi collezioni

Question

Ho una vasta raccolta di stringhe (fino a 1M) ordinate alfabeticamente. Ho sperimentato query LINQ contro questa raccolta utilizzando HashSet, SortedDictionary e Dictionary. Sto memorizzando nella cache statica la raccolta, ha una dimensione massima di 50 MB e sto sempre chiamando la query LINQ contro la raccolta memorizzata nella cache. Il mio problema è il seguente:

Indipendentemente dal tipo di raccolta, le prestazioni sono molto più scarse di SQL (fino a 200 ms). Quando si esegue una query simile rispetto alle tabelle SQL sottostanti, le prestazioni sono molto più veloci (5-10 ms). Ho implementato le mie query LINQ come segue:

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

E 'la mia comprensione che la HashSet, dizionario, ecc implementare le ricerche utilizzando la ricerca binaria albero invece che l'enumerazione standard. Quali sono le opzioni per le query LINQ ad alte prestazioni nei tipi di raccolta avanzati?

Answer 1

Nel codice attuale non si fanno uso di una qualsiasi delle particolarità delle Dictionary/SortedDictionary/HashSet collezioni, si utilizza allo stesso modo che si usa un List. Questo è il motivo per cui non vedi alcuna differenza nelle prestazioni.

Se si utilizza un dizionario come indice in cui i primi caratteri della stringa sono la chiave e un elenco di stringhe è il valore, dalla stringa di ricerca è possibile selezionare una piccola parte dell'intera raccolta di stringhe che ha possibili partite.

Ho scritto la classe qui sotto per testare questo. Se lo compilo con un milione di stringhe e cerco con una stringa di otto caratteri, esso strappa tutte le possibili corrispondenze in circa 3 ms. La ricerca con una stringa di un carattere è il caso peggiore, ma trova le prime 1000 partite in circa 4 ms. La ricerca di tutte le corrispondenze per una stringa di un carattere richiede circa 25 ms.

La classe crea indici per chiavi di 1, 2, 4 e 8 caratteri. Se guardi i tuoi dati specifici e ciò che cerchi, dovresti essere in grado di selezionare quali indici creare per ottimizzarli per le tue condizioni.

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

Se si sta eseguendo un "inizia con", ci si preoccupa solo dei confronti ordinali e si può ordinare la raccolta (sempre in ordine ordinale), quindi suggerirei di avere i valori in una lista. È quindi possibile eseguire una ricerca binaria per trovare il primo valore che inizia con il prefisso destro, quindi scendere lungo la lista producendo risultati lineari fino al primo valore che non inizia con il prefisso destro.

In effetti, si potrebbe probabilmente fare un'altra ricerca binaria per il primo valore che non inizia con il prefisso, quindi si dovrebbe avere un inizio e un punto finale. Quindi è sufficiente applicare il criterio di lunghezza a quella porzione corrispondente. (Mi auguro che se si tratta di dati sensibili, la corrispondenza del prefisso eliminerà la maggior parte dei valori candidati.) Il modo per trovare il primo valore che non inizia con il prefisso è cercare il valore lessicograficamente primo che non - es con un prefisso "ABC", cerca "ABD".

Nessuno di questi utilizza LINQ ed è tutto molto specifico per il caso specifico, ma dovrebbe funzionare. Fammi sapere se tutto ciò non ha senso.

Answer 3

Basta guardare il codice, direi che si dovrebbe riordinare il confronto di approfittare di corto circuito quando si utilizzano gli operatori booleani:

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

Il confronto di lunghezza sta andando sempre essere un O (1) operazione (dato che la lunghezza viene memorizzata come parte della stringa, non conta ogni carattere ogni volta), mentre la chiamata a StartsWith sta per essere un'operazione O (N), dove N è la lunghezza della query (o la lunghezza della stringa, a seconda di quale sia la più piccola).

Inserendo il confronto della lunghezza prima della chiamata su StartsWith, se il confronto fallisce, è possibile risparmiare alcuni cicli aggiuntivi che potrebbero essere aggiunti durante l'elaborazione di un numero elevato di elementi.

Non credo che una tabella di ricerca possa aiutarti in questo modo, poiché le tabelle di ricerca sono valide quando si confronta l'intera chiave, non parti della chiave, come si fa con la chiamata a StartsWith.

Piuttosto, potrebbe essere meglio utilizzare una struttura ad albero che viene suddivisa in base alle lettere nelle parole nell'elenco.

Tuttavia, a quel punto, si sta davvero ricreando ciò che sta facendo SQL Server (nel caso degli indici) e sarebbe solo una duplicazione degli sforzi da parte dell'utente.

Answer 4

Scommetto che hai un indice sulla colonna in modo che il server SQL possa eseguire il confronto in operazioni O (log (n)) anziché O (n).Per imitare il comportamento del server SQL, utilizzare una raccolta ordinata e trovare tutte le stringhe s tali che s> = query e quindi osservare i valori finché non si trova un valore che non inizia con s e quindi esegue un filtro aggiuntivo sui valori. Questo è ciò che viene chiamato un intervallo di scansione (Oracle) o un indice di ricerca (server SQL).

Questo è un codice di esempio che è molto probabile che entri in loop infiniti o abbia errori una tantum perché non l'ho provato, ma dovresti ottenere l'idea.

// 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

Se si sta cercando di ottimizzare la ricerca di una lista di stringhe con un determinato prefisso si potrebbe desiderare di dare un'occhiata a implementare un Trie (da non confondere con un normale tree) struttura dati in C#.

Tries offre ricerche di prefissi molto veloci e un sovraccarico di memoria molto ridotto rispetto ad altre strutture di dati per questo tipo di operazione.

Informazioni su LINQ su Oggetti in generale. Non è insolito avere una riduzione della velocità rispetto a SQL. La rete è littered with articles analizzando le sue prestazioni.

Answer 6

Penso che il problema sia che Linq non ha modo di usare il fatto che la sequenza è già stata ordinata. Soprattutto non può sapere, che applicando la funzione StartsWith mantiene l'ordine.

Vorrei suggerire di utilizzare il metodo List.BinarySearch insieme a un IComparer<string> che esegue solo il confronto dei primi caratteri di query (potrebbe essere difficile, poiché non è chiaro, se la stringa di query sarà sempre il primo o il secondo parametro per ()).

Si potrebbe anche utilizzare il confronto di stringhe standard, poiché BinarySearch restituisce un numero negativo che è possibile integrare (utilizzando ~) per ottenere l'indice del primo elemento che è più grande della query.

Devi quindi iniziare dall'indice restituito (in entrambe le direzioni!) Per trovare tutti gli elementi corrispondenti alla stringa di query.