Discussion :

[tevious]

onjour,

J'ai réalisé un logiciel en C# et Sqlite pour m'aider au jeu "4 images et 1 mot", et ça fonctionne plutôt pas mal.

Afin de pouvoir partager mon outil et avoir quelque chose de multiplateforme j'ai décidé d'en faire une version web et tout coder en php avec Mysql.

Le principe est simple, j'ai créé une table contenant plus de 700 000 mots de la langue française (elle contient les variantes, verbes et adjectifs quand c'est le cas pour chaque mot de base rassurez vous!), qui est constituée du mot, de sa taille et de sa signature: une colonne pour chaque caractère (donc 26) + une pour les jokers (j'inclus les espaces, tirets et apostrophes etc.). et pour chaque colonne je renseigne le nombre de fois où le caractère apparait dans le mot... exemple: coco -> a = 0, b = 0, c = 2, d = 0 [...] o = 2, [...] z = 0

Pour chaque planche du jeu 4 img et 1 mot, on a un jeu de lettres proposés et une taille de mot (plus petite que le jeu de lettres).

Je calcule donc l'ensemble des combinaisons alliant le jeu de lettre et la taille du mot (pas les permutations, c'est important pour les performances) et pour chaque combinaison je génére la signature, chaque signature étant stockée j'ai ensuite un beau tableau... et donc

il suffit de faire avec sql un sélect pour chaque signature de combinaison avec en clé supplémentaire la taille du mot, et de récupérer les mots qui correspondent, et cela avec l'ensemble des combinaisons pour avoir le mot qu'on doit trouver dedans (ensuite c'est l'humain qui a l'aide des images indices fait le tri).

ça marche bien, par contre j'ai un facteur 10 niveau performance entre mon appli C# (la plus rapide) et mon appli Php, et j'aimerais savoir comment optimiser ça.

pour un mot de 6 lettres dans la séquence iqnafpgdelru, il y a 924 combinaisons à tester, en C# ça me prend 2'10, en Php il m'a fallu plus de 22'.

En C# je fais continuellement des ouvertures/fermeture de la base (un fichier Sqlite pour rappel... je pense pas que ce soit aussi performant qu'un sgbd) pour chaque combinaison, en Php avec Mysql j'utilise les requêtes préparées et je déclare un seul objet PDO que j'utilise du début à la fin, et malgré ça les résultats sont une catastrophe...

Une idée?

Code de ma fonction de recherche de mots:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public static function fetchWords2($signs,$size) // $signs est un 2dim tableau, chaque élément est un tableau qui a la signature d'un mot, $size est un int
    {
 
       // query de la requête préparée
        $reqselsign = "select * from word where length=? and a=? and b=? and c=? and d=? and e=? and f=? and g=? and h=? and i=? and j=? and ";
        $reqselsign .= "k=? and l=? and m=? and n=? and o=? and p=? and q=? and r=? and s=? and t=? and u=? and v=? and w=? and x=? and y=? and   z=?;";
 
 
        if(!isset($size) or $size <2 or !isset($signs))
            return array();
 
        try
        {
            $db = new PDO(self::$connectionstring, self::$username, self::$pwd);
        }
        catch(Exception $e)
        {
            die('DB error, stop! : '.$e->getMessage());
        }
 
        $wordslist = array(); // notre tableau de liste des mots à retourner à la fin
        $req = $db->prepare($reqselsign);
 
 
 
 
        foreach($signs as $signa) // pour chaque sous-tableau "signature d'un mot" $signa
        {
 
 
            // $param est la liste des paramètres de ma requête, sur plusieurs lignes uniquement pour plus de visibilité
 
            $param = array($size,$signa["a"],$signa["b"],$signa["c"],$signa["d"],$signa["e"],$signa["f"],$signa["g"],$signa["h"],$signa["i"],$signa["j"],$signa["k"]);
            $param = array_merge($param, array($signa["l"],$signa["m"],$signa["n"],$signa["o"],$signa["p"],$signa["q"],$signa["r"],$signa["s"],$signa["t"]));
            $param = array_merge($param, array($signa["u"],$signa["v"],$signa["w"],$signa["x"],$signa["y"],$signa["z"]));
 
 
 
            $req->execute($param);
 
            while ($data = $req->fetch())
            {
                $wordslist[] = $data["name"]; // récupérer le mot stocké dans la colonne name et l'ajouter à notre liste résultat
            }
 
            $req->closeCursor();
        }       
 
 
 
        return $wordslist;
 
 
    }

[Dendrite]

Je suppose que tu veux parler de secondes ('') plutôt que de minutes (')

N'utilise pas 'or' en PHP, juste en SQL. Sinon tu auras de très mauvaises surprises.
Essaie avec cette condition...

Code :

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

1
2
3
4
if( empty($size) ||  empty($signs) || (! empty($size) && $size <2 )){
   return false;
}
//puis ensuite tu déroules ton code, tranquille.

[tevious]

Salut,

merci, pourquoi || et pas or? J'imagine que c'est du coup aussi && à la place de and?
J'avoue qu'il y a 2 jours j'y connaissais rien en php, j'avais lu un tuto sans accrocher il y a 10 ans... puis je suis devenu ingénieur et pas le choix, j'ai appris C++, Java, C# puis Python, et là Php m'a par d'un coup très facile, mais je connais pas encore les subtilités...

Sinon je te confirme bien que c'est des minutes... et le lag vient bien de la communication avec la base de données (le code que j'ai écrit dans mon premier message), la génération des combinaisons ne prends que quelques millisecondes à côté... donc j'aimerais optimiser cette chose car je comprends pas qu'un programme utilisant SQL derrière un système de fichier puisse être plus rapide que quand il s'agit d'un Sgbd, et c'est pourtant le cas...
C# une fois compilé en bytecode est peut être plus rapide que l'interprétation brut de Php par Apache... mais 2 minutes VS 22 minutes... il doit y avoir autre chose.

[Dendrite]

Teste d'abord, je t'expliquerai après, si ça fonctionne.
Sinon, il faut absolument poser des indexes dans ta table sur les 26 lettres.
Aussi, évite le * dans une requête SQL quand tu fais tourner ta méthode dans une boucle. Mets directement tous les champs qui t'intéressent.
Sinon, tu vas convoquer une méta requête (pour aller chercher tous tes champs justement) totalement inutile à chaque tour.
Et enfin un dernier conseil...
filtre dans l'ordre du plus rare au plus fréquent des fréquences de lettres
Z, W, K, Y etc.... avec A, U, O, I, E en dernier...
Ca devrait rendre les performances meilleures, et pas qu'un peu.

[Dendrite]

Je vais être honnête, je ne comprends pas bien ce que tu mets à la place de tes marqueurs à l'arrivée, et le concept de "signature" du mot.
Soyons concret

Code SQL :

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

select * from word where length=? and z=? and y=? and k=? and w=? /*etc*/

Pourrais-tu me donner une exemple de par quoi tu remplaces tes points d'interrogation, quand la lettre est présente, quand la lettre est absente ?

Edit : est-ce que fondamentalement, on part un peu du même principe que le jeu du pendu ?

[Dendrite]

Bon, je me réponds toute seule, je suis allée voir, oui, c'est fondamentalement le même principe que le jeu du pendu.

Je ne vois pas à quoi sert ta table abcdef...

Je ferais le traitement en PHP.
En mettant en session les lettres déjà trouvées pendant la session du joueur. C'est peut-être la notion qui te manque dans le langage PHP, et qui est indispensable.
session = variable qui ne doit pas disparaître à chaque rafraîchissement de page, mais ne doit pas non plus forcément persister au point d'être stocké en base...

Voici les grandes lignes de l'algo que je te propose, et qui devrait offrir une excellente performance.

D'abord côté SQL, tu n'aurais que 3 tables :

vocabulaire (id, mot) unicité mot, 700 000 tuples si j'ai bien compris
joueur(id, login, mdp) unicité login,
jeu(id, joueur_id, vocabulaire_id, score) unicité du couple joueur_id + vocabulaire_id

Ensuite en PHP

1) mettre en session l'id du joueur $_SESSION['joueur_id'],
le mot choisi aléatoirement dans ta table n_vocabulaire $_SESSION['cible'] (prenons 'callipyge'), et qui n'est pas déjà dans ta table jeu pour ce joueur,

Enfin, une dernière variable de session qui déterminera ton algo pendant le déroulement du jeu.

Code :

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

$_SESSION['tentatives']=array();

Mettons que le joueur ait droit à 10 tentatives maxi
et qu'à la première, il te propose "L"

Code :

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

$_SESSION['tentatives'][]= array ('mot'=> NULL, 'lettre' => 'L', 'nb' => 2);

Mettons qu'il soit très fort, et que dès la deuxième tentative, il saisisse le bon mot !

Code :

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

1
2
 
$_SESSION['tentatives'][]=array ('mot'=> 'CALLIPYGE', 'lettre' => NULL, 'nb' => 9);

Quand il a gagné, tu saisis dans ta table jeu les 3 données qui t'intéressent, le score final étant count($_SESSION['tentatives']) puis tu réinitialises toutes tes variables de session.

Voilà, la suite, tu connais, des histoires de connexion à la base, de boucles et de conditions.

Sinon

j'ai créé une table contenant plus de 700 000 mots de la langue française

Tu as obtenu ça gratuitement ? Je rêve d'avoir ça...

[Celira]

@Dendrite : je crois que le but n'est pas de faire le jeu, mais plutôt un site d'assistance pour le jeu, une sorte de dictionnaire. On entre les lettres disponibles et la liste ressort les mots correspondants, ce qui permet à la personne en train de jouer au jeu d'avoir un coup de pouce (ya plus qu'à trouver le bon mot dans la liste)

Donc le but de l'opération est de trouver dans la base tous les mots de la longueur souhaitée et qui contiennent des lettres de la liste, pas nécessairement toutes, mais uniquement des lettres de la liste dans la quantité de la liste.
Genre avec "iqnafpgdelru" et 4 lettres, tu dois trouver "page" et "lire", mais pas "toto" ou "papa".

[tevious]

Salut,

Merci pour tes réponses!

Alors j'ai été voir sur php.net pour la différence de or et ||, effectivement c'est subtil (et sacrément casse gueule!).
Pour les sessions, je connais le principe et je compte les utiliser pour autre chose, mais je pense que je n'ai pas bien expliqué mon idée.
Mon idée n'est pas de résoudre le mot car c'est impossible avec cette méthode, trop de mots matchent avec les différentes combinaisons à partir du moment où: taille du jeu de lettres > taille du mot, mais de donner une liste de mots (où la solution est forcément incluse) où à partir des images d'indices on retrouvera la solution... et ça marche plutôt pas mal au final pour moi

Mon principe de signatures c'est donc d'avoir le minimum de combinaisons de lettres à tester, pour ça j'ai ma base de signature du dictionnaires, et à partir du jeu de lettre, je n'ai qu'à tester les combinaisons et pas toutes les permutations sous jacentes, ce qui diminue grandement la complexité:



Pour illustrer, si je prend le jeu cacaop (oui je cherche cacao) et cherche un mot de 5 lettres, j'ai 720 permutations possibles (ce qui revient à faire une combinaison sur la colonne name sans utiliser les signatures), et seulement 5 combinaisons possibles...
Donc l'idée est là, je cherche les différentes combinaisons et ensuite j'interroge mon dictionnaire en injectant la signature de chaque combinaison, et je m'évite ainsi 715 requêtes dans ce cas là... ça fait un "gros" boulot pour générer la base de signatures (120 mo le sql) mais on le fait qu'une fois, à comparer avec le temps de calcul si on a pas les signatures et si on doit se taper toutes les combinaisons.

Pour la suite, ma requête est effectivement faite à l'arrache, je devrais commencer par ne selecter qu'une colonne, en l'occurence le name, c'est une super idée là
Pour les indexes, je ne m'en suis jamais soucis avant vue que j'ai pas une formation d'informaticien à la base je n'ai pas appris le SQL à l'école et c'était mes collègues qui structuraient les tables... j'ai cru comprendre que ça optimiser les requêtes, au prix de la taille de la base, mais sur 26 colonnes, ça ne risque pas de montrer ses limites?
Sinon comment je peux les implanter concrètement (sur la base déjà existante si possible sinon je la drop et je régénère le sql du dico avec les requêtes pour les indexes)) avec quoi comme requête SQL?

Merci

Si je peux faire plaisir, voilà le dico (naturellement j'ai retraité le fichier et j'ai fait ma sauce derrière avec mysql...), et oui il est gratuit
http://infolingu.univ-mlv.fr/Donnees...hargement.html

[Dendrite]

Coucou,

@celira : merci, je n'avais pas compris.

@tevious : Merciiiiiiiiiiiiiiiiiiiii pour le cadeau. Je vais jouer avec ça tout de suite !

Bon, oui, il te faut poser des indexes, et oui, c'est archi-rentable, et oui, c'est très simple. si tu as PHPmyadmin

tu cliques sur ta table / structure / tu cliques sur index pour chaque champ que tu veux indexer...

[tevious]

De rien

Merci pour les infos, j'ai finalement réussi mon optimisation... j'ai fait 2 indexes (mysql limite chaque index à 16 colonnes max... donc il m'en a fallu 2 pour tout l'alphabet), par contre j'ai joué sur une subtilité, je n'ai pas fait par ordre alphabétique, mais par fréquence d'apparition de chaque lettres, on a donc un index de 16 et un de 10, je ne sais pas si c'est judicieux, en tout ça marche.

Je suis passé de 22 minutes, à... 3 secondes, j'ai eu du mal à y croire, pour le coup je suis en train de regarder la théorie derrière ces indexes avec B-tree et compagnie, c'est encore l'occasion d'apprendre quelque chose

Merci pour ton aide!

[Dendrite]

You're welcome.

Je t'explique le pourquoi / comment des 2 choses de façon vulgarisée, du moins ce que je crois en comprendre :

1 - les indexes sont essentiels, absolument incontournables si tu as beaucoup de données.
Imagine que tu as une table de 700 000 données avec mettons le champ "couleur_preferee" avec seulement 20 données différentes... Quand tu indexes, il stocke dans une clé les 20 données différentes, dans l'autre sens que la table. Ex => orange : 258, 15 812, 97 531, 659 000 etc... les chiffres représentant les id des tuples qui, à la colonne 'couleur', ont pour valeur 'orange'. Exactement comme dans un bouquin technique, tu as un index à la fin du bouquin, qui te met un mot clé et la liste des pages qui possèdent ce mot clé.
Du coup, quand tu fais une requête avec le filtre "couleur_preferee" = "orange", il ne tape que dans l'index au lieu d'aller explorer tes 700 000 tuples !

2 - pourquoi c'est important de filtrer D'ABORD sur les trucs les plus restreints, et ensuite sur les trucs les plus fréquents, et surtout pas dans l'autre sens.
On est d'accord que le premier mouvement d'un humain est plutôt l'inverse, on dira : les femmes qui aiment l'orange, et pas les gens qui aiment l'orange et qui se trouvent être des femmes.
Comme souvent, la modélisation en db se fichent de l'intuitivité humaine.

On reprend tes indexes. Tu as un index genre (H,F) et tu as un index couleur_preferee.
On imagine pour simplifier, que les 20 couleurs sont uniformément réparties dans la population.

Tu cherches les filles qui aiment le orange.

si tu dis "cherche tous les id des filles de l'index genre, puis, parmi eux, tous les id des couleurs orange"... Ca va te faire à peu près 350 000 id suivis de 17 500 id . Soit (au maximum)... 6 milliards de tests !!!

Si tu dis "cherche tous les id des gens qui aiment le orange, puis parmi eux, tous les id des filles", ça va te faire à peu près 17 000 id suivis de... 8500, soit (au maximum) moins de 150 millions de tests.

Un monde de différences en matière d'optimisation SQL... qui effectivement peut passer de 20' à 3''.

J'espère que j'ai été claire sur l'intérêt de ces 2 points.

PS : pour l'instant, en important ton fichier zip du lexique français, je ne suis pas parvenue à récupérer, fichier trop gros, techno mysql.
edit du PS : mon mari me souffle qu'il faut le faire en ligne de commande... que ce sera beaucoup plus performant. Et je me souviens qu'il a raison !

[grunk]

Notez au passage qu'il était tout à fait possible de rester en sqlite sous PHP (et donc utiliser la même base qu'en C#) et que la problématique des index est identique .
Mysql est toutefois bien meilleur si il y'a risque d'accès concurrent.

[tevious]

@grunk: Effectivement, je vais encore m'y attaquer avec mon "client lourd" en C#, j'ai mis les pieds dans tous les plats en même temps, il y a 1 semaine je connaissais rien en php... donc pas mal de bidouillage en sql aussi (je suis automaticien, personne n'est parfait ) mais là le sujet m'intéresse donc je vais continuer. le choix de mysql c'est pour avoir une version déployée en ligne, donc oui le problème de concurrence se pose, sinon j'aurais gardé sqlite pour les deux solutions!

@Dendrite: merci, du coup il faudrait que "j'incite" mysql a utilisé l'index avec les fréquences d'apparition les moins fortes? Je croix savoir qu'on peut le forcer à utiliser un index ou l'autre, mais je sais pas si on peut lui dire "essaye l'index A, puis B", de ce que j'ai compris, si on dit rien c'est l'optimiseur de requête qui décide s'il faut utiliser un index et lequel le cas échéant, sauf si on utilise un des secret hint de la doc pour le forcer à en utiliser un particulier... tu pourrais m'en dire plus?

Pour le dico, c'est un fichier.txt qui contient 1 voir 2 mots par ligne (je crois que c'est la forme plurielle si elle est "irrégulière") ou une variante du mot 1 dans tous les cas, puis ensuite plein d'infos sur le genre du mot etc...
J'ai retravaillé le fichier avec C# en plusieurs passes pour ne garder que les mots et en avoir un par ligne, puis ensuite pour l'utiliser dans une base de données, j'ai chargé les 700 000+ mots dans une List<string> puis j'ai générer un fichier .sql avec des insert pour chaque mot en itérant la liste... le fichier fait 120 mo... en local j'ai trafiqué php.ini pour que ça passe (le fichier .sql dans mon cas fait 120 mo) en virant le timeout et la limite de taille de fichier dans phpmyadmin... sur le site web j'ai fait un fichier .sql par lettre de l'alphabet et pour ne pas dépasser la limite de 10 mo de phpmyadmin, quand j’atteignais 50 000 enregistrements pour une lettre je créais un fichier bis pour la lettre en question. ça a pris du temps pour passer tous les fichiers mais ça marche!

Pour la petite histoire, à la base j'avais pas eu l'idée des signatures et je n'utilisais même pas de bdd, je faisais toutes les permutations possibles et je les comparais en mot à mot avec mon vecteur de tous les mots (j'ai commencé le programme en C++, et j'ai switché vers C# quand j'ai décidé d'utiliser Sqlite car le driver est mieux foutu avec ce dernier)) , sauf que c'était tellement volumineux que mon std::vector<string> dicofrance a fini par faire planter mon programme... je savais pas que la lib standard pouvait faire ça dans une utilisation "normale", en C# jamais eu de problèmes...