Forum Programmation.perl Algo ; Evitez les doubles "boucles" ?

Posté par (page perso) . Licence CC by-sa
4
28
oct.
2014

Salut les regex !

J'ai souvent à parser des gros fichiers en tentant de matcher par rapport à une liste.
Du coup je me retrouve souvent à faire des doubles boucles bien dégueulasses et bien gourmandes en ressources.

En gros j'aimerais savoir (en Python ou en Perl), comment faire ça de manière en plus élégante et moins "brutale", de préférence en évitant d'aller charger des modules externes ça serait le top, pis si ça pouvait rester lisible aussi, parce que je vous connais les brutos du Perl …

    @mon_log = open(LOG,</mon/chemin/log);
    @ma_grosse_liste_IP;

    foreach $ligne @mon_log
    {
       foreach $IP @ma_grosse_liste_IP
       {
         //Match de mon ip dans la log et traitement ...
       }
    }

Merci à vous.

  • # Le type "set" ?

    Posté par . Évalué à 5.

    J'y connais rien en perl, mais en python ya ça :

    https://docs.python.org/3/library/stdtypes.html#frozenset

    Ça te ferait passer de O(taille_ficher * taille_liste) à O(taille_liste + taille_fichier), en supposant que ce soit implémenté avec une table de hash (ils font chier à pas mettre les complexité).

    Please do not feed the trolls

    • [^] # Re: Le type "set" ?

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

      Je pertinente, à condition que sa grosse liste IP tienne en mémoire.

      Une fois chargée en mémoire la liste IP sous forme de set ou de frozenset, la recherche d'une IP de log dans l'ensemble est en O(1) — les set utilisent des tables de hachage comme les dict (redimensionnables pour limiter les collisions). Cf http://stackoverflow.com/questions/3949310/how-is-set-implemented

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

      • [^] # Re: Le type "set" ?

        Posté par . Évalué à 4.

        la recherche d'une IP de log dans l'ensemble est en O(1)

        Comment tu fais ça ?

        Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

        • [^] # Re: Le type "set" ?

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

          Cf le lien que j'ai donné, quand ça collissionne, ils prennent une table plus large.
          Et en plus il y a un genre de sel ajouté il y a quelques temps pour éviter les attaques via des requêtes web avec des chaines forgées qui donnaient des clés identiques.

          +il y a le lien vers les sources si tu as du temps.

          Mais, même en O(log(n)), ça serait plus rapide que du O(n/2) d'une recherche séquentielle.

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

          • [^] # Re: Le type "set" ?

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

            Faudrait voir dans les détails comment ils se débrouillent (http://www.laurentluce.com/posts/python-dictionary-implementation/ => ils redimensionnent dès qu'une table de hachage est pleine aux deux tiers)… un petit test, en utilisant les dictionnaire installés:

            #!/usr/bin/python3
            # -*- encoding: utf-8 -*-
            
            import pprint
            
            # Fichier 1.5Mo, lu en une seule fois pour pouvoir reboucler dessus.
            with open("/usr/share/dict/french", encoding='utf-8') as f:
                mots = f.read().splitlines()
            
            print("Nombre de mots:", len(mots))
            smots = set(mots)
            
            # Fichier 917K. Lu en une seule fois, mais on pourrait faire au fur et à mesure.
            with open("/usr/share/dict/american-english", encoding='utf-8') as f:
                eng = f.read().splitlines()
            
            # Comptage des mots anglais présents dans le français.
            cpt = 0
            for m in eng: 
                if m in smots:
                    cpt += 1
            
            print("Mots communs:", cpt)

            Me donne:

            pointal@soupir:~$ time python3 collisions.py 
            Nombre de mots: 139719
            Mots communs: 6139
            
            real    0m0.165s
            user    0m0.144s
            sys     0m0.020s

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

          • [^] # Re: Le type "set" ?

            Posté par . Évalué à 4.

            Donc dans "la recherche d'une IP de log dans l'ensemble est en O(1)", tu ignore la partie extraction des IP de ton log. C'est pourtant, à mon avis, ce qui est le plus couteux.

            Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

            • [^] # Re: Le type "set" ?

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

              Tu cherches quoi ? Tu as quelque chose à proposer sans avoir d'info sur la forme des lignes de logs?

              Je n'ignore rien, l'extraction de l'IP du log peut être coûteuse, sa recherche en O(n) l'est au moins autant… sinon beaucoup plus s'il y a beaucoup d'adresses dans sa "grosse liste d'addresses IP". S'il a quelques milliers d'adresses IP dans sa liste, alors une recherche séquentielle est énormément plus coûteuse qu'une opération d'extraction.

              Mais si Kwiknclean donne la forme de ses logs, il y aura probablement quelqu'un pour l'aider à écrire la regexp optimale qui va bien (peut-être pas moi sur les regexp).

              J'ai modifié l'algo pour comparer la recherche en séquentielle (ie. dans la liste) à la recherche dans le set. Pour rappel, l'équivalent de la "gosse liste d'IPs" fait ~140000 entrées.

              #!/usr/bin/python3
              # -*- encoding: utf-8 -*-
              
              import pprint
              import time
              
              # Fichier 1.5Mo, lu en une seule fois pour pouvoir reboucler dessus.
              with open("/usr/share/dict/french", encoding='utf-8') as f:
                  mots = f.read().splitlines()
              
              print("Nombre de mots:", len(mots))
              smots = set(mots)
              
              # Fichier 917K. Lu en une seule fois, mais on pourrait faire au fur et à mesure.
              with open("/usr/share/dict/american-english", encoding='utf-8') as f:
                  eng = f.read().splitlines()
              
              # Comptage des mots anglais présents dans le français.
              # En utilisant la liste de mots:
              t = time.time()
              cpt = 0
              for m in eng: 
                  if m in mots:
                      cpt += 1
              temps = time.time() - t
              print("Mots communs:", cpt, "en", temps, "par recherche dans la liste.")
              
              # En utilisant le set de mots:
              t = time.time()
              cpt = 0
              for m in eng: 
                  if m in smots:
                      cpt += 1
              temps = time.time() - t
              print("Mots communs:", cpt, "en", temps, "par recherche dans le set.")

              Et ça donne (temps en secondes):

              pointal@soupir:~$ python3 collisions.py 
              Nombre de mots: 139719
              Mots communs: 6139 en 350.167192697525 par recherche dans la liste.
              Mots communs: 6139 en 0.022248506546020508 par recherche dans le set.

              Sans commentaire.

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

              • [^] # Re: Le type "set" ?

                Posté par . Évalué à 4.

                Tu as quelque chose à proposer sans avoir d'info sur la forme des lignes de logs?

                Oui lis les autres commentaires…

                Je n'ignore rien, l'extraction de l'IP du log peut être coûteuse, sa recherche en O(n) l'est au moins autant… sinon beaucoup plus s'il y a beaucoup d'adresses dans sa "grosse liste d'addresses IP". S'il a quelques milliers d'adresses IP dans sa liste, alors une recherche séquentielle est énormément plus coûteuse qu'une opération d'extraction.

                Tu enfonce des portes ouvertes. Mais une autre possibilité pourrait être d'utiliser un tas pour ça. Si ces IPs recherchées sont rare dans les log (ce qui est potentiellement le cas), un bloom filter sera plus efficace encore. Mais ça reste très probablement de la microoptimisation parce que ce qui coute c'est l'extraction. Tu parle d'une recherche séquentielle sans résoudre le problème de l'extraction séquentielle.

                C'est un peu comme si tu disais qu'il peut stocker les IP (v4) sous forme de 4 octets plutôt qu'en chaine de caractères qui peut faire 15 octets. Et montrer (benchmark à l'appuie) que pour 1000 ip : 1000*4 < 1000*15.

                Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

                • [^] # Re: Le type "set" ?

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

                  Désespérant.

                  []

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

                  • [^] # Re: Le type "set" ?

                    Posté par (page perso) . Évalué à 3. Dernière modification le 29/10/14 à 15:22.

                    Correction, Regexp::Assemble est très intéressant. Juste vérifier qu'il n'y a pas de matchs incorrects (ie. connaître la forme/le type d'info dans les logs - qu'on ait pas plusieurs champs d'IP où il faut en ignorer certaines, sinon le pré-traitement fait perdre pas mal vis à vis de la solution).

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

      • [^] # Re: Le type "set" ?

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

        La liste d'IP n'est pas monstrueuse en fait ; une petite centaine, en forte croissance tous les mois toutefois.

        En revanche le fichier lui fait un peu plus mal 1Go / jour en forte croissance, traitée tous les jours heureusement, c'est la log Nagios, la regex elle est triviale, l'Ip est toujours sur la deuxième ou troisième colonne, en fait un split suffit.

        Question subsidiaire :
        Dans mon exemple je boucle en premier sur les lignes de mon fichier.

        Y aurait une différence notable si je commençais par boucler plutôt sur ma liste d'IP, ou ça n'a aucune incidence ?

        • [^] # Re: Le type "set" ?

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

          Si tu utilises un set (ou frozenset), tu ne boucles plus sur la liste d'IPs. Il n'y a plus qu'une boucle sur ton fichier de log, le test de présence de l'IP de log dans ta collection est juste une opération ~simple~¹.

          Il y a sûrement un équivalent en Perl au set Python, transforme ta liste d'IP dans cet outil, et déjà tu gagneras beaucoup sans trop toucher ton code.

          voir avec le Regexp::Assemble de M.Barrett - comme tu es déjà en Perl…

          ¹ En Python l'opérateur in appliqué à une liste fait comme toi, une boucle sur les éléments à la recherche de celui que tu testes. Par contre, l'opérateur in appliqué à un set/frozenset c'est calcul de la clé de hachage si elle n'est pas déjà présente, mapping de celle-ci à l'index dans la table de répartition des clés, et identification (ou non) de la présence de ce que tu recherches (avec éventuellement parcours de qq valeurs s'il y a des collisions - cf un des autres commentaires et les liens accompagnant).

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

  • # En Python ?

    Posté par (page perso) . Évalué à 4. Dernière modification le 28/10/14 à 23:34.

    En Python. Je sais pas ce que je peux t'apprendre ou pas. Par contre ton énoncé est flou :)

    # je fais l'hypothèse que la liste ressemble à ça :
    # en fait je fais un set (non ordonné), c'est beaucoup plus adapté qu'une liste
    mon_gros_set_dIP = {'192.168.1.1', '192.168.1.2'}  
    
    def matching_ips(logfile, ip_set):
        with open(logfile) as handle:
            for ip_line in handle:
                # je fais l'hypothèse qu'il y a une adresse IP et rien d'autre sur chaque ligne du fichier.
                if ip_line.strip() in mon_gros_set_dIP: # normalisation minimale
                    yield ip_line
    
    for match in matching_ips('/mon/chemin/log', mon_gros_set_dIP):
        print(match)

    Note : il y a au moins une bonne bibliothèque correcte pour gérer les adresses IP en Python :

  • # Regexp::Assemble

    Posté par . Évalué à 7.

    Tout se perl ! Tu peut simplifier les choses avec Regexp::Assemble.

    Tu dois pouvoir faire quelque chose comme ça :

    my $ra = Regexp::Assemble->new;
    $ra->add( $_ ) for @ips;
    my $re = $ra->re();
    
    while (<>) {
        print if /$re/;
    }

    Ce qui fait une complexité en O(n+m) avec n ip et m lignes.

    Tu peut voir un bench là : http://articles.mongueurs.net/magazines/perles/perles-29.html

    Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

    • [^] # Re: Regexp::Assemble

      Posté par . Évalué à -4.

      Il est rigolo ton lien :

      Lassé du spam et des virus qui engorgeaient son serveur STMP, et constatant que nombre d'entre eux provenaient d'adresses de connexion ADSL chez des particuliers (probablement infestés de virus et de chevaux de Troie), David Landgren a pris des mesures radicales

      « Lassé des problèmes sociaux causé par les inégalité, et constatant que nombre des richesses étaient accaparée par des gens d'origine juive (probablement parce qu'il faut bien être originaire de quelque chose), le parti nazi a pris des mesures radicales »

      Please do not feed the trolls

    • [^] # Re: Regexp::Assemble

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

      Trouvé un outil similaire à Regexp::Assemble en Python (ça peut toujours servir):
      https://bitbucket.org/haypo/hachoir/wiki/hachoir-regex

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

  • # Merci les mecs !

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

    On fait du Python et du Perl dans la boite au choix (ils sont sympas ils nous laisse décider selon les périmètres).

    Python j'trouve ça sympa mais ce manque de parenthèses et d'accolades ça me trouble, puis je fais très peu de POO.

    Malgré tout Perl j'en démords pas même après toutes ces années, ces @,$, $_
    je les adore.

    D'ailleurs pourquoi on a plus de niouzes sur les nouvelles versions du langage sur linuxfr ?

    Ca m'ennuie un peu d'utiliser un paquet CPAN quand même je voudrais proposer mon script à d'autre, mais ça m'a l'air rudement efficace.

    Y a moyen d'ailleurs de "packager" des modules pour augmenter la portabilité ?

    • [^] # Re: Merci les mecs !

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

      D'ailleurs pourquoi on a plus de niouzes sur les nouvelles versions du langage sur linuxfr ?

      cela ne tient qu'à toi, cf. les appels récents à participation :

    • [^] # Re: Merci les mecs !

      Posté par . Évalué à 4. Dernière modification le 29/10/14 à 09:08.

      Ça m'ennuie un peu d'utiliser un paquet CPAN quand même je voudrais proposer mon script à d'autre, mais ça m'a l'air rudement efficace.

      Tu peut faire de la détection de module, avoir un message d'alerte si le module n'est pas présent et utiliser comme moyen dégradé une combinaison de regexp à toi (un join avec "\|" par exemple).

      Après il faut voir les volumes que tu as. Si tu as peu d'IP le module ne t'apportera pas de grosses optimisations.

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # En python ...

    Posté par . Évalué à 3.

    Si j'étais toi je ferai ça :

    sortir toutes les ip de ton log, ce qui se fait très bien avec une expression régulière.
    Puis regarder en python par exemple si ta liste d'IP match avec le module set.
    Tu peux faire des opérations sur les ensembles facilement. D'ailleurs un des commentaires dit la même chose.
    Si tu veux éviter les boucles, le mot clé in est pour toi. Il permet de vérifier qu'un élément appartient à une ligne sans la parser entièrement. après voir la librairie standard, tu as certainement plein de façons pour faire ce que tu veux.

    • [^] # Re: En python ...

      Posté par . Évalué à 5.

      Ça me semble contre performant. Ça coute la construction de tes 2 ensemble plus l'intersection entre les deux, alors que tu peut filtrer déjà sur lors de la création de ton second ensemble (celui des ip du log). Oui les ensembles c'est très performants, mais c'est pas pour ça que c'est toujours pertinent (en l'occurrence je ne vois pas comment ça peut l'être).

      Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)

  • # explication sur les sets

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

    http://sametmax.com/ce-que-vous-ne-saviez-pas-sur-les-collections-en-python/

    http://sametmax.com/le-sourire-du-jour/

    If you choose open source because you don't have to pay, but depend on it anyway, you're part of the problem.evloper) February 17, 2014

    • [^] # Re: explication sur les sets

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

      Rien à voir mais : très sympa ta carte DDOS dans ta signature, on a cherché cet après midi avec un collègue à quoi pouvait correspondre géographiquement l'île qui semble bien active au Sud du pacifique face à l'Argentine …

      Notre dernière hypothèse à la louche s'est arrêtée sur l'île de Bouvet … un caillou gelé de 40Km sans habitants … la NSA a mis un data-center dessus ou quoi ?

      • [^] # Re: explication sur les sets

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

        Je vais envoyer un email à la NSA, comme ça on saura

        []

        comment on n'est pas dredi ?

        If you choose open source because you don't have to pay, but depend on it anyway, you're part of the problem.evloper) February 17, 2014

        • [^] # Re: explication sur les sets

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

          Je pense que plein de spammeurs prennent des .bv (pour Bouvet) et qu'il n'y a personne sur l'île, d'ailleurs la NSA ne m'a pas répondu.

          If you choose open source because you don't have to pay, but depend on it anyway, you're part of the problem.evloper) February 17, 2014

  • # Je ne pensais pas que ma question ...

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

    … déchainerait autant les passions.

    Du calme les mecs ne vous emballez pas ;)
    Et merci pour TOUTES vos propositions et manières de faire.

    Pour situer un peu mieux le contexte, en fait il s'agit d'aller "filtrer" la log quotidienne Nagios qui pèse environ 1 Go ! en éliminant les lignes qui contiennent une liste d'IP donnée (une petite centaine je dirais), pour régénérer le fichier de log dépourvus des notifications de ces IP "parasites" avant traitement par un logiciel maison.

    Enfin d'une manière général j'ai souvent ce type de "filtrage" à réaliser sur des log bien verboses, vsftp, squid, nagios ..

    Donc oui les ensembles o(Ip * Nb Lignes) sont du genre très très gourmands …

Suivre le flux des commentaires

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