FILTRAGE / NOM SUR LISTE 3 NIVEAUX

Version imprimable

09/07/2013, 11h36
Kikuts

FILTRAGE / NOM SUR LISTE 3 NIVEAUX

Bonjour à tous ! J'ai une question mais je ne sais où la poster :(

Car mon problème ne concerne pas un langage mais plutôt sur la partie algorithmique.

J'ai une liste d'éléments (niveau 1) où chaque élément possède un libellé et une collection d'éléments (niveau 2) où chaque élément possède un libellé et une collection d'éléments (niveau 3). Chaque niveau est de type différent.

L'utilisateur, via une page de recherche doit pouvoir saisir du texte et je dois afficher un arbre (treeview) correspondant à sa recherche.

Je ne sais pas comment m'y prendre pour avoir un algo le moins complexe et le plus optimisé possible.

Prenons un exemple, j'ai une liste de "Joueur". Chaque joueurs a une liste de "Jeu", dans chaque jeu, il y a une liste de "Personnage".

Si je recherche mario voici le genre de résultat que je dois avoir :

Kikuts > Super Mario Galaxy > Mario
Kikuts > Super smash bross > Mario
Kikuts > Mario party princesse edition (admettons ce jeu fictif où mario n'est pas dans les personnages du jeux mais uniquement dans le libellé du jeux).
MarioDu93
MarioDu94 > Super Mario Galaxy.

Vous aurez compris que je ne peux pas filtrer bêtement de niveau en niveau car par exemple, Kikuts n'a pas un nom qui contient "Mario" mais comme il a des jeux dont le nom contient mario ou alors des jeux dans lesquelles un des personnages s'appel Mario, on va l'afficher.

Merci de m'indiquer où je devrais poster ce message pour avoir le plus de réponses possible ! Merci d'avance :)

ps : malheureusement, je ne développe rien en rapport avec mario ... mais dans un ERP ... mais pour l'exemple c'était plus sympa ;)
09/07/2013, 14h08
dkmix

Bonjour,

Citation:

Vous aurez compris que je ne peux pas filtrer bêtement de niveau en niveau car par exemple, Kikuts n'a pas un nom qui contient "Mario" mais comme il a des jeux dont le nom contient mario ou alors des jeux dans lesquelles un des personnages s'appel Mario, on va l'afficher.

Je pense que dans ce cas il faut autant de recherche séparée que de niveaux.
Rien n'empêche après de lancer les trois recherche en même temps avec des Tasks Parallel

PS : Ceci dit, rien n'empêche que la méthode de recherche soit identique pour tous les niveaux, si c'est factorisable.
09/07/2013, 14h18
Kikuts

Merci pour ta réponse. Aurais tu un nom d'algo pour trier sur plusieurs niveaux sur un arbre ?

Je pense également qu'il y aura n niveau de boucle que de niveaux.

J'ai une idée d'algo mais je ne sais pas ce qu'elle vaut :/

Par exemple, je vérifie si le joueur a un nom qui contient la variable recherché. S'il n'y a pas correspondance, je vais dans une boucle.

Dans cette boucle, je vérifie chaque jeux. Si un jeu a un nom qui ne contient pas le texte recherché, je vais aller dans les personnages.

Si parmi les personnages, je n'en trouve aucun dont le nom est le texte, alors je n'afficherai pas la grappe d'objets représentant un joueur (un joueur, ses jeux et leurs perso).

(ce n'est qu'une partie)

Mais je pense que certains se sont déjà penché sur le problème et on trouvé un algo de tri performant.

Pour la recherche parallèle, dans mon cas, il faudrait que je lance plusieurs task ou chacune s'occuperait d'analyser un joueur ? Je n'ai que très rarement utiliser les task (à part dans le cadre de l'utilisation de await et async)

Encore merci pour ta lecture et ta réponse !
09/07/2013, 14h29
dkmix

Citation:

Pour la recherche parallèle, dans mon cas, il faudrait que je lance plusieurs task ou chacune s'occuperait d'analyser un joueur ?

Non pas un joueur mais un Niveau. Si j'ais bien compris la problématique, les niveaux ne sont pas liés : Un joueur peut avoir un perso Mario sans avoir un nom qui contient Mario et vice versa, un joueur peut s'appeler Mario* sans avoir de jeux ni de persos Mario. On a donc pas de relation entre les niveaux.
Il faut rechercher dans :
- tous les noms de joueur,
- tous les noms de jeux
- tous les noms de persos.

Selon les conditions (performances, BDD, autres...).
Code non testé et qui ne gère pas les null !
PS : Rien a voir avec les propositions précédentes de recherche sur 3 niveaux en utilisant des Tasks, mais cette version est peut-être suffisante dans votre cas.

Code:

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
28
29
30
31
32
33
34
 
 
    public class Jeux
    {
        public string Nom {get;set;}
        public List<Perso> Persos { get; set; }
    }
 
    public class Perso
    {
        public string Nom {get;set;}
    }
 
    public class User
    {
        public string Nom {get;set;}
        public List<Jeux> Jeux { get; set; }
    }
 
