Le moyen le plus rapide de trouver des objets d'une collection correspondant à une condition sur un membre de chaîne

Question

Supposons que je dispose d'une collection (que ce soit un tableau, une liste générique ou quelle que soit la solution la plus rapide à ce problème) d'une certaine classe, appelons-la ClassFoo . :

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
} 

Supposons qu'il y aura environ 50 000 articles dans la collection, tous en mémoire. Maintenant, je souhaite obtenir le plus rapidement possible toutes les instances de la collection qui obéissent à une condition de son membre, par exemple:

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

Comment puis-je obtenir les résultats aussi rapidement que possible? Devrais-je envisager des techniques d'indexation et des infrastructures de données avancées?

Le domaine d'application de ce problème est un autocompléteur, qui obtient une requête et fournit un ensemble de suggestions. Supposons que la condition ne soit pas plus complexe que cela. Supposons également qu'il y aura beaucoup de recherches.

Answer 1

Avec la contrainte que la clause de condition peut être "tout", vous êtes limité à l'analyse de la liste complète et à l'application de la condition.

S'il existe des limitations sur la clause de condition, vous pouvez alors organiser les données pour gérer plus efficacement les requêtes.

Par exemple, l'exemple de code avec le "byFirstLetter" Le dictionnaire n’aide pas du tout avec un " endsWith " requête.

Cela revient donc vraiment aux requêtes que vous souhaitez effectuer sur ces données.

Dans Bases de données, ce problème est la charge de l’optimiseur de requêtes. Dans une base de données classique, si vous avez une base de données sans index, chaque requête sera évidemment une analyse de table. Lorsque vous ajoutez des index à la table, l'optimiseur peut utiliser ces données pour élaborer des plans de requête plus sophistiqués afin de mieux accéder aux données. C’est essentiellement le problème que vous décrivez.

Une fois que vous avez un sous-ensemble plus concret des types de requêtes, vous pouvez alors prendre une meilleure décision quant à la meilleure structure. En outre, vous devez tenir compte de la quantité de données. Si vous avez une liste de 10 éléments de moins de 100 octets chacun, une analyse de tout pourrait bien être la chose la plus rapide que vous puissiez faire puisque vous avez une si petite quantité de données. Évidemment, cela ne correspond pas à un 1M d’éléments, mais même des techniques d’accès intelligentes entraînent des coûts de configuration, de maintenance (comme la maintenance d’index) et de mémoire.

MODIFIER , en fonction du commentaire

S'il s'agit d'un compléteur automatique, si les données sont statiques, triez-les et utilisez une recherche binaire. Vous n'allez vraiment pas aller plus vite que ça.

Si les données sont dynamiques, stockez-les dans une arborescence équilibrée et effectuez une recherche. C'est effectivement une recherche binaire, et cela vous permet de continuer à ajouter les données de manière aléatoire.

Quelque chose d'autre est une spécialisation sur ces concepts.

Answer 2

var Answers = myList.Where (item = > item.bar.StartsWith (requête) || item.bar.EndsWith (query));

c'est le plus facile à mon avis, devrait être exécuté assez rapidement.

Answer 3

Je ne suis pas sûr de comprendre ... Tout ce que vous pouvez vraiment faire est d’optimiser la règle, c’est la partie qui doit être la plus rapide. Vous ne pouvez pas accélérer la boucle sans simplement lancer plus de matériel.

Vous pouvez paralléliser si vous avez plusieurs cœurs ou machines.

Answer 4

Je ne suis pas sur Java pour le moment, mais je penserais aux choses suivantes.

Comment créez-vous votre liste? Vous pouvez peut-être le créer déjà commandé de manière à réduire le temps de comparaison.

Si vous ne faites qu'une boucle directe dans votre collection, vous ne verrez pas beaucoup de différence entre le stocker sous forme de tableau ou sous forme de liste chaînée.

