LINQ Performance pour les Grandes Collections

Dans votre code actuel, vous ne faites pas usage de l'une des caractéristiques particulières de l' Dictionary /SortedDictionary /HashSet collections, vous utilisez la même manière que vous utiliseriez un List. C'est pourquoi vous ne verrez pas de différence dans la performance.

Si vous utilisez un dictionnaire, index, où les premiers caractères de la chaîne est la clé et une liste de chaînes de valeur, vous pouvez à partir de la chaîne de recherche choisir une petite partie de l'ensemble de la collection de chaînes de caractères qui a des correspondances possibles.

J'ai écrit la catégorie ci-dessous pour tester cela. Si je le remplir avec un million de cordes et de recherche avec une chaîne de huit caractères, il déchire toutes les correspondances possibles dans environ 3 ms. Recherche une chaîne de caractères est le pire des cas, mais il trouve les 1000 premiers matches sur 4 mme. Trouver tous les matches pour une seule des chaînes de caractères prend environ 25 ms.

La classe crée des index pour 1, 2, 4 et 8 touches de caractères. Si vous regardez vos données et ce que vous recherchez, vous devriez être en mesure de sélectionner quels de créer des index pour optimiser vos conditions.

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

Si vous êtes en train de faire une "commence par", vous ne se soucient ordinale des comparaisons, et vous pouvez avoir la collection triée (encore une fois dans l'ordinal de l'ordre), alors je vous suggère d'avoir les valeurs dans une liste. Vous pouvez ensuite binaire de recherche pour trouver la première valeur qui commence avec le bon préfixe, puis allez en bas de la liste de façon linéaire donne des résultats jusqu'à ce que la première valeur qui n'est pas commencer avec le bon préfixe.

En fait, vous pourriez probablement faire une autre recherche binaire pour la première valeur qui ne commence pas par le préfixe, alors vous pourriez avoir un début et une fin. Ensuite, vous avez juste besoin d'appliquer la longueur critère pour que la partie correspondante. (J'espère que si il est judicieux de données, la mise en correspondance de préfixe va se débarrasser de la plupart des candidats de valeurs.) Le chemin pour trouver la première valeur qui ne commence pas par le préfixe est à la recherche de la lexicographiquement-première valeur qui n'est pas - par exemple avec un préfixe "ABC", recherche pour "ABD".

Rien de tout cela utilise LINQ, et c'est très spécifique à votre cas particulier, mais il devrait fonctionner. Laissez-moi savoir si ce n'est pas logique.

Simplement en regardant ton code, je dirais que vous devez réorganiser la comparaison de prendre avantage de court-circuit lors de l'utilisation d'opérateurs booléens:

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

La comparaison de la longueur est toujours va être un O(1) opération (comme la longueur est stockée comme une partie de la chaîne, il ne compte pas chaque personnage à chaque fois), alors que l'appel à StartsWith va être un O(N), où N est la longueur de la requête (ou de la longueur de la chaîne, selon le moindre des deux).

En plaçant la comparaison de la longueur avant l'appel à StartsWith, si la comparaison échoue, vous vous sauver de quelques cycles supplémentaires qui pourraient ajouter jusqu'à lors du traitement d'un grand nombre d'éléments.

Je ne pense pas qu'une table de recherche va vous aider ici, comme les tables de recherche sont bons quand vous comparez l'ensemble des clés, et non pas les parties de la clé, comme vous le faites avec l'appel à StartsWith.

Plutôt, vous pourriez être mieux à l'aide d'une structure de l'arbre qui est coupé basé sur les lettres dans les mots de la liste.

Toutefois, à ce stade, vous êtes vraiment juste recréer ce que SQL Server est en train de faire (dans le cas de l'index) et qui serait juste une duplication d'effort de votre part.