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

Posté par Kwiknclean le 28 octobre 2014 à 22:52. Licence CC By‑SA.

Étiquettes :

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 Zylabon le 28 octobre 2014 à 23:30. É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 lolop (site web personnel) le 29 octobre 2014 à 09:07. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
  - [^] # Re: Le type "set" ?
    
    Posté par barmic le 29 octobre 2014 à 09:10. É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 lolop (site web personnel) le 29 octobre 2014 à 13:34. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
      - [^] # Re: Le type "set" ?
        
        Posté par lolop (site web personnel) le 29 octobre 2014 à 14:07. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
      - [^] # Re: Le type "set" ?
        
        Posté par barmic le 29 octobre 2014 à 14:12. É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 lolop (site web personnel) le 29 octobre 2014 à 14:45. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
        
        [^] # Re: Le type "set" ?
        
        Posté par barmic le 29 octobre 2014 à 14:56. É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 lolop (site web personnel) le 29 octobre 2014 à 15:11. Évalué à 2.
        
        Désespérant.
        
        []
        
        Python 3 - Apprendre à programmer dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
        
        [^] # Re: Le type "set" ?
        
        Posté par lolop (site web personnel) le 29 octobre 2014 à 15:18. Évalué à 3. Dernière modification le 29 octobre 2014 à 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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
  - [^] # Re: Le type "set" ?
    
    Posté par Kwiknclean le 29 octobre 2014 à 16:41. É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 lolop (site web personnel) le 29 octobre 2014 à 18:37. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141

# En Python ?

Posté par feth le 28 octobre 2014 à 23:32. Évalué à 4. Dernière modification le 28 octobre 2014 à 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 :

https://docs.python.org/3/library/ipaddress.html (interne à Python !)

# Regexp::Assemble

Posté par barmic le 29 octobre 2014 à 00:43. É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 Zylabon le 29 octobre 2014 à 01:13. É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 lolop (site web personnel) le 29 octobre 2014 à 16:08. É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 dans l'écosystème Python → https://www.dunod.com/EAN/9782100809141
# Merci les mecs !

Posté par Kwiknclean le 29 octobre 2014 à 01:37. É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 BAud (site web personnel) le 29 octobre 2014 à 02:07. É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 :
  - en Rédaction
  - Participer en rédaction c'est facile !
- [^] # Re: Merci les mecs !
  
  Posté par barmic le 29 octobre 2014 à 09:06. Évalué à 4. Dernière modification le 29 octobre 2014 à 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 lolcat le 29 octobre 2014 à 03:10. É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 barmic le 29 octobre 2014 à 09:04. É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 palm123 (site web personnel) le 29 octobre 2014 à 08:22. Évalué à 5.

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

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

ウィズコロナ
- [^] # Re: explication sur les sets
  
  Posté par Kwiknclean le 29 octobre 2014 à 16:14. É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 palm123 (site web personnel) le 29 octobre 2014 à 17:29. Évalué à 3.
    
    Je vais envoyer un email à la NSA, comme ça on saura
    
    []
    
    comment on n'est pas dredi ?
    
    ウィズコロナ
    - [^] # Re: explication sur les sets
      
      Posté par palm123 (site web personnel) le 30 octobre 2014 à 14:32. É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.
      
      ウィズコロナ
# Je ne pensais pas que ma question ...

Posté par Kwiknclean le 29 octobre 2014 à 16:08. É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 …
- [^] # Re: Je ne pensais pas que ma question ...
  
  Posté par fearan le 30 octobre 2014 à 09:23. Évalué à 2.
  
  en même temps
  
  En gros j'aimerais savoir (en Python ou en Perl),
  
  Forcément, les deux religions vont s'affronter; un peu comme une rencontre entre témoin de jéhovah et des jedi…
  
  Il ne faut pas décorner les boeufs avant d'avoir semé le vent
  - [^] # Re: Je ne pensais pas que ma question ...
    
    Posté par Kwiknclean le 30 octobre 2014 à 21:50. Évalué à 1.
    
    Ce n'était pas du tout volontaire du tout pourtant …

Suivre le flux des commentaires

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