optimisation Résolu/Fermé

Question

Bonjour, 

j'ai un petit exercice que l'on m'a donné et je ne comprend pas ce que je dois répondre, voici l'énnoncé : 


On vous demande d'optimiser un petit programme faisant office d'annuaire de la société. Les utilisateurs entrent un nom et obtiennent le numéro de téléphone associé en retour.
Ce programme lit dans un fichier texte des milliers de couples d'information « nom / numéro de téléphone ». Le fichier texte fait quelques dizaines de Mo.
Le fichier texte est mis à jour une fois par jour, la nuit, quand l'application est éteinte.
On compte une dizaine de milliers d'utilisations (demande d'un numéro de téléphone) chaque jour. 
Actuellement, pour chaque demande utilisateur, le programme parcourt séquentiellement le fichier pour trouver la réponse à renvoyer. Cette opération prend parfois plusieurs secondes.
On vous demande quelles modifications effectuer dans le programme pour accélérer les demandes utilisateur (sans utiliser de base de données).
Que recommandez-vous, en 5 lignes max (1 ligne bien choisie peut suffire), comme modifications du programme ?



Configuration: Mac OS X Mountain Lion  (10.8.2) / Chrome 24.0.1312.56

yoann090 · Answer

Bonjour,  

Actuellement, pour chaque demande utilisateur, le programme parcourt séquentiellement le fichier pour trouver la réponse à renvoyer. 

Il faut que tu proposes un autre protocole de recherche qui peut être plus rapide.

En gros, la recherche séquentielle fait que le programme parcourt tout le tableau jusqu'à trouver le nom recherché, mais par exemple si le nom recherché est Zimmerman et qu'il commence par la lettre A, ça va prendre du temps de le trouver. Il faut que tu modifies l'algorithme pour qu'il recherche différemment.

guiguidili · Answer

Merci beaucoup, 

mais c'est la que je comprend pas justement, l'algorithme je l'ai pas et j'ai pas trop d'idée de à quoi il peut ressembler donc pour le modifier c'est pas facile.

yoann090 · Answer

Le "que recommendez vous" me laisse penser qu'on vous demande pas un algorithme précis mais juste d'expliquer ce que vous pouvez faire. 
L'algorithme avec recherche séquentielle peut être du genre un grand tableau avec admettons 100 noms dedans, chaque case du tableau contenant une variable String avec le nom de la personne. Dans la recherche séquentielle en pseudo langage on aura un truc du genre : 

POUR indice allant de 1 à 100 

SI nom_recherché=tableau_indice_i ALORS

Afficher(nom+numéro tel associé à l'indice i)

SINON tableau_indice_i PREND LA VALEUR tableau_indice_i+1

-----------------------------------------------------------
On pourrait utiliser du faire tant que, ou tout autre chose, en fait on s'en moque. Ce qui compte c'est que l'algorithme va lire chaque nom du tableau jusqu'a ce qu'il trouve le bon. 
-------------------------------------------------------------
Ton exercice est donc d'expliquer en quelques lignes comment lui faire chercher pour que ça aille plus vite. 

Exemple (je te donne quasiment la réponse...) : recherche dichotomique, l'ordinateur va cherché par rapport à la valeur du milieu du tableau si le nom est contenu dans la première moitié ou la deuxieme, et à chaque fois il réduit. Du coup ça va plus vite. 

Par exemple pour ZIMMERMAN, il se place au milieu il remarque que le nom est dans la deuxieme moitié et il ne va rechercher plus que la, à l'étape 2 admettons que la moitié de la première moitié tombe sur VERNAY il cherchera de nouveau dans la moitié droite. 

Pour le faire avec des nombres c'est très facile, avec des noms, une possibilité étant d'associé les lettres de l'alphabet à des caractères ASCII. 


Tu fais un mix entre ce que j'ai dit au début sur la recherche par groupe de lettre (String) et par code ASCII et tu peux proposer une réponse.

KX · Answer

Si "le fichier texte fait quelques dizaines de Mo", il peut facilement être stocké en mémoire, ce qui évite déjà des lectures incessantes dans le fichier alors que les accès sur le disque dur sont plus lent que dans la mémoire vive. D'autant que "Le fichier texte est mis à jour (...) quand l'application est éteinte."

Après une fois en mémoire on peut imaginer n'importe quelle structure de données, donc soit un bête tableau mais en utilisant une dichotomie comme proposé par yohan090, soit d'autres structures plus performantes comme les arbres, les tables de hachage, etc.

guiguidili · Answer

ok j'ai bien compris ce dont vous parlez. Merci beaucoup, je n'avais pas penser à la technique du code ASCII.

Optimisation

5 réponses

Discussions similaires

Newsletters