Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
3005 connectés 

  FORUM HardWare.fr
  Programmation
  C++

  [Réglé][C++]Vérification d'algorithme + conseils

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Réglé][C++]Vérification d'algorithme + conseils

n°1924034
burn2
ça rox du poney
Posté le 14-09-2009 à 19:43:07  profilanswer
 

Bonjours à tous et toutes, je m'en viens chercher votre avis sur un algorithme que je vois pour solutionner un problème. Tout d'abord pardon pour le pavé qui va suivre.
Mon but n'est donc pas que vous me pondiez une solution, mais bien juste que vous me confirmiez ou me conseillez d'améliorer certaines choses afin d'avoir quelque chose de "parfait" et pas trop contraignant à faire évoluer. :o
 
 
Bon alors voilà le contexte:

Citation :


Je reçois un fichier avec des enregistrements en csv dedans (avec un champ ou j'ai un code postal). ==> + de 3000 enregistrements dedans et ça pourra augmenter.
Je dois spliter ce fichier en 3 agences. Donc 3 fichiers différents.
Ces 3 agences ont un département (admettons 33, 34, 45) et doivent recevoir les enregistrements correspondants à leurs départements.
Le nombre d'enregistrement doit être découpé en 3 donc.
Les enregistrements doivent être affecté dans un ordre choisis. (C'est à dire que j'ai une table d'enregistrement des départements dans un ordre voulu).
Je dois donc affecter tous les enregistrement en parcourant la liste des départements et récupérant les enregistrements concernant ce département pour l'affecter aux agences.  
(toujours en gardant à l'esprit que le 33 doit avoir ses enregistrements + d'autres le total ne devant pas dépasser le nombre total d'enregistrement/3).
Bien sûr le fichier d'enregistrement de tous les enregitrements à spliter n'est pas ranger forcément s'eu été trop facile.


 
J'ai choisis de partir sur du C++/QT, pas de conseil à prendre ici, c'est mon choix, un choix comme un autre donc merci d'éviter les C# ça sux tout ça. :D
 
Dans tous les cas mon point de repère doit être ma table de département organisé, je dois la parcourir et affecter à chaque agence les enregistrements en puisant dans les données. (ça ça ne peut changer). Cette table est un fichier texte qui contient les départements en ligne.
 
Donc du point de vue d'algorithme au début j'étais parti sur du sqlite et insérer tous les 3000 enregistrements dans la bd puis faire des select par département, mais de une c'est long à insérer 3000 enregitrements :/ Et puis de deux en réfléchissant ça me semble un peu c$$ et une meilleure idée m'est venue à l'esprit.
 
 
Donc voilà l'idée de structure qui m'est venue à l'esprit, le tout devant être facilement évolutif (nombre d'agence qui bouge, table des départements qui bouge, et pourquoi pas devoir travailler avec une bd pour faire tout un tas d'autre truc).
 
Structure:

Citation :


QStringList Tableau [nb_departement]: tableau qui va contenir mon fichier d'enregistrement mais classé par département (près traitement), donc dans chaque case correspondant au département, j'ai une liste de QString (donc pareil que les strings pour ceux qui ne connaissent pas le qt).
 
Liste numAgence: une liste d'entier qui contient les départements des agences. (vous comprendrez plus tard pourquoi cette nécessitée).
 
Une classe agence avec comme atributs:
m_departement: département principal de l'agence
m_listRec: liste de ligne d'enregistrement qui sont affectés à l'agence.
une methode count() qui renverra le nombre d'élément dans m_list
 
Avec donc une liste d'agence
list<Agence> m_agences;


 
 
Etape 1:
J'ouvre mon fichier d'enregistrement, lit la première ligne et je récupère le nombre de colonne du fichier (en comptant le nombre de ";" puisque c'est du csv)
J'ai récupérais préalablement dans un fichier de conf (via un QSetting) la colonne qui contient le code postale (je préfère paramétrer car si la structure du fichier change je n'aurais que le paramétrage à faire) et je vérifie que je puisse accéder à cette colonne, on l'appelle colonneCodePostale.
Soit "ligne" la ligne courante lue;
A partir de là j'insère dans mon tableau chaque ligne de cette manière:
tableau[ligne.split(';').at(colonneCodePostale)].add(ligne);
car ligne.split(';').at(colonneCodePostale) me renverra le code postal de l'enregistrement (en gros je bidouillerais pour convertir 33800 en 33 mais bon là rien de génant), donc le but est de trier dans le tableau par code postale.
 
ça c'est la première étape, à la fin de cette étape j'ai donc toutes mes lignes d'enregistrement rangées dans un tableau classé par département le tout dynamique.
 
Etape2:
Je vais chercher dans mon fichier de setting les agences.
Pour chaque agence je fais:
j'insère le département dans numAgence et je crée une agence en lui affectant son département dans l'attribut.
Je récupère la taille du tableau (j'ai maintenant le nombre d'enregistrement :) ) et je divise par le nombre d'éléments dans m_agences pour récupérer donc le nombre d'enregistrements que doit avoir chaque agence: on l'appellera nbperagence
 
Etape3:
J'ajoute pour chaque agence les enregistrements les concernants directements (les enregistrements du 33 pour l'agence 33 etc...) afin d'en être débarrassé.
J'ouvre mon fichier qui possède les départements organisés.

Code :
  1. Soit agenceCourante un entier qui pointe sur l'agence en cours (agence non pleine) initialisé à 0
  2. Tant que pas à la fin du fichier des départements triés
  3. si ma liste des num d'agence ne contient pas ce département (donc pas déjà inséré)
  4.   //(et c'est pour celà que je l'ai créé afin de savoir en une seule ligne via un if (!numAgence.contain(num)) si c'est une agence ou pas.
  5.   tant que (tableau[num].count()!=0)
  6.   {
  7.     //le ou est pour éviter les effets de bors des nombres impairs
  8.     si (m_agences.at(agenceCourante).count()<nbperagence || agenceCourante==numAgence.count()-1)
  9.    {//on rajoute l'enregistrement à l'agence agenceCourrante de la liste
  10.      m_agences.at(agenceCourante).add(tableau[num].at(0))
  11.      //puis on supprime l'enregistrement dans la liste de ce département du tableau afin de le vider progressivement
  12.      tableau[num].removeat(0);
  13.     }
  14.     sinon alors on l'incrémente:
  15.       agenceCourante++;
  16.   }
  17. lire ligne suivante du fichier des départements


 
 
Me voilà donc avec mes agences qui ont leurs listes d'enregistrements affectés. Il ne me reste plus que soit les insérer dans un fichier soit dans une base de donnée. Et normalement le tout est totalement évolutif et dynamique.  
Qu'en pensez vous? Niveau mémoire ça va passer?? Vous voyez des astuces pour gagner du temps?
 
 
Merci d'avance si vous prenez le temps de tout bien lire et que vous me comprenez. :)


Message édité par burn2 le 15-09-2009 à 18:43:23

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
mood
Publicité
Posté le 14-09-2009 à 19:43:07  profilanswer
 

n°1924135
rufo
Pas me confondre avec Lycos!
Posté le 15-09-2009 à 09:44:43  profilanswer
 

Ton algo est plus rapide que de passer par une insertion dans une bd puis du requêtage?


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°1924137
burn2
ça rox du poney
Posté le 15-09-2009 à 09:54:36  profilanswer
 

En passant par une db du style sqlite, à mon avis de loin, je n'ai pas fini de le faire, mais vu le temps que ça prends pour insérer 3000 enregistrements dans une bd (avec le dd qui mouline à fond) je suis sûr à 100% que ça sera bien plus rapide.
(il me faut plus de 5/10 minutes rien que pour faire l'insertion dans la bd vu que j'ai déjà fait cette étape, alors nulle doute que tout le reste sera bien plus rapide).
 
Par contre je viens de repenser au territoires d'outre mer. C'est du 97X :/ C'est pas pratique ça pour mon histoire de tableau.
Ou alors je concidère que les domTom c'est 101 102 103 104 105... au lieu de 971 972.... (normalement il n'y en aura jamais mais bon on ne sait jamais ce qui peut se passer).
 
