Discussion :

[luelo2b]

Bonjour,

Je suis à la recherche d'une méthode efficace pour parcourir un texte à la recherche de terme.

Je m'explique :
J'ai un champs "Article" contenant des données de texte brut. Ce champs n'a pas de taille limite.
J'ai de l'autre coté une liste de terme (environ 10 000 eléments), stockée en base de donnée.

Description de mon entité

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
class MyEntity {
  string terme;
  string description;
  string plop;
}

Pour l'instant je récupère une liste d'entité List<MyEntity>.

1)Il faudrait que je travaille non pas avec la liste d'entité mais plutot avec la liste des termes. Comment convertir donc ma List<MyEntity> en List<string> ? Une solution pourrait être de faire que ma couche de donnée me retourne directement une List<string> mais je veux savoir s'il n'y a pas une autre méthode.

2)Quel est la meilleur méthode (en terme de performance) me permettant de trouver dans mon champs "Article" les occurences de ma liste des termes ?

Merci de vos pistes.

[luelo2b]

J'ai posé la question trop vite.
Pour le point 1 la solution suivante me parait être pas mal :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
List<String> listFields = entities.ConvertAll<string>(delegate(MyEntity entity) {
        return entity.terme;
      });

Par contre, j'accepte toujours un coup de main pour le point 2

[Graffito]

2)Quel est la meilleur méthode (en terme de performance) me permettant de trouver dans mon champs "Article" les occurences de ma liste des termes ?

Cela dépend de la taille respective de la liste de termes et du texte :

1. Combien de termes dans la liste ?
2. Combien de mots dans le texte ?
3. Combien de textes sont traités consécutivement avec la même liste de termes.

Dans tous les cas, pour des traitement qui durent plus 30 secondes, on pourra découper le travail en blocs et lancer autant de threads que de cores !

[olibara]

Combien de termes dans la liste ?

Il a dit +/- 10000

Combien de mots dans le texte ?

Il a dit indéterminé

A priori il faut voir ce que dure la constitution d'un Hashset sur la liste de terme

Mais je dirais qu'en terme de performance le plus rapide serait
- Constituer un Hashset sur les termes
- Lire le texte en phrase ou par bloc
- Spliter les blocs en mots tester chaque mots sur le Hasaset
- Tu peux rafiner en constituant un tableau des longueurs des termes et verifier qu'un mot a une longueur plausible avant de tester le Hashset (elimination des articles)

[tomlev]

1)Il faudrait que je travaille non pas avec la liste d'entité mais plutot avec la liste des termes. Comment convertir donc ma List<MyEntity> en List<string> ? Une solution pourrait être de faire que ma couche de donnée me retourne directement une List<string> mais je veux savoir s'il n'y a pas une autre méthode.

Quelle version de .NET utilises-tu ?
Avec 3.5 ou plus, tu peux utiliser Linq :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

List<string> terms = entities.Select(e => e.terme).ToList();

Sinon la méthode que tu as utilisée avec ConvertAll est bien aussi, ça revient à peu près au même.

2)Quel est la meilleur méthode (en terme de performance) me permettant de trouver dans mon champs "Article" les occurences de ma liste des termes ?

Toujours avec Linq, tu peux utiliser la méthode Intersect pour obtenir l'intersection de ta liste de termes et des mots de ton texte.

Par exemple, en utilisant une expression régulière pour trouver les mots :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
var terms = entities.Select(e => e.terme);
var words = Regex.Matches(text, @"\b\w+\b").Cast<Match>().Select(m => m.Value);
var termsInText = words.Intersect(terms).ToList();

Si le texte est vraiment long, la Regex n'est probablement pas la meilleure solution. Une autre option est de faire un itérateur pour renvoyer les mots au fur et à mesure qu'ils sont lus :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static IEnumerable<string> GetWords(string text)
{
    StringBuilder currentWord = new StringBuilder();
    foreach (char c in text)
    {
        if (Char.IsLetterOrDigit(c)) // critère à affiner...
        {
            currentWord.Append(c);
        }
        else
        {
            if (currentWord.Length > 0)
            {
                yield return currentWord.ToString();
                currentWord.Clear();
            }
        }
    }
    if (currentWord.Length > 0)
        yield return currentWord.ToString();
}
 