Pour stocker les résultats, selon la manière dont vous les collectez, la structure peut faire la différence (mais si les structures génériques de Java sont intelligentes, elles ne le feront pas). Comme je le disais, je ne connais pas Java, mais je suppose que la liste générique liée garderait un pointeur de queue. Dans ce cas, cela ne ferait pas vraiment une différence. Quelqu'un ayant une meilleure connaissance de l'implémentation du tableau sous-jacent par rapport à la liste chaînée et de la manière dont il finit par chercher dans le code d'octet pourrait probablement vous dire si l'ajout à une liste chaînée avec un pointeur de queue ou son insertion dans un tableau est plus rapide (je suppose que ce serait le tableau ). Par ailleurs, vous devez connaître la taille de votre jeu de résultats ou sacrifier de l’espace de stockage et le rendre aussi grand que l’ensemble de la collection que vous parcourez si vous souhaitez utiliser un tableau.

Optimiser votre requête de comparaison en déterminant quelle est la comparaison la plus susceptible d'être vraie et le faire en premier pourrait également aider. Par exemple, si généralement 10% du temps d’un membre de la collection commence par votre requête et 30% du temps qu’un membre se termine avec une requête, vous voudrez d’abord effectuer la comparaison finale.

Answer 5

Pour votre exemple particulier, le tri de la collection vous aiderait, car vous pouvez binarychop pour le premier élément commençant par query et se terminer plus tôt lorsque vous atteignez le prochain élément non; vous pouvez également créer une table de pointeurs sur les éléments de la collection, triée à l’inverse de chaque chaîne pour la deuxième clause.

En général, si vous connaissez la structure de la requête à l'avance, vous pouvez trier votre collection (ou créer plusieurs index triés pour votre collection s'il y a plusieurs clauses) de manière appropriée. Si vous ne le faites pas, vous ne pourrez pas faire mieux que la recherche linéaire.

Answer 6

Si vous remplissez la liste une fois, puis effectuez de nombreuses recherches (des milliers ou plus), vous pouvez créer une sorte de dictionnaire de recherche qui mappe les points de départ avec / se terminant avec les valeurs réelles. Ce serait une recherche rapide, mais utiliserait beaucoup plus de mémoire. Si vous ne faites pas beaucoup de recherches ou si vous savez que vous allez repeupler la liste au moins une fois fréquemment, j'irais avec la requête LINQ suggérée par CQ.

Answer 7

Vous pouvez créer une sorte d'index et il pourrait être plus rapide.

Nous pouvons construire un index comme celui-ci:

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

Ensuite, utilisez le comme ceci:

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

Maintenant, nous n’avons peut-être pas besoin de parcourir autant de ClassFoo que dans votre exemple, mais nous devons maintenir l’index à jour. Il n'y a aucune garantie que ce soit plus rapide, mais c'est certainement plus compliqué.

Answer 8

Dépend. Est-ce que tous vos objets vont toujours être chargés en mémoire? Avez-vous une limite finie d'objets pouvant être chargés? Vos requêtes devront-elles prendre en compte des objets qui n'ont pas encore été chargés?

Si la collection s'agrandit, j'utiliserais certainement un index.

En fait, si la collection peut atteindre une taille arbitraire et que vous n'êtes pas sûr de pouvoir tout mettre en mémoire, recherchez un ORM, une base de données en mémoire ou une autre base de données intégrée. base de données. On pense à XPO de DevExpress for ORM ou SQLite.Net pour les bases de données en mémoire.

Si vous ne voulez pas aller aussi loin, créez un index simple composé du "bar". les références de membre mappant les références de classe.

Answer 9

Si l'ensemble de critères possibles est fixe et petit, vous pouvez affecter un masque de bits à chaque élément de la liste. La taille du masque de bits est la taille de l'ensemble des critères. Lorsque vous créez / ajoutez un élément à la liste, vous vérifiez les critères auxquels il répond, puis définissez les bits correspondants dans le masque de bits de cet élément. Faire correspondre les éléments de la liste sera aussi simple que faire correspondre leurs masques de bits au masque de bits cible. Une méthode plus générale est le filtre Bloom.