EDIT: ah non c'est bon pour les domtom c'est toujours la même taille niveau longueur c'est 97XXX 98XXX donc c'est bon sauvé. :)


Message édité par burn2 le 15-09-2009 à 10:19:50

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924151
burn2
ça rox du poney
Posté le 15-09-2009 à 10:32:38  profilanswer
 

Je confirme niveau temps: 5s pour traiter les 2400 lignes au lieu de plus de 5minutes. Donc gros gain. (juste pour l'équivalent de l'insertion dans la bd)


Message édité par burn2 le 15-09-2009 à 10:32:51

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924206
rufo
Pas me confondre avec Lycos!
Posté le 15-09-2009 à 13:29:53  profilanswer
 

bizarre quand même 5 à 10 mins pour insérer 3000 lignes dans une BD. J'utilise Mysql et ça met pas ce temps là.
En ce moment, je m'amuse à faire du calcul matriciel en php et pour que ça aille plus vite, je fais tout dans des tables myisam de Mysql. Là, pour insérer 1 471 680 lignes, il m'a fallu moins de 30 mins (et encore, dans le tas, y'avait un traitement en php chargé d'analyser les mots de plus de 600 documents txt avant de les mettres dans la table). Et pour dupliquer cette table dans une autre, quelques secondes seulement... Donc soit t'as un pc tout pourri, soit sqlite est lent ou pas adapté pour faire ce que tu veux. Tu devrais essayer avec mysql ;)


