Salutations.

Tu effectues une recherche "dichotomie" sur Google ou autre(s) et tu sauras tout.
Je vois d'ici les chevronnés dirent : Nous connaissons tous cela et ajouter (peut-être) nous ne l'utilisons pas car nous n'en avons nul besoin. Dans ce cas, rien à ajouter.
D'autres, les débutants, diront "Qu'est-ce que c'est et à quoi cela peut-il servir ?".
Pour ceux-là, j'ajouterai quelques commentaires.
Nous faisons presque chaque jour de la recherche dichotomique instinctivement, naturellement. Mais elle n'est pas vraiment rigoureuse, et, bien que seulement approximative, elle permet de gagner un temps fou. D'ailleurs, nous n'envisagerions jamais de procéder autrement.
Exemple : je recherche un mot sur un GROS dictionnaire en un seul volume TRES épais.
Par exemple "Médecin". Je ne lirais jamais tous les mots du dico par ordre alphabétique jusqu'à trouver médecin
Je vais ouvrir le dico vers son milieu et, si je découvre un mot situé avant médecin, je vais éliminer toute la partie gauche. Ensuite j'ouvre au milieu de la partie droite et je tiens le même raisonnement. Si le mot trouvé est après médecin, je vais écarter la partie droite. Mon dico a déjà été divisé par quatre (approximativement). Et ainsi de suite.

Vous savez tous que j'ai monté une application Cinéma pour Cloclo.
J'ai une option Recherche des chômeurs .
Principe : Tous les réalisateurs et acteurs ont-ils eu du travail dans au moins un film ?
Et je l'avais programmé le plus simplement possible (sans recherche dichotomique que je connais pourtant bien, l'ayant pratiquée il y a plus de 30 ans). Tant que les fichiers ont été modestes, cela allait relativement vite. Mais c'était mal connaître Cloclo : elle en ajoute tous les jours.
J'ai testé une nouvelle fois ce programme (3.588 réalisateurs, 12.207 acteurs et 10.201 films).
Le programme a tourné un peu plus de 70 minutes, plus d'Une heure.
Alors je me suis dit "il faut faire quelque chose", et j'ai décidé d'améliorer avec de la dichotomie.
Le temps de recherche a été réduit à 35 secondes et des poussières, soit 120 fois plus rapide, ce qui n'est pas du tout négligeable. Cela démontre l'intérêt de cette technique.

Quel que soit le langage, cela permet de rechercher dans une table triée ou un fichier trié ouvert en lecture la position d'une valeur.

Si tu veux en savoir plus, à ta disposition.

Salutations.

Belle démonstration, comme toujours.

SFLPMEA, je te verrais bien dans le groupe de documentation, pour nous rédiger quelques doc sur le Basic

Petite note de complexité pour les mateux

supposons que nous ayons un tableau contenant n élément trié et que l'on souhaite faire une recherche dessus.

