Forum Programmation.python [Résolu] Itertools générer les combinaisons une par une

Posté par  . Licence CC By‑SA.
Étiquettes :
2
26
déc.
2022

Bonjour le monde !
J'ai un petit problème très pythonesque à vous soumettre aujourd'hui.
J'ai codé un petit script qui me génère toutes les situations « gagnantes » au jeu de Marienbad.
Il génère des combinaisons de tas de jetons, et teste si elles sont gagnantes, et les montre à l'écran si oui.
Pour la génération des combinaisons, j'utilise itertools avec la fonction combinations_with_replacement().
Seulement, quand on commence à passer à des générations avec une quinzaine de tas pouvant aller jusqu'à 20 jetons, le nombre de combinaisons générées explose et remplit mes 4 Go de RAM avant de se faire tuer par l'OS.
Pour résoudre ce problème, il faudrait pouvoir tester les combinaisons au fur et à mesure qu'elles sont générées par itertools, et non pas quand il a fini de générer une fournée de combinaisons.
Quelqu'un aurait-il une idée sur la façon de procéder, sachant que le module itertools est écrit en C, mais il existe une version python dans les libs de Pypy ?

  • # Lister un itérateur

    Posté par  . Évalué à 3.

    Tu devrais essayer sans l'appel à list() ligne 42, le retour de combinations_with_replacement() est un itérateur, et le for devrait parcourir les items sans qu'il soit besoin de les générer tous au préalable.

    • [^] # Re: Lister un itérateur

      Posté par  . Évalué à 1.

      Merci !
      J'essaie ça tout de suite, mais normalement, ça devrait fonctionner, lentement mais quand même.

      L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

      • [^] # Re: Lister un itérateur

        Posté par  . Évalué à 2.

        Regarde également la doc du mot clé yield, qui peut te permettre de faire une loop sur une fonction itérative sans charger l’ensemble des données en mémoire.

        • [^] # Re: Lister un itérateur

          Posté par  . Évalué à 1.

          En effet, mais il sert seulement si tu crées une fonction qui retourne yield quelquechose.
          Dans mon cas, quelquechose est déjà retourné par la fonction combination_with_remplacement().
          yield peut être utile, mais pas ici.

          L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

    • [^] # Re: Lister un itérateur

      Posté par  . Évalué à 4.

      En regardant vite fait son script la première chose qu'il fait c'est rechercher le max donc en l'état il va avoir besoin de tout charger. Faudrait revoir l'évaluation pour qu'elle n'ai pas besoin de l'ensemble des données.

      https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

      • [^] # Re: Lister un itérateur

        Posté par  . Évalué à 1.

        Je pense que tu as mal compris le problème ou le code.
        Une combinaison n'est pas très grande, juste un tuple de quelques éléments, mais le nombre de combinaisons possibles est gigantesque !!!

        Et mon code évalue chaque combinaison une à une dans la fonction checkCombination(), qui prend en paramètre une unique combinaison. C'est là que je dois trouver le plus grand nombre du tuple (la combinaison) pour avoir la longueur de son équivalent binaire afin de savoir combien de fois boucler pour évaluer chaque décimale de chaque élément du tuple convertit en binaire.
        La solution est un peu sale, mais je ne pense pas qu'elle impacte beaucoup les performances.

        Le problème initial venait du fait que je convertissais un lot de combinaisons en liste avant de les passer à checkCombination(), et de ce fait, je chargeais en RAM un nombre incroyable de combinaisons.

        Mon code n'est peut-être pas très clair (normal pour un code), mais seules les deux premières fonctions sont importantes, les autre sont surtout là pour l'interface GUI et CLI et des options particulières.

        L'informatique n'est pas une science exacte, on n'est jamais à l'abri d'un succès

        • [^] # Re: Lister un itérateur

          Posté par  . Évalué à 3.

          Effectivement j'ai mal lu le code.

          https://linuxfr.org/users/barmic/journaux/y-en-a-marre-de-ce-gros-troll

Suivre le flux des commentaires

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