Forum Programmation.perl Traitement de gros fichier

Posté par . Licence CC by-sa
Tags :
1
24
mar.
2015

Salut à tous,

Voilà je dois rechercher dans un fichier le contenu d'un autre fichier.

mais deux fichiers ont 8 champs chaqu'un séparer par des ";"

je dois vérifier si le champs 8 de mon premier fichier est présent dans mon second fichier ( champs 8 égalements ) si c'est pas le cas ecrire la ligne complete dans un fichier de sortie.

Seulement mon second fichier fais un peu plus de 7 millions de lignes =/

Donc les double boucle sa ramme un peu ^

je débute en perl, donc si âme charitable veux bien m'aider pour avoir un traitement optimiser …

  • # table de hachage

    Posté par . Évalué à 1.

    Tu peux essayer de construire une Table de hachage gigantesque avec le champ 8 de ton second fichier, ainsi tu n'auras plus de double boucle et tu pourras rechercher très rapidement si une valeur est présente dans le gros fichier.

    • [^] # Re: table de hachage

      Posté par . Évalué à 2.

      à priori, je ferais probablement un truc dans ce gout là, mais il manque quelques infos dans la présentation du problème pour mieux cerner le problème. Par exemple, tu présupposes que le fameux champs 8 peut prendre beaucoup de valeurs différentes, ce qui mènerait à une table de hachage relativement importante, mais c'est un truc à vérifier. La variabilité de ce champs peut changer le choix de la méthode de résolution. Par exemple, si le champ ne peut prendre qu'un nombre relativement restreint de valeurs, on pourrait arrêter de parser les deux fichiers dès qu'on aurait relevé la présence au moins une fois de chaque valeur dans le second fichier.

      A partir d'ici, ce commentaire ne s'adresse plus à toi, mais à l'auteur de la question.

      Une meilleure connaissance du contexte pourrait aussi aider.
      Par exemple, est-ce que c'est un script qui doit être lancé régulièrement ou est-ce que ça ne servira qu'une fois de temps en temps ? Est-ce qu'il y a des contraintes particulières sur le temps de traitement, l'espace disque, la quantité de RAM disponible ? Est-ce que le second fichier est un fichier de référence qui évolue lentement au cours du temps (auquel cas on pourrait maintenir un index des valeurs possibles dans un fichier indépendant et trié), ou est-ce qu'on doit régulièrement comparer deux fichiers dont la taille varie arbitrairement ? Est-ce que les fichiers sont triés sur le champ 8 ? (peu probable, mais si c'est le cas, on peut gagner plein de temps).

      Tant qu'on y est, comment sont générés ces fichiers et est-ce qu'on a accès à leur mode de génération ? (genre s'ils sont extraits du BDD à laquelle on a accès, il y a peut-être quelque chose à faire).

      • [^] # Re: table de hachage

        Posté par . Évalué à 1.

        Merci de ta reponse je vais essayer d'etre plus precis

        Ce traitement sera lancer occasionellement. Oui il y a une contrainte de temps, le script ne doit pas dépasser les 20mins. Pour ce qui est des ressources machine il y a pas de contrainte.

        Le champs 8 ( qui nous sert de reference entre les deux fichiers ) peut varier énormément.

        Les fichiers n'évolue pas, pour resumé le context on a effectuer une fusion entre deux entité et on veux vérifer que ce qui était dans l'entité A ce retrouve bien dans l'entité B.

        On a donc extrait le 1er fichiers avant fusion puis le second fichier après fusion. Les deux fichier sont des extrait de base de donnée mais je n'est pas la main sur les extractions je les recois tel quel.

        ex du fichier 1 ( ~ 7000 lignes ) :

        04129441;555;wJsQC0000OpkA;SOLEV003930;CR;11.69;wJsQC0000OpkA;MmDx90005bejL

        ex du fichier 2 ( + de 7 millions de lignes ) :

        00473316;009;wJsQC00006A50;109FL002698;CR;1.98;wJsQC00006A50;MmDx90004D59C

        J'espère que c'est plus claire comme sa.

        • [^] # Re: table de hachage

          Posté par (page perso) . Évalué à 2. Dernière modification le 25/03/15 à 13:10.

          Faudrait faire en Perl un truc du même genre que ça:

          #!python3
          
          connu = set()
          with open("fichier1") as f:
              for ligne in f:
                  items = ligne.split(':')
                  connu.add(items[7])
          
          nouveau = set()
          with open("fichier2") as f:
              for ligne in f:
                  items = ligne.split(':')
                  nouveau.add(items[7])
          
          print(connu - nouveau) # doit afficher set() si tout ok

          Et ajouter mémorisation indexée des lignes de connu afin de pouvoir les ressortir…

          Python 3 - Apprendre à programmer en Python avec PyZo et Jupyter Notebook → https://www.dunod.com/sciences-techniques/python-3

        • [^] # Re: table de hachage

          Posté par . Évalué à 2.

          c'est un peu plus clair, mais ça soulève d'autres questions. Vous avez si peu confiance dans votre mécanisme de fusion que vous deviez faire ce type de vérification ? Ou alors vous avez à faire à un intervenant tiers qui parfois fais sa fusion correctement, parfois pas, et vous n'y pouvez rien ? En tout cas, ça fait pas rêver :D

          • [^] # Re: table de hachage

            Posté par . Évalué à 1. Dernière modification le 25/03/15 à 15:20.

            C'est plus un principe de précaution, il est question de gros sous …

            J'ai reussi a faire ce que je voulais en passant par des tables de hachage.

            J'ai un peu galèrer a tous comprendre mais une fois assimiler c'est super pratique ce machin là ^ .

            Le traitement dure environ 1m30.

            #Tables de hash des unions et intersections des deux fichiers
            %inter = ();
            %union = ();
            
            #Ouverture des fichiers, tue le script en cas d'echec
            open(FILE,"fichier_1.txt") or die;
            open(FILE2,$fichier_comp) or die;
            
            #Chargement des references chaque fichiers dans des tableaux
            while(<FILE>){
                chomp();
                @ligne = split(/;/,$_);
                push(@index1,$ligne[7]);
            }
            
            while(<FILE2>){
                chomp();
                @ligne2 = split(/;/,$_);
                push(@index2,$ligne2[7]);
            }
            
            #Fermeture des fichiers
            close(FILE);
            close(FILE2);
            
            #On mes tous les elements du premier tableau dans l'union
            foreach $a (@index1) {
                $union{$a} = 1;
            }
            
            #Pour tous les elements du second tableau
            foreach $a (@index2) {
            
                #Si il existe dans l'union, c'est qu'il est dans les tableau precedant
                #Il est donc placer dans l'inter
                if ( exists ($union{$a} ) )
                {
                    $inter{$a} = 1;
                }
            
            }
            
            # reconstitution des tableaux à partir
            # des tables de hachage
            my @inter = keys(%inter);
            
            • [^] # Re: table de hachage

              Posté par . Évalué à 3. Dernière modification le 25/03/15 à 16:01.

              C'est un bon début :)

              Il est possible de simplifier largement ton traitement (au vu de ton énoncé) en n'utilisant qu'un seul hash contenant toutes les informations dont tu as besoin :

              #!/usr/bin/perl
              
              #Tables de hash contenant en clé la référence et en valeur la ligne à afficher
              %lignes_a_afficher = ();
              
              #Ouverture des fichiers, tue le script en cas d'echec
              open(FILE,"fichier_1.txt") or die;
              open(FILE2,"fichier_comp") or die;
              
              #Chargement des references et des lignes à afficher dans le hash à partir du premier fichier
              while(<FILE>){
                  chomp();
                  @ligne = split(/;/,$_);
                  $lignes_a_afficher{$ligne[7]} = $_;
              }
              close(FILE);
              
              #Vérification de la présence de la ref dans le second fichier, si elle est présente on l'enlève des lignes à afficher
              while(<FILE2>){
                  chomp();
                  @ligne2 = split(/;/,$_);
                  if (exists $lignes_a_afficher{$ligne2[7]}) {
                    delete $lignes_a_afficher{$ligne2[7]};
                  }
              }
              close(FILE2);
              
              #Affichage 
              foreach my $ligne_a_afficher (values(%lignes_a_afficher)) {
                 print $ligne_a_afficher."\n";
              }
              • [^] # Re: table de hachage

                Posté par . Évalué à 1.

                Merci beaucoup c'est pile ce qu'il me fallais.

                Merci à tous pour votre aide :)

  • # join

    Posté par . Évalué à 1. Dernière modification le 24/03/15 à 15:41.

    Essaye peut-être avec la commande "join" ?

    join -t';' -v1 -1 8 -2 8 fichier1 fichier 2

    (ou quelque chose comme ça, je suis pas très au fait de la commande join)

    Edit: oups, pas vu qu'il s'agissait d'une demande en perl

  • # indexation

    Posté par . Évalué à 2. Dernière modification le 24/03/15 à 15:59.

    Tu peux indexer en mémoire, dans un premier temps, ton champ à comparer dans un tableau en utilisant le plus petit des deux fichier puis parcourir le second pour tester la présence du champ dans le tableau avec un smart match ($index ~~ @tableau). Ce sera déjà bien plus efficace que la double boucle répétant l'éclatement des champs du fichier.

  • # Un petit exemple ...

    Posté par . Évalué à -2.

    Merci pour vos réponse, mais un petit exemple avec vos solution serais le bien venu, je suis vraiment une bille en perl ( mais j'ai pas le choix du langage … ).

  • # Problème de type N^2

    Posté par . Évalué à 1. Dernière modification le 25/03/15 à 12:32.

    Dans tous les cas, à moins que tes deux fichiers ne soient déjà triés (ordre croissant ou décroissant), le problème est de complexité N2 (temps de calcul proportionnel au carré de la quantité de données).

    Et si tu dois les trier avant, tu retombes sur une complexité N2 pour le tri…

    • [^] # Re: Problème de type N^2

      Posté par (page perso) . Évalué à 2.

      Et si tu dois les trier avant, tu retombes sur une complexité N2 pour le tri…

      Avec un algo naif, oui. Le meilleur algo est en nlog n (et c'est dans le pire cas). Donc il peut être utile de trier les fichiers. Ensuite la comparaison deux deux fichiers se fait rapidement (en O(n))

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.