....
 
         // Main
        List<User> users = new List<User>();
        string pattern = "Mario";
        List<User> usersMatch = users.FindAll(
            //recherche dans User
            u => (u.Nom.Contains(pattern)) |
            //recherche dans Jeux
                u.Jeux.Exists(j => j.Nom.Contains(pattern) | 
                    //recherche dans Persos
                    u.Jeux.Exists(j => j.Persos.Exists(p => p.Nom.Contains(pattern)))));
        /*
         * Il faut ensuite gerer l'affichage des usersMatch
         */

09/07/2013, 16h20
Kikuts

Ok.

Citation:

Il faut rechercher dans :
- tous les noms de joueur,
- tous les noms de jeux
- tous les noms de persos.

Ce que j'ai peur, c'est de faire des recherches inutiles. Par ex, il est inutile de chercher si un joueur / un jeux contiennent mario si un des jeux a comme personnage un dénommé Mario.

Or si je balance des task sur différents niveaux, il est possible que j'analyse un niveau pour rien car un de ses sous niveaux contient le texte recherché.

Pour ton deuxième message,

Citation:

List<User> usersMatch = users.FindAll(
//recherche dans User
u => (u.Nom.Contains(pattern)) |
//recherche dans Jeux
u.Jeux.Exists(j => j.Nom.Contains(pattern) |
//recherche dans Persos
u.Jeux.Exists(j => j.Persos.Exists(p => p.Nom.Contains(pattern)))));

c'est à la base un truc dans le genre que j'avais. Mais je pensais qu'il y avait plus optimal en gérant les niveaux et parcours d'éléments à la main.

Avec cette requête je récupère bien les joueurs qui ont un nom, un jeux, un des perso contenant la recherche.

Mais elle ne retourne pas une liste épurée des personnages ne contenant pas la recherche. Ou encore, à partir d'un joueur (admettons son nom ne satisfait pas la recherche), on aura accès à tous ses jeux, du moment qu'un des jeux remplisse la condition sur le libellé égal à la recherche.

(ou alors je suis fatigué :aie:) en partant du principe que ma remarque est pertinente, pour avoir le résultat escompté, il faudra que je réitère ce traitement (ton code de contrôle sur le libellé) avec un niveau de test en moins à chaque sous niveau.

Et pas sur que ce soit le plus optimisé possible. Bien entendu, je ne recherche pas LE CODE parfait. Mais si je pouvais me payer le luxe de ne pas avoir à revenir dessus lorsque cela sera en prod et qu'un client me dis que le filtrage est lent... :mrgreen:

En tout cas, les algo de tri sur des listes contenant des listes, c'est toujours aussi -chiant- fun :D

merci encore !

Je ferrais un projet test avec des données bidons demain matin ! J'implémenterai ton algo dedans et te reconfirmerai si j'ai vu juste ou si ta solution est bonne :)
17/07/2013, 16h00
Kikuts

Bon ba en fait, ta fonction est géniale.

Je ne sais pas ce qu'il me manquait pour que ça tourne bien.

Par contre, il reste un petit problème :

Si dans un jeux, un des personnages contient le pattern, la requête retournera tous les personnages.

Si un des jeux contient le pattern, l'algo retournera tous les jeux du joueurs etc etc.

Du coup, il a fallut que j'ajoute un peu de logique à la main... :roll:
Je met le code au cas où ça sert un jour à quelqu'un !

Citation:

Dim listePreFiltree As List(Of FamilleProduitModel) = listeFPA.FindAll(Function(f) f.Libelle.ToUpper().Contains(texteRecherche) OrElse
f.ListProduit.Any(Function(p) p.Libelle.ToUpper().Contains(texteRecherche)) OrElse
f.ListProduit.Any(Function(p) p.ListArticle.Any(Function(a) a.Libelle.ToUpper().Contains(texteRecherche)))).ToList()

' Une fois les données préfiltrées, on va supprimer les éléments en bout de chaîne qui ne contiennent pas le texte recherché.

Dim listeArtSuppr As New List(Of ArticleModel)
Dim listeProdSuppr As New List(Of ProduitModel)

For Each fam As FamilleProduitModel In listePreFiltree

For Each prod As ProduitModel In fam.ListProduit

For Each art As ArticleModel In prod.ListArticle
If Not art.Libelle.ToUpper().Contains(texteRecherche) Then
listeArtSuppr.Add(art)
End If
Next

For Each element In listeArtSuppr
prod.ListArticle.Remove(element)
Next
listeArtSuppr.Clear()

If Not prod.Libelle.ToUpper().Contains(texteRecherche) AndAlso prod.ListArticle.Count = 0 Then
listeProdSuppr.Add(prod)
End If
Next

For Each element In listeProdSuppr
fam.ListProduit.Remove(element)
Next
listeProdSuppr.Clear()
Next

Return listePreFiltree