...
 
var terms = entities.Select(e => e.terme);
var words = GetWords(text);
var termsInText = words.Intersect(terms).ToList();

[olibara]

Salut Tomlev

luelo2b est a la recherche de performances !!

J'ecarterais donc d'office le regexp

L'autre methode que tu propose je l'aurais peut etre ecrite selon ce principe en C, mais en language comme C#, je crains que ta methode GetWords soit fort gourmande.

Tu me dira qu'un split doit faire +/- la meme chose mais probablement de maniere plus optimisée dans un niveau plus bas.

Quand a l'intersect je crois sincerement que qu'un intersect sur hashset et non sur List sera beaucoup plus performant

[luelo2b]

Ok

Merci pour tout ces retours.

Ca me donne déja de bonne piste pour avancer.

Quelle version de .NET utilises-tu ?
Avec 3.5 ou plus, tu peux utiliser Linq :

Je suis en 3.5 et je peut donc utiliser Linq sans pb.

Je vais tester les différentes solutions today.
Je ferais un retour ensuite.

[luelo2b]

Petit retour par rapport au différentes pistes.

En reprécisant un peu le besoin.
Ma liste de termes contient un peu moins de 30000 éléments. (Un peu plus que prévu)
Mes articles sous forme de texte n'ont pas de taille limite mais ne devraient pas dépasser dans la pratique les 100000 caractères.

Du coup pour le point 1 :
Ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
List<String> terms = entities.ConvertAll<string>(delegate(MyEntity entity) {
  return entity.terme;
});

ou ca :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
List<string> terms = entities.Select(entity => entity.terme).ToList();

Franchement, en terme d'execution ca revient au même.

Pour le point 2 :
Le intersect est pour moi un bon compromis. Du moins ca remplit mon besoin en terme de perf. Je trouve les termes dans mon article en moins d'1ms. C'est largement au dessus de mon besoin et c'est donc parfait.

So ! Merci pour votre aide.

[tomlev]

luelo2b est a la recherche de performances !!

J'ecarterais donc d'office le regexp

Vu que la regex est très simple, je suis pas vraiment inquiet pour les performances... La raison pour laquelle je suggérais une autre solution, c'est que le Regex.Matches va générer tous les résultats en mémoire en même temps, donc si le texte est très long ça peut être gourmand en mémoire. La technique avec l'itérateur renvoie les résultats au fur et à mesure, donc c'est plus économique (et peut-être un peu plus rapide, mais pas tant que ça à mon avis)

Autre avantage de la 2e technique : si on a accès au Stream d'où est lu le texte, on peut même éviter de charger le texte entier en mémoire, en lisant le Stream au fur et à mesure...

L'autre methode que tu propose je l'aurais peut etre ecrite selon ce principe en C, mais en language comme C#, je crains que ta methode GetWords soit fort gourmande.

Qu'est-ce qui te fait dire ça ? Le traitement n'est a priori pas beaucoup plus lent qu'en C... Le compilateur JIT fait du bon boulot en général

Tu me dira qu'un split doit faire +/- la meme chose mais probablement de maniere plus optimisée dans un niveau plus bas.

Un split poserait le même problème de mémoire que je mentionnais plus haut, et je ne pense pas que ce soit plus rapide... mais il faudrait benchmarker pour en être sûr.

Quand a l'intersect je crois sincerement que qu'un intersect sur hashset et non sur List sera beaucoup plus performant

Je confirme, c'est nettement plus rapide avec un HashSet... sauf que le HashSet, il faut d'abord le créer, et ça peut prendre du temps.

Mais de toutes façon, la méthode Intersect utilise elle-même un hashset(*), donc au final ça revient au même

(*) pas la classe HashSet d'ailleurs, mais une implémentation spécifique qui utilise le même principe. Jon Skeet l'a implémenté avec un HashSet normal dans sa série Edulinq (que je vous conseille vivement de lire !)