Message édité par rufo le 15-09-2009 à 13:31:31

---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°1924211
burn2
ça rox du poney
Posté le 15-09-2009 à 13:47:00  profilanswer
 

Oui sqlite doit être lent en insert. ;)
En select, rien de visible, mais en insert c'était affreusement long.  
Je sais que mysql est bien plus rapide pour avoir fait de l'insertion de masse. Mais là ma solution niveau algo me semble bien plus efficace que via une bd.
(surtout que je ne me vois pas installer un service mysql sur mes serveurs en plus juste pour des données temporaires...)
 
EDIT: il me reste juste à solutionner un problème incompréhensible dans mes classes je risque de revenir poster si je ne trouve pas la cause.


Message édité par burn2 le 15-09-2009 à 13:48:49

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924235
burn2
ça rox du poney
Posté le 15-09-2009 à 14:39:27  profilanswer
 

Bon j'ai résolu mon bug, par contre ma répartition n'est pas équitable, du moins pas tout à fait, il faut que je comprenne ce qui se passe.
j'ai 794 810 et 810.
Je dois avoir un problème dans mon algo qui pourtant me semble logique :??:
 
Pourtant j'ai 2431 enregistrements.
Divisé par le nombre d'agence soit 3 pour le moment c'est 810. La question est pourquoi ma dernière agence n'a pas le compte total, visiblement j'ai choucrouté une boucle.
EDIT: ou alors je n'ai pas tous les départements dans ma liste...
 
EDIT2: bon ben c'est ça j'ai 95 départements (en rajoutant mes 3 agences) et pas 96 donc il en manque un je pense.
EDIT3: il m'en manquait bien un mais j'ai toujours pas le compte: 810 810 806.
il m'en manque encore 5. ça sent la boucle qui s'arrête trop tôt ça.


Message édité par burn2 le 15-09-2009 à 15:15:00

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924256
burn2
ça rox du poney
Posté le 15-09-2009 à 15:22:38  profilanswer
 

Bon je ne comprends pas, il me manque des éléments encore, mais à la fin je n'ai plus rien dans mon tableau trié temporaire par département.
Donc soit je ne récupère pas toutes les lignes du fichier, soit j'en oublie lors de la sauvegarde?
Sauf que le problème, c'est 6 lignes qu'il manque, 5 lignes c'est bizarre
 
 
EDIT: récapitulons:
Dans ma boucle qui récupère les lignes du fichiers et les classes j'ai bien 2431 lignes.
Donc je récupère bien l'ensemble de mon fichier.
 
