Forum Programmation.shell Suppression massive de lignes

Posté par  .
Étiquettes : aucune
0
26
jan.
2007
Salut,

Voila je cherche un petit conseil. Je possede deux fichiers: f1 et f2 (environ 100000 et 60000 lignes respectivement).
Ce que je souhaite faire c'est supprimer de f1 les entrees se trouvant dans f2. A priori facile.. mais ce que je cherche c'est la solution la plus rapide possible.
Pour l'instant je parcours mon fichier f2 et je fais un sed '/entre/d' f1. Ca marche mais c'est terriblement lent..
J'ai essaye un grep -v -f f2 f1mais c'est encore pire.

Alors si qqn a une idee, je suis preneur.
Petite precision, les fichiers f1 et f2 ne contiennent pas les memes donnees.

Merci

  • # fichier trié ?

    Posté par  (site web personnel) . Évalué à 2.

    Tes fichiers sont trié ? Sinon, pour chaque ligne de f1 tu dois tester avec tout f2.

    Sinon, il faut avancer les 2 fichiers ensembles.

    "La première sécurité est la liberté"

    • [^] # Re: fichier trié ?

      Posté par  . Évalué à 1.

      Effectivement mes fichiers sont non tries.
      En fait f1 contient pas mal d'infos (genre: cle blablabla) et f2 ne contient que des "cles" (une par ligne).
      Donc je suis effectivement oblige de parcourir tout f2 (je pense..)

      • [^] # Re: fichier trié ?

        Posté par  (site web personnel) . Évalué à 2.

        Je ferais un parse en perl qui colle f2 dans un %hash ensuite tu cherches chaque clef de f1 dans le hash, si tu le trouve, bingo.

        "La première sécurité est la liberté"

        • [^] # Re: fichier trié ?

          Posté par  . Évalué à 1.

          Le probleme c'est que moi et le perl.. on est fache :)
          Je vais quand meme essayer de voir.
          Merci de ta reponse

  • # Capillo-tracte

    Posté par  (site web personnel) . Évalué à 1.

    Hello,

    voila une idee, non testee:

    concatenation des 2 fichiers
    ~> cat f1 f2 > f3

    selection des doublons (il faut trier d'abord)
    ~> sort f3 > f4; uniq -d f4 > doublons

    concat doublons et f1
    ~> cat f1 doublons > f5

    selection des lignes uniques de f1 (toutes celles qui sont aussi dans f2 sont en double dans f5)
    ~> sort f5; uniq f5 > f6

    et hop, dans f6 tu as ce que tu veux!
    Je pense que ca peut etre relativement rapide.

    pour rigoler, ca doit pouvoir se faire en une ligne:
    ~> cat f1 `cat f1 f2 | sort | uniq -d` | sort | uniq

    • [^] # Re: Capillo-tracte

      Posté par  . Évalué à 1.

      Merci de ta reponse mais je ne pense pas que ca marche.
      Comme dit plus haut, les fichiers ne contiennent pas les memes donnees.
      f1 contient des infos + des "cles" (ex: cle blablabla) et f2 ne contient que "des cles" (une par ligne)
      Donc meme en triant je n'aurais pas de doublon..

      • [^] # Re: Capillo-tracte

        Posté par  . Évalué à 2.

        et un grand coup de
        grep -v "^cle " f1
        ca peut pas le faire, si le but est juste de virer les lignes de clef ?

        hmmm... F1... RB3... désolé, je m'égare...

      • [^] # Re: Capillo-tracte

        Posté par  (site web personnel) . Évalué à 1.

        Ah OK, j'avais effectivement mal compris... Ca ne peut pas marcher comme ca.

        Desole, et bonne chance quand meme!

  • # Si tu peux utiliser autre chose que le shell...

    Posté par  (site web personnel) . Évalué à 3.

    J'avais commencé par un remlines.py
    #!/bin/env python
    # -*- coding: ascii -*-

    def remlines(fin,fref,fout) :
    ....lines_to_remove = set(iter(open(fref)))
    ....fin_file = open(fin)
    ....fout_file = open(fout,"w")
    ....for line in fin_file :
    ........if not line in lines_to_remove :
    ........fout_file.write(line)
    ....fout_file.close()
    ....fin_file.close()

    if __name__ == "__main__" :
    ....import sys
    ....remlines(sys.argv[1],sys.argv[2],sys.argv[3])

    (j'ai mis des . en début de ligne à la place des espaces because indentation en Python)
    Qui supprime les lignes de f2 que l'on trouve exactement dans f1.

    Mais j'ai vu ta petite précision les fichiers f1 et f2 ne contiennent pas les memes donnees et les discussions... bref tu recherche pour chaque ligne de f1 si elle contient une des lignes de f2... Ca serait bien le boulot d'une jolie expression régulière avec f2[0] | f2[1] | f2[3]... compilée en mémoire, et appliquée à chacune des lignes de f1. Ca peut se faire en Python (modulo peut-être la longueur d'une telle expression), mais il me semble que ce genre de traitement est le domaine naturel de Perl.

    Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

    • [^] # Re: Si tu peux utiliser autre chose que le shell...

      Posté par  (site web personnel) . Évalué à 2.

      ...et si tu es capable d'extraire ta clé:


      ....for line in fin_file :
      ........if not extraction_cle(line) in lines_to_remove :
      ............fout_file.write(line)


      [gaffe, j'avais oublié une indentation dans la ligne après celle du "if" dans mon post précédent.]

      Ca correspond à la proposition qui a été fait d'utiliser un hash en Perl (là j'utilise un set en Python). Je ne pense pas que tu puisses trouver plus rapide comme algo.

      Note: tout ça en considérant qu'il n'y a pas de problème de casse/marques diacritiques entre l'expression les clés dans F1 et celle dans f2.

      Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

      • [^] # Re: Si tu peux utiliser autre chose que le shell...

        Posté par  (site web personnel) . Évalué à 2.

        Pour extraction_cle, si tu poste un exemple, on pourra faire un bout de code.

        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

        • [^] # Re: Si tu peux utiliser autre chose que le shell...

          Posté par  . Évalué à 1.

          Ok, c'est gentil.
          Le fichier f1 est de la forme :
          ip: blablabla
          Le blabla peut etre de diverses formes.

          Le fichier f2 contient une liste d'adresse ip (une par ligne)

          • [^] # Re: Si tu peux utiliser autre chose que le shell...

            Posté par  (site web personnel) . Évalué à 2.

            Ajoute la fonction suivante:


            def extraction_cle(line) :
            ....return line.split(':')[0]


            Ou bien directement dans le test:

            ....for line in fin_file :
            ........if not line.split(':')[0] in lines_to_remove :
            ............fout_file.write(line)

            Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

            • [^] # Re: Si tu peux utiliser autre chose que le shell...

              Posté par  (site web personnel) . Évalué à 2.

              J'oubliais, s'il y a des problèmes de retours à la ligne qui resteraient dans les chaines suite à la lecture de f2, tu peux modifier un peu le chargement des clés:

              ....lines_to_remove = set( (i.strip() for i in open(fref) ) )


              Note au cas où: ça s'appelle avec :
              python remlines.py f1 f2 fsortie

              Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

              • [^] # Au final...

                Posté par  (site web personnel) . Évalué à 2.


                #!/bin/env python
                # -*- coding: ascii -*-

                def remlines(fin,fref,fout) :
                ....lines_to_remove = set( (i.strip() for i in open(fref)))
                ....fin_file = open(fin)
                ....fout_file = open(fout,"w")
                ....for line in fin_file :
                ........if not line.split(':')[0] in lines_to_remove :
                ............fout_file.write(line)
                ....fout_file.close()
                ....fin_file.close()

                if __name__ == "__main__" :
                ....import sys
                ....remlines(sys.argv[1],sys.argv[2],sys.argv[3])


                J'ai essayé avec f1:

                12.4.23.54: Un essai
                192.168.0.1:It is bad
                54.123.14.53:La y'a qq chose
                127.0.0.1:A retirer
                90.32.41.15:Et encore la c'est bon
                255.255.255.255:Non mais ca c'est nul
                32.435.124.23:Et ce c'est ok


                Et f2:

                192.168.0.1
                127.0.0.1
                255.255.255.255


                python remlines.py f1 f2 fout

                Dis nous ce que ça donne côté perfs sur tes gros fichiers.

                Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

  • # rien à voir avec le shell mais: sql

    Posté par  . Évalué à 2.

    et pourquoi pas une importation dans une base sql ?
    Avec les indexes et le delete from ... where... in(select... qui vont bien, ça pourrait prendre quelques secondes.

    ou encore plus jouissif, un trigger sur f2 qui détruit l'enregistrement dans f1 correspondant...

    ps: recommandé pour une utilisation répétées bien sûr

    • [^] # Re: rien à voir avec le shell mais: sql

      Posté par  . Évalué à 1.

      Oh la bonne idee.. J'avoue que je n'y avais pas pense..
      Apres un petit test tout bete (et deux jolis index), l'operation ne mets que 4 secondes :)
      C'est extremement efficace !!!!
      Merci donc de ta reponse

      PS: j'utilise une base SQL pour stocker d'autres donnees donc tout va bien.. mais si je ne l'avais pas.. le pb reste entier ;)

  • # Memory mapping

    Posté par  . Évalué à 1.


    J'ai essayé un grep -v -f f2 f1mais c'est encore pire.


    Et quid de l'option -mmap pour grep ? Il y avait déjà eu une astuce à ce propos: http://www.linuxfr.org/tips/269.html Cela vaut-il la peine d'être considéré ?

    Certes, effectuer les traitements grâce à MySQL semble élégant et impressionnant en terme de vitesse, cependant, si l'on considère aussi l'importation des données, auparavant, le temps total pour effectuer toutes les opérations est sans doute plus long, non ?

    • [^] # Re: Memory mapping

      Posté par  . Évalué à 1.

      Je pensais la meme chose au niveau de l'import.. Mais en faisant un load data infile.. hop hop hop en moins de 2 secondes le fichier est mangé :)
      Je ne connaissais pas l'option -mmap de grep mais malheureusement elle n'est pas dispo sous mon OS (OpenBSD)

Suivre le flux des commentaires

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