- une recherche simple (c'est à dire tester les éléments 1 à 1), demande, au pire n opération ;
- une recherche dicotomique demande, au pire log2(n) !

Bon, pas très parlant tout ça hein ? En gros, supposons que n soit très grand, genre 4 000 000 000. Oui oui, 4 milliards.
Recherche simple : 4 milliard d'opération
Recherche dicotomique : log2(4 000 000 000) = 32 opérations (soit 125 millions de fois plus rapide )

Terrible le gain de temps non ^^ ?

Edité par Francesco ( 04/05/2008 12:24:51 )

Salutations.

La recherche dichotomique, ce n'est pas vraiment de la programmation, mais de la logique pure, assaisonnée de math.
Et c'est pourquoi elle peut (et devrait) s'appliquer quel que soit le langage utilisé.
En effet on divise le 'domaine initiale' de recherche, au fur et à mesure de l'avancement, par : 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, etc …
Elle est toujours intéressante, mais le résultat 'gain de temps' double de pair avec la dimension du fichier (ou de la table). Il est nettement plus important, en valeur temps, lorsque la prospection s'effectue dans un fichier au lieu d'une table (où tout s'effectue en mémoire centrale qui comporte préalablement le tout). Plus la table est grande (ce qui élimine en partie le Qbasic) plus c'est efficace. Si nous doublons la taille proposée par Francesco (ce ne peut être qu'un fichier de Qbasic), 8 au lieu de 4 milliards, nous n'aurons qu'un test supplémentaire

Vive la dichotomie et n'hésitez pas, si besoin , à l'utiliser.

Salutations.

Tant qu'on parle de structures de données, dans le même genre il y a les tables de hachage. C'est encore plus connu que la dichotomie, vu que dès que vous rangez un objet vous en utilisez le principe, souvent sans le savoir.

Le principe est tout simple : ranger un objet là où on sait qu'on ira le chercher. Par exemple, un livre dans la bibliothèque avec les livres de même nature. Les assiettes dans la cuisine, etc ... En informatique on peut faire pareil avec ses données, sauf que c'est la machine qui dit où elle veut les ranger. On calcule un hash de la donnée, on fait un modulo dessus pour que ça rentre dans la table que l'on a préparée. Dans chaque élément de la table, on met la liste des éléments qu'on a rangé dans cette case.

Le temps d'insertion est constant quelle que soit la taille de la table (sauf si on veut trier les listes en plus ...). Si la table est suffisamment grande, on récupère ses données en moyenne en O( 1 ) (en temps constant), mais c'est en moyenne, si les données sont mal fichues ça peut être en O( N ), mais là c'est vraiment pas de chance, faut changer de fonction de hachage . Après rien n'empêche d'utiliser la dichotomie pour aller plus vite dans les listes, mais mieux vaut agrandir la table cela permet de réduire la taille des listes à quelques éléments seulement.

Salutations.

Dans mon esprit, tous les objets sont de même nature et il ne saurait en être autrement. Ils sont déjà triés (indispensable) et je ne veux que rechercher où l'un d'entre eux se trouve, sa position. Eventuellement, vérifier si il est absent de la liste.
Il peut y en avoir un nombre pratiquement illimité. Sauf erreur, seule, la recherche dichotomique est performante.

La constitution, création du fichier qui les contient est un autre problème. Si, dans une bibliothèque, on peut insérer manuellement un livre au bon endroit (à déterminer éventuellement à l'aide de la dichotomie si le nombre de volumes antérieur atteint le million), et 'pousser' les autres, ce n'est pas le cas pour une table ou un fichier car il va falloir décaler d'une place tous les livres suivants en utilisant le SWAP pour une table (dans ce cas, nous sommes limités au point de vue nombre). Cette instruction n'existe pas pour un fichier en entrée/sortie et il faut le faire en 'triangle' en utilisant une zone auxiliaire. Il faut certainement utiliser la dichotomie pour savoir à partir d'où il convient de mettre de l'ordre.

Je ne connais pas le hachage :
http://www.supinfo-projects.com/fr/2004/hachage%5F2004/1/
Je ne l'ai jamais pratiqué, mais je me suis renseigné …

Salutations.

une table de hachage n'est pas un tableau dans lequel tu range des données, c'est simplement une sorte de sommaire qui permet de retrouver les données. Tu n'as pas à décaler quoi que ce soit dans une table de hachage puisque les données sont rangées sous forme de listes. ça ne sert qu'à dégrossir vite fait le travail de recherche/insertion.

Rien ne t'empêche d'ailleurs de ranger tes données dans une liste, un tableau ou un fichier et de les faire pointer par une table de hachage. Tout dépend de ce dont tu as besoin. Ce qui est pratique avec la table de hachage, c'est que ça permet de ranger des données d'après des clefs (chaînes de caractères, nombres, ...).

Tout dépend de ce dont on a besoin. La dichotomie nécessite une notion d'ordre pour trier les éléments, sinon impossible de diviser l'espace de recherche en temps constant, une table de hachage n'a pas besoin d'ordre, tu lui donnes une clef, elle te donne la valeur associée.

Attention ne pas confondre hachage et table de hachage. Le hachage est une opération qui "mélange" des données pour calculer une valeur qui sera suffisamment représentative des données initiales pour que si l'on recommence l'opération avec des données différentes, la probabilité d'obtenir un hash différent soit grande (mais elle reste < 1).

L'idée de la table de hachage, c'est que tu calcules le hash de ta clef, et tu ranges tes données dans la liste qui correspond à ce hash. Ensuite si tu cherches les données associées à une clef, tu recalcules le hash de la clef, et tu sais que si tu as des données associées à cette clef, alors elles sont dans la liste associée à ce hash.

Après, il ne faut pas changer de fonction de hachage, sinon c'est comme lorsque une personne range les affaires d'une autre personne, cette dernière ne les retrouve plus (enfin pas en temps constant).

Salutations.

Je crois que nous nous éloignons du sujet que je voulais évoquer sur le forum Basic dans mon message initial et que nous abordons un problème beaucoup plus vaste de stockage/recherche de données quelconques (et multiples) de toutes natures en utilisant le 'hachage'.
Il ne faut pas oublier que nous n'avons pas tous (loin de là) fréquenté Supinfo ou des écoles d'ingénieur en informatique ou autre. Nous avons peut-être un niveau correct de maths, nous en avons retenu les bases essentielles suffisantes pour nos besoins courants, et nous continuons à apprendre le plus possible si cela nous est permis. La plupart d'entre nous est autodidacte : après un petit stage éventuel en informatique sur les principes de base, nous nous sommes lancés dans la programmation (sur des matériels divers qui ont beaucoup évolués depuis nos débuts, avec juste un manuel de références), bien souvent dans des applications qui pouvaient être une vraie découverte, avec des interlocuteurs qui ignoraient tout de l'informatique et s'imaginaient que tout était possible (un ordinateur peut tout faire, sans limites). Et il n'était nullement question d'applications très scientifiques, mais relevant simplement de la vie courante des entreprises.
Nous ne sommes pas tous des étudiants bénéficiant d'un environnement d'aide et assistance, ce qui doit aider beaucoup.
Notre seule arme : une logique rigoureuse indispensable, mais nous sommes seuls pour essayer de résoudre nos problèmes, peser le pour et le contre, définir la bonne méthode. Essayons de bien connaître et maîtriser les fichiers 'classiques' dans une première étape. Ne compliquons pas outre mesure les façons de procéder.

Peut-être, plus tard …
A ce moment-là, nous ferons appel à zuzuf.

Salutations.

Je suis d'accord avec toi, il faut que ça reste simple. Mais je suis convaincu que c'est simple, je connaissais cela avant d'arriver en école. Le problème c'est que j'ai peut être perdu l'habitude d'expliquer avec des outils que tout le monde connait

Au passage: dans le cycle ingénieur, on débute l'informatique en prépa, et à un niveau assez faible... on a pas mal de retard sur le reste du monde à ce niveau là . Une grande partie de ce que je connais en informatique, je l'ai apprise grâce à ces forums, et c'est plus que suffisant pour que je m'en sorte très bien sans travailler l'info à l'école !

En tout cas, je retiens la leçon, la prochaine fois, j'éviterais de pondre un amas de texte incompréhensible

J'apporte mon témoignage surle parcours d'ingénieurs. Les cours d'info à proprement parler ont commencé, pour moi, en école d'ingé, et non en prépa.

Les cours dispensés se limitaient principalement à aborder la programmation procédurale. Mais rien de bien spécifique. On trouve tout le contenu sur le web et assez facilement.

Le petit plus que j'ai pu trouvé concerne des cours de génie logiciel, branche très souvent oublié lorsqu'on est autodidacte.

Génie logiciel?
Tu parles de l'UML, je suppose?
A part le cas des diagrammes de classe, je voit pas l'intérêt de ce truc ^^