Bonjour, cliquez-ici pour vous inscrire et participer au forum.
  • Login:



+ Répondre à la discussion
Page 4 sur 4 PremièrePremière 4
Affichage des résultats 46 à 59 sur 59

nombres dont les chiffres sont tous différents [PYTHON]

  1. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Oui, vu que je n'arrive pas à dormir, ça marche bien avec des bitfields. 1ms pour les 1 à 100 000 et 150 ms pour les 10 milliards :

    Code:
    object UniqueBitfield extends App {
    
      val start = System.nanoTime()
      var count=0
      var i = 1
      while(i<11) {
        count += loop1(i)
        i += 1
      }
      val time = (System.nanoTime()-start)/1000000.0
      println(count)
      println(s"time=$time")
    
    
      def loop1(n: Int): Int = {
        var i = 1
        var count = 0
        while(i<10) {
          count += loop0(n-1, 1 << i)
          i += 1
        }
        count
      }
    
      def loop0(n: Int, used: Int): Int = {
        if(n == 0 ) 1
        else {
          var i = 0
          var current = 1
          var count = 0
          while (i < 10) {
            if((used & current) == 0) count += loop0(n - 1, used | current)
            current = current << 1
            i += 1
          }
          count
        }
      }
    }

    -----

     


    • Publicité



  2. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En C, ca va un peu plus vite : 80 ms pour les 10 milliards :

    Code:
    #include <stdio.h>
    
    int loop0(int n, short used)
    {
      if(n == 0) {
        return 1;
      }
      else {
        int count = 0;
        short current = 1;
        for(int i = 0; i<10; i++) {
          if((used & current) == 0) {
    	count += loop0(n - 1, current | used);
          }
          current <<= 1;
        }
        return count;
      }
    }
    
    int loop1(int n)
    {
      int count = 0;
      for(int i = 1; i<10; i++) {
        count += loop0(n-1, 1 << i);
      }
      return count;
    }
    
    int main(int argc, char **argv)
    {
      int count = 0;
      for(int i = 1; i<11; i++) {
        count += loop1(i);
      }
      printf("%d\n", count);
    }
     

  3. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    J'ai encore complexifiée ma fonction récursive pour atteindre 0.106ms
    Tu peux réessayer en affichant Stopwatch..ElapsedMilliseconds ? Parce que je n'obtiens pas les mêmes chiffres que toi. Je suis à 2 ms avec ton code.
     

  4. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En python, c'est beaucoup plus lent et pas vraiment plus rapide que le code simple avec les permutations : 1 min environ pour les 10 milliards.

    Code:
    def loop1(n):
        count = 0
        for i in range(1, 10):
            count += loop0(n-1, 1 << i)
        return count
    
    def loop0(n, used):
        if(n == 0):
            return 1
        else:
            current = 1
            count = 0
            for i in range(10):
                if((used & current) == 0):
                    count += loop0(n - 1, used | current)
                current = current << 1
            return count
    
    count=0
    for i in range(1, 11):
        count += loop1(i)
    print(count)
     

  5. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Une autre version, non optimale pour le temps, mais avec une tentative d'élégance pythonesque dans le code (pas forcément réussie... tout commentaire et amélioration bienvenue).


    Code:
    def nbperm(n, verbose=False):
        listefinale=[]
        for i in range(n):
            listefinale=listefinale+nbde(i+1)
        if verbose: print listefinale
        else: print len(listefinale)        
    
    def nbde(n=1, liste=[str(x+1) for x in range(9)]):
        if n>1: return nbde(n-1, successeur(liste))
        return liste      
    
    def successeur(liste):
        return[liste[x] + str(y) for x in range(len(liste)) for y in range(10) if liste[x].find(str(y)) == -1]
        
    nbperm(5, True)
    for i in range(5): nbperm(i+1)
    Dernière modification par Jiav ; 21/12/2017 à 16h38.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     


    • Publicité



  6. Jiav

    Date d'inscription
    juillet 2004
    Messages
    8 351

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    En poussant l'idée un peu plus loin:

    Code:
    def nbperm(n, verbose=False):
        if verbose: print mk_res(n)
        else: print len(mk_res(n))        
    
    def mk_res(n, letexte=[]):
        if n>1: return mk_res(n-1, mk_liste(n) + letexte)
        else: return mk_liste(n) + letexte 
    
    def mk_liste(n=1, liste=[str(x+1) for x in range(9)]):
        if n>1: return mk_liste(n-1, mk_next(liste))
        else: return liste      
    
    def mk_next(liste):
        return[liste[x] + str(y) for x in range(len(liste)) for y in range(10) if liste[x].find(str(y)) == -1]
        
    nbperm(3, True)
    for i in range(5): nbperm(i+1)
    Lisibilité meilleure, non?
    Dernière modification par Jiav ; 21/12/2017 à 17h50.
    The opposite of a deep truth may well be another deep truth. Information is physical.
     

  7. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Jiav Voir le message
    Lisibilité meilleure, non?
    Je ne suis pas assez "fluent" en python pour vraiment juger. Mais c'est propre en effet.
    Sinon, un collègue à qui j'ai posé la colle a fait la version permutations en Scala beaucoup plus élégant que moi :

    Code:
    def gen(n: Int) = (1 to n).flatMap("0123456789".combinations(_)).flatMap(_.permutations).filter(!_.startsWith("0"))
     

  8. Garion

    Date d'inscription
    janvier 2005
    Localisation
    Hérault
    Âge
    47
    Messages
    2 503

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par pm42 Voir le message
    Tu peux réessayer en affichant Stopwatch..ElapsedMilliseconds ? Parce que je n'obtiens pas les mêmes chiffres que toi. Je suis à 2 ms avec ton code.
    C'est fait, il me donne 0, je suis avec Delphi 10.1 Berlin compilé en mode release (configuration par défaut du mode release), et exécuté hors debugger. Mon PC même s'il a 9 ans, est pas trop mal vu qu'il est overclocké à 4Ghz.
     

  9. Garion

    Date d'inscription
    janvier 2005
    Localisation
    Hérault
    Âge
    47
    Messages
    2 503

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par pm42 Voir le message
    En C, ca va un peu plus vite : 80 ms pour les 10 milliards :
    Je suis battu, 125ms pour arriver jusqu'à 10milliards.
    Je viens de tenter une compilation en 64 bits qui utilise mieux les instruction SSE, et je tombe à 120ms.
    Les compilateurs C sont mieux optimisé pour les processeurs récents, ils tirent mieux parti du cache et des instructions des processeurs modernes.
    Je vais convertir ton code C en Delphi pour voir si c'est l'algo ou le compilateur qui fait la différence.
     

  10. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Citation Envoyé par Garion Voir le message
    C'est fait, il me donne 0, je suis avec Delphi 10.1 Berlin compilé en mode release (configuration par défaut du mode release), et exécuté hors debugger. Mon PC même s'il a 9 ans, est pas trop mal vu qu'il est overclocké à 4Ghz.
    Ok. Je suis en Delphi 10.2 et à 3.5 Ghz. Ceci dit, 125 ms pour arriver à 10 milliards, c'est déjà pas mal du tout.
     

  11. Garion

    Date d'inscription
    janvier 2005
    Localisation
    Hérault
    Âge
    47
    Messages
    2 503

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Hum, j'ai un problème avec ton code C (mais je suis proche de l'ignare en C)
    D'une part, il ne fait qu'énumérer les possibilités sans les générer. D'autre part, le count donné ne correspond pas à ce qu'obtiens en Delphi.
    J'ai une incertitude avec la ligne
    count += loop0(n-1, 1 << i);
    Soit il faut que j'approfondisse (mais je n'ai pas le temps ce soir) car j'ai une mauvaise compréhension du code C, soit il y a un truc louche.
    Mais j'avoue que je n'ai pas essayé de comprendre l'algo, juste essayé de le convertir.
    Je verrai quand j'aurai le temps.
     

  12. pm42

    Date d'inscription
    juillet 2015
    Messages
    4 200

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Si je génère, je vais être un peu plus lent mais ce n'est pas dur non plus. C'est juste un poil chiant et là, j'ai la flemme parce que je vais aller dormir
    Et s'il y a une erreur, c'est possible : j'ai codé ça pendant des pointes d'insomnies dues à une rhino.
    Déjà qu'en temps normal, je ne suis pas infaillible mais là...

    Mais le principe est de faire une 1ère boucle pour le 1er chiffre qui va de 1 à 9 (loop1) et qui ensuite appelle une autre boucle loop0 qui elle fait le chiffre suivant de 0 à 9.
    loop0 continue comme ça.
    Et pour ne jamais utiliser 2 fois le même chiffre, j'utilise un bitfield de 16 bits où je mets à 1 le bit correspondant à ceux déjà pris. Donc si j'ai utilisé 0 et 2, je passe 0000000000000101.

    C'est encore optimisable mais après 3 variantes de l'algo dans 3 langages, je vais passer à autre chose.
    Dernière modification par pm42 ; 21/12/2017 à 23h33.
     

  13. Garion

    Date d'inscription
    janvier 2005
    Localisation
    Hérault
    Âge
    47
    Messages
    2 503

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Edit... Erreur (confondu décalage à gauche et décalage à droite).
    Je comprend mieux maintenant.
    Dernière modification par Garion ; 21/12/2017 à 23h38.
     

  14. Garion

    Date d'inscription
    janvier 2005
    Localisation
    Hérault
    Âge
    47
    Messages
    2 503

    Re : nombres dont les chiffres sont tous différents [PYTHON]

    Et grosso modo, la différence de stratégie, c'est vaut-il mieux tout générer tout et tester un par un avec ton algo optimisé (ta stratégie) ou ne générer que les nombres valides (ma stratégie).
    Ne sachant pas, je vais tester les deux stratégies car ça m'intrigue sur ce cas.
    (putain, je passe une bonne partie de mon temps sur des profiler pour optimiser la performance du code dans mon boulot, j'ai même du écrit du code natif en assembleur SSE3 pour optimiser les choses, je fais de la simulation énergétique des bâtiments).
    Dernière modification par Garion ; 21/12/2017 à 23h52.
     


    • Publicité







Sur le même thème :


    301 Moved Permanently

    301 Moved Permanently


    nginx/1.2.1



 

Discussions similaires

  1. [Energie] Lecture optique de chiffres/nombres
    Par Bientzou dans le forum Électronique
    Réponses: 7
    Dernier message: 11/02/2016, 10h03
  2. Chiffres différents par digits, 74SL47
    Par XDamienX007 dans le forum Électronique
    Réponses: 5
    Dernier message: 16/02/2015, 22h33
  3. Tous les nombres entiers sont égaux.
    Par Sund dans le forum Science ludique : la science en s'amusant
    Réponses: 9
    Dernier message: 26/06/2014, 22h08
  4. nombres en 4 chiffres
    Par tontonMamar dans le forum Science ludique : la science en s'amusant
    Réponses: 3
    Dernier message: 13/03/2010, 23h32
  5. Chiffres et nombres
    Par Gu1ll4um3 dans le forum TPE / TIPE et autres travaux
    Réponses: 11
    Dernier message: 30/10/2008, 11h52