Je sais que dans mon agence 1 j'ai bien 810 lignes
DAns mon agence 2 j'ai bien 810 lignes.
Dans mon agence 3 je devrais avoir 811 lignes oui mais non j'en ai 806.
ET il ne reste plus rien dans mon tableau qui avait les 2431 lignes. What could be the problem... IL faudrait que je dépile quelque part sans empiler ailleurs or normalement je n'ai pas une boucle de ce genre là...


Message édité par burn2 le 15-09-2009 à 15:47:31

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924268
rufo
Pas me confondre avec Lycos!
Posté le 15-09-2009 à 15:56:48  profilanswer
 

un écrasement d'un élément déjà empilé peut-être?


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°1924270
burn2
ça rox du poney
Posté le 15-09-2009 à 16:03:26  profilanswer
 

Je fais des pushfront() donc normalement impossible.
BOn je suis sûr à 100% que:
Je récupère bien 2431 lignes que je stocke.
Que lors de la première étape, c'est à dire lors que j'affecte à chaque agence ses enregistrements (33 pour le 33 etc)
j'ai bien encore le bon compte. (en faisant la somme de ce que j'ai dans le tableau de rec et la somme de ce que j'ai par agence)
 
Il ne reste donc plus que l'étape ou je vide le tableau par la suite et l'étape ou je sauvegarde (mais si ça sauvegarde bien 810 pour deux agences, vu que c'est la même fonction pourquoi pas ensuite???).
 
 
EDIT: bon apparemment ils sont en fait toujours dans mon tableau! Je ne sais pas pourquoi je n'avais pas réussi à les voir... Me reste à trouver pourquoi et ou ils sont.


Message édité par burn2 le 15-09-2009 à 16:06:27

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
mood
Publicité
Posté le 15-09-2009 à 16:03:26  profilanswer
 

n°1924274
burn2
ça rox du poney
Posté le 15-09-2009 à 16:09:11  profilanswer
 

Gné, ils sont dans le département 0! Comment c'est possible! alors là moi y en a pas comprendre. :D
(ce qui explique pourquoi je me suis fait avoir quand j'ai testé l'indice ou j'avais des enregistrements encore en stock)
 
EDIT: ok j'ai compris comment c'est possible, j'ai des enregistrements sans code postal, le truc qui ne devrait pas être possible.... Mais bien sûr vu qu'on ne maitrise pas les données sources...


Message édité par burn2 le 15-09-2009 à 16:11:06

---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924278
burn2
ça rox du poney
Posté le 15-09-2009 à 16:21:10  profilanswer
 

Donc c'est bon c'est good, ça marche et ça prends à peine 2s.
Personne n'a de conseil ou d'amélioration?


---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"
n°1924289
rufo
Pas me confondre avec Lycos!
Posté le 15-09-2009 à 17:28:40  profilanswer
 

ben 2s, ça vaut pas le coup de chercher à optimiser :/


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°1924318
burn2
ça rox du poney
Posté le 15-09-2009 à 18:43:10  profilanswer
 

OK bon je passe ça en réglé. ;)
Merci d'avoir pris le temps de lire ce pavé.


---------------
"C'est vrais qu'un type aussi pénible de jour on serait en droit d'espérer qu'il fasse un break de nuit mais bon …"

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C++

  [Réglé][C++]Vérification d'algorithme + conseils

 

Sujets relatifs
Post à supprimer!ASM(masm32) ou C++ ?
[C] conversioncross compilation C++ et wrapper C++
Programation en C[C#]Cherche idée de programme, sondage
Encoder une URL en CSharp C#[C++] Probleme de Makefile/linkage
verification code chargement java appelant un fichier prolog via jplQuelques conseils sur access !
Plus de sujets relatifs à : [Réglé][C++]Vérification d'algorithme + conseils


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR