Recherche dichotomique en C dans fichier

Résolu
dodie -  
 DzarGol -
Bonjour, j'ai un petit problème en langage C... Je cherche à faire une recherche dans un fichier contenant un dictionnaire, c'et pour un programme de scrabble... Dnc j'ai besoin de faire une recherche dichotomique dans mon fichier pour savoir si le mot que j'ai a vérifier existe.
Le problème est que je ne sais pas vraiment comment utiliser la recherche dichotomique dans un fichier, puisque ça ne fonctionne pas de la meme manierre que dans un tableau.
Si vous savez comment faire et que vous avez du temps à me consacrer, merci d'avance!!!

9 réponses

Réponse 1 / 9
batmat Messages postés 1871 Date d'inscription   Statut Membre Dernière intervention   114
 
ben, tu lis le fichier et tu le charges dans un tableau... (en RAM donc)

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
3
Réponse 2 / 9
Lord Woden Messages postés 89 Date d'inscription   Statut Membre Dernière intervention   21
 
Salut,

Avant tout je crois qu'il serait utile que tu précises exactement ce que tu veux dire dans "un fichier contenant un dictionnaire". Je veux dire qu'il faudrait préciser le type de format de fichier et la structure de données employé pour conserver ton dictionnaire.

En effet, comme tu parles de ta capacité à faire cette recherche dans un tableau mais pas un fichier je penses que c'est de là que vient ton problème?

@+ Lord Woden ;o)
0
Réponse 3 / 9
batmat Messages postés 1871 Date d'inscription   Statut Membre Dernière intervention   114
 
De toute façon, à moins que ton fichier ne fasse plus de quelques Mo, il vaut mieux le charger en mémoire justement... sinon ta recherche va être extrêmement lente.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
Réponse 4 / 9
dodie
 
oui, désolée, j'ai oublié de préciser.
C'est un fichier txt, qui contient environ 360 000 mots.
J'ai réussi à effectuer cette recherche avec un simple strcmp, mais il se trouve que cela ralentit notre programme de scrabble, donc je pensais effectuer une recherche dichotomique pour gagner su temps. Le problème de créer un tableau de mots contenant mon dico c'est que ce serait beaucoup trop lourd, alors je ne sais pas comment faire pour faire cette recherche dichotomique sans passer mon fichier txt en tableau.

j'espère avoir été un peu plus claire...
0
batmat Messages postés 1871 Date d'inscription   Statut Membre Dernière intervention   114
 
Avec une moyenne de 15 caractères par mots (ça fait déjà pas mal, non ?), ça fait 15*360000 = 5,4Mo en mémoire... C'est pas non plus énorme. En 32 bits, on peut jouer avec jusqu'à deux Go de RAM.
Mon conseil donc : au lancement du prog, passe le en RAM... J'ai retenu un conseil sur ce type de pb : un utilisateur sera 1000 fois plus compréhensif si le prog met 2 secondes de plus à se lancer que s'il met 0.5 secondes de plus à chaque requête pendant l'exécution ...

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0
teebo Messages postés 33491 Date d'inscription   Statut Modérateur Dernière intervention   1 793 > batmat Messages postés 1871 Date d'inscription   Statut Membre Dernière intervention  
 
C'est presque toujours vrai (sauf quelques cas particuliers de programmes), j'ai meme vu une boite ou il leur fallait une heure pour lancer leur soft, ca genait personne, ils prenaient leur cafe, tapaient la discute, lisaient les mails en arrivant et voila :O)

.  .
\_/
0
fou2dodie Messages postés 605 Date d'inscription   Statut Membre Dernière intervention   33 > teebo Messages postés 33491 Date d'inscription   Statut Modérateur Dernière intervention  
 
ouai mais j'iamgine mal son prof lors de sa soutenance partir prendre un café et taper la discute le tant que le programme se lance ;0)

LMCT (H -2 avant que je te rejoigne ma dodie)

j'ai touché le fond
maintenant je creuse
0
teebo Messages postés 33491 Date d'inscription   Statut Modérateur Dernière intervention   1 793 > fou2dodie Messages postés 605 Date d'inscription   Statut Membre Dernière intervention  
 
Bien vu :-DDD

.  .
\_/
0
batmat Messages postés 1871 Date d'inscription   Statut Membre Dernière intervention   114 > teebo Messages postés 33491 Date d'inscription   Statut Modérateur Dernière intervention  
 
Ouai, mais il vaudrait mieux qu'il le prenne avant, que de penser pendant :
"J'devrais aller chercher un café moi !"

:-)

@++
Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 9
dodie
 
je vais peut etre vous paraître stupide, mais qu'est-ce que tu entends par passe le en ram? je comprends ce que tu veux dire, mais je ne vois pas du tout comment faire ça.
je ne suis pas très douée en C, en fait je n'ai commencé qu'il y a quelques moi et je reconnais que tout ce qui concerne la mémoire est un peu flou pour moi...
0
Réponse 6 / 9
p.legal
 
J'ai fait un petit prog en basic et voici les resultats: 

analyse du dico en cours...
Le programme a trouvé 369085 Mots dans le dico.
chargement en cours
100%
creation des phrases...
creation de la phrase 739 / 739
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?ZYGOMATIQUE
ce mot est bien dans le dico
temps de recherche : 281 ms
quel mot voulez-vous chercher
?AVION
ce mot est bien dans le dico
temps de recherche : 0 ms
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?LOIRE
ce mot est bien dans le dico
temps de recherche : 16 ms
quel mot voulez-vous chercher
?


j'ai un dico de 370 000 mots
je le charge en memoire dans un tableau puis je cree des phrases de 500 mots chacunes

enfin je teste la presence du mot que je cherche dans l'une de ces phrases.

si tu veux la source la voici: 

        print "analyse du dico en cours..."
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnn]
                nb=nb+1
                if int(nb/5000)=nb/5000 then locate 1,2:print nb
                mot2$=mot$
                [reload.cnn]
            wend
        close #dico
        locate 1,2:print "Le programme a trouvé ";nb;" Mots dans le dico."
        print "chargement en cours"
        nbt=nb
        dim dico$(nbt)
        nb=0
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnt]
                nb=nb+1
                mot2$=mot$
                if int(nb*100/nbt)=nb*100/nbt then locate 1,4:print using("###",(nb*100/nbt));"%"
                dico$(nb)=mot$
                [reload.cnt]
            wend
        close #dico
        print "creation des phrases..."
        nbph=int(nbt/500)+1
        'print nbph
        dim ph$(nbph)
        trace 2
        for i=1 to nbt
            nump=int(i/500)+1
            if nump<>nump2 then
                nump2=nump
                locate 1,6:print "creation de la phrase ";nump;" / ";nbph
            end if
            ph$(nump)=ph$(nump)+" "+dico$(i)
        next i
    [suite]
        print "quel mot voulez-vous chercher"
        input r$
        r$=" "+upper$(r$)+" "
        t=time$("ms")
        for i=1 to nbph
            if instr(ph$(i),r$) then okmot=1:exit for
        next i
        t2=time$("ms")
        if okmot=1 then
            print "ce mot est bien dans le dico"
        else
            print "ce mot n'est pas dans le dico"
        end if
        print "temps de recherche : ";(t2-t);" ms"
    goto [suite]
    
    wait


c'est ecrit en Liberty BASIC, donc en C tu devrais exploser les temps, tout le monde sait que le basic, c'est lent ! (lol)

@++
0
Réponse 7 / 9
DzarGol
 
y a pas moyen de créer une structure spéciale, genre un arbre binaire de recherche (basé sur le dichotomique, d'ailleurs), le stocker en mémoire au démarrage et faire ensuite des accès dessus pour la recherche? en C, ça devrait se programmer assez bien, et les structures ABR sont dans les plus rapides pour faire une recherche...

à voir... ;-)

(au fait, je suis moi aussi sur un projet de Scrabble en C, donc si vous trouvez une soluce en C, prévenez... ;-) )

@++
0
Réponse 8 / 9
Marden Messages postés 1072 Date d'inscription   Statut Membre Dernière intervention   210
 
J'ai croisé un jour déjà lointain, l'auteur d'un site avec jeu en ligne, qui m'a dit que son dictionnaire, sans doute en Java, occupait moins de 500ko.
Je suppose qu'il s'agit d'une sorte d'arbre dont les clés sont d'abord à une lettre (sous-arbre dont les mots commencent par ...), etc. Les feuilles sont les mots du dictionnaire, mais on peut supposer que les féminins, les pluriels, les conjugaisons sont gérés par des pointeurs vers quelques règles de génération des terminaisons.
Je sais que le jeu proposé n'applique aucune stratégie, se contentant de proposer la solution rapportant le maximum de points, compte-tenu des lettres déjà en place, et autres multiplicateurs de la grille.
Mon meilleur score (je ne suis pas un spécialiste) est de -40 par rapport à celui de la "machine" !!!

Le site en question : http://duel-de-mots.com/
0
Réponse 9 / 9
DzarGol
 
en fait, j'avais aussi trouvé une structure bizarre permettant de mettre l'ODS4 de 4Mo en 400Ko, mais c un algo assez compliqué... Il faut aller voir sur ce site : http://www.nongnu.org/eliot/
0

Discussions similaires

recherche à partir de la barre d'adresse
Sylviane -
Lulin -

11 réponses
Réglage chaine de la TNT FR3 TF1 A2 TMC
Yamina -
Redbart -

1 réponse
Recherche de pairs sur utorrent bloqué
flo.h -
Claire -

4 réponses
recherche manuelle canaux chaînes TNT sur TV Sony Bravia
bernie9206 -
baladur13 -

6 réponses
1fichier
titi342 -
bazfile -

1 réponse