Comment rendre ce bloc de code python court et efficace

Question

Je suis totalement novice en programmation et en python. Je résolvais un problème. J'ai trouvé la solution mais cela semble trop lent.

     if n % 2 == 0 and n % 3 == 0 and\
       n % 4 == 0 and n % 5 == 0 and\
       n % 6 == 0 and n % 7 == 0 and\
       n % 8 == 0 and n % 9 == 0 and\
       n % 10 == 0 and n % 11 == 0 and\
       n % 12 == 0 and n % 13 == 0 and\
       n % 14 == 0 and n % 15 == 0 and\
       n % 16 == 0 and n % 17 == 0 and\
       n % 18 == 0 and n % 19 == 0 and\
       n % 20 == 0:
 

C'est le code qui permet de vérifier si n est divisible par tous les nombres de 2 à 20 ou non.

Comment je peux le rendre court et efficace.

Answer 1

Il y a un compromis entre la courte et efficace.

Le Court chemin est - if all(n % i == 0 for i in range(2, 21)):

L' Efficace façon est d'avis que des choses comme n % 20 == 0 aussi dire qu' n % f == 0 où f est un facteur de 20. Par exemple, vous pouvez déplacer n % 2 == 0. Si vous finirez avec moins de comparaisons qui sera exécuté plus rapidement. En faisant cela, vous remarquerez un modèle et vous remarquerez que l' ensemble de la déclaration réduit à l' if n % 232792560 == 0! Mais qui a désormais profondément ancrée de la de 20 dans il sera donc difficile de détricote si vous avez besoin d'une autre limite supérieure.

Vous voyez donc que l' efficacité chemin n'est pas très facile à lire et à maintenir. Afin de choisir celui qui convient le mieux à vos exigences.

Answer 2

Il ya une façon plus intelligente de le faire. Si n est divisible par tous les entiers in range(1, 21), alors il doit être un multiple du plus petit commun multiple de ces entiers.

Vous pouvez calculer le PPCM de un ensemble de nombres progressivement, en utilisant le PGCD (plus grand commun diviseur). Vous pouvez importer le pgcd fonction de l' fractions module, ou de mettre en œuvre directement dans votre code.

def gcd(a, b):
    ''' Greatest Common Divisor '''
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    ''' Least Common Multiple '''
    return a * b // gcd(a, b)

# Compute the LCM of range(1, 21)
n = 2
for i in range(3, 21):
    n = lcm(n, i)

lcm20 = n
print('LCM =', lcm20)
#test 
for i in range(1, 21):
    print(i, lcm20 % i)

sortie

LCM = 232792560
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 0

Maintenant, pour tester si un nombre n est divisible par tous les nombres est range(1, 21) il vous suffit de faire

n % lcm20 == 0

ou le code de la constante dans votre script:

# 232792560 is the LCM of 1..20
n % 232792560 == 0

---

Anton Sherwood souligne dans son commentaire, nous pouvons accélérer le processus de trouver le nécessaire LCM en prenant juste le PPCM de la moitié supérieure de la gamme. Cela fonctionne parce que chaque nombre dans la moitié inférieure de la gamme est un diviseur d'un nombre dans la moitié supérieure de la gamme.

Nous pouvons améliorer la vitesse encore plus loin dans la paroi du PGCD et PPCM des calculs, plutôt que d'appeler des fonctions pour effectuer ces opérations. Python appels de fonction sont sensiblement plus lent que le C de la fonction d'appels en raison de l'extra frais généraux impliqués.

Yakk mentionne une approche alternative pour trouver le nécessaire LCM: calculer le produit de la prime pouvoirs dans la gamme. C'est assez rapide si la plage est assez grande (environ 40), mais pour les petits numéros de la simple LCM boucle est plus rapide.

Ci-dessous quelques - timeit code qui compare la vitesse de ces différentes approches. Ce script s'exécute sur Python 2 et 3, je l'ai testé sur la version 2.6 de Python et Python 3.6. Il utilise une liste des premiers de la fonction par Robert William Hanks pour mettre en œuvre Yakk de la suggestion. J'ai modifié Robert du code légèrement pour le rendre compatible avec Python 3. Je suppose qu'il y a peut être un moyen plus efficace de trouver le premier des pouvoirs; si oui, je voudrais le voir. :)

Je l'ai mentionné plus tôt qu'il y est un PGCD de fonction dans l' fractions module. J'ai fait quelques tests de temps avec elle, mais c'est nettement plus lent que mon code. Sans doute parce qu'il ne la vérification des erreurs sur les arguments.

#!/usr/bin/env python3

''' Least Common Multiple of the numbers in range(1, m)

    Speed tests

    Written by PM 2Ring 2016.08.04
'''


from __future__ import print_function
from timeit import Timer
#from fractions import gcd

def gcd(a, b):
    ''' Greatest Common Divisor '''
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    ''' Least Common Multiple '''
    return a * b // gcd(a, b)

def primes(n):
    ''' Returns a list of primes < n '''
    # By Robert William Hanks, from https://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lcm_range_PM(m):
    ''' The LCM of range(1, m) '''
    n = 1
    for i in range(2, m):
        n = lcm(n, i)
    return n

def lcm_range_AS(m):
    ''' The LCM of range(1, m) '''
    n = m // 2
    for i in range(n + 1, m):
        n = lcm(n, i)
    return n

def lcm_range_fast(m):
    ''' The LCM of range(1, m) '''
    n = m // 2
    for i in range(n + 1, m):
        a, b = n, i
        while b:
            a, b = b, a % b
        n = n * i // a
    return n

def lcm_range_primes(m):
    n = 1
    for p in primes(m):
        a = p
        while a < m:
            a *= p
        n *= a // p
    return n

funcs = (
    lcm_range_PM,
    lcm_range_AS,
    lcm_range_fast,
    lcm_range_primes
)

def verify(hi):
    ''' Verify that all the functions give the same result '''
    for i in range(2, hi + 1):
        a = [func(i) for func in funcs]
        a0 = a[0]
        assert all(u == a0 for u in a[1:]), (i, a)
    print('ok')

def time_test(loops, reps):
    ''' Print timing stats for all the functions '''
    timings = []
    for func in funcs:
        fname = func.__name__
        setup = 'from __main__ import num, ' + fname
        cmd = fname + '(num)'
        t = Timer(cmd, setup)
        result = t.repeat(reps, loops)
        result.sort()
        timings.append((result, fname))

    timings.sort()
    for result, fname in timings:
        print('{0:16} {1}'.format(fname, result))

verify(500)

reps = 3
loops = 8192
num = 2
for _ in range(10): 
    print('\nnum = {0}, loops = {1}'.format(num, loops))
    time_test(loops, reps)
    num *= 2
    loops //= 2

print('\n' + '- ' * 40)

funcs = (
    lcm_range_fast,
    lcm_range_primes
)

loops = 1000
for num in range(30, 60):
    print('\nnum = {0}, loops = {1}'.format(num, loops))
    time_test(loops, reps)

sortie

ok

num = 2, loops = 8192
lcm_range_PM     [0.013914467999711633, 0.01393848999941838, 0.023966414999449626]
lcm_range_fast   [0.01656803699916054, 0.016577592001340236, 0.016578077998929075]
lcm_range_AS     [0.01738608899904648, 0.017602848000024096, 0.01770572900022671]
lcm_range_primes [0.0979132459997345, 0.09863009199943917, 0.10133290699923236]

num = 4, loops = 4096
lcm_range_fast   [0.01580070299860381, 0.01581421999981103, 0.016406731001552544]
lcm_range_AS     [0.020135083001150633, 0.021132826999746612, 0.021589830999801052]
lcm_range_PM     [0.02821666900126729, 0.029041511999821523, 0.036708851001094445]
lcm_range_primes [0.06287289499960025, 0.06381634699937422, 0.06406087200048205]

num = 8, loops = 2048
lcm_range_fast   [0.015360695999333984, 0.02138442599971313, 0.02630166100061615]
lcm_range_AS     [0.02104746699842508, 0.021742354998423252, 0.022648989999652258]
lcm_range_PM     [0.03499621999981173, 0.03546843599906424, 0.042924503999529406]
lcm_range_primes [0.03741390599861916, 0.03865244000007806, 0.03959638999913295]

num = 16, loops = 1024
lcm_range_fast   [0.015973221999956877, 0.01600381199932599, 0.01603960700049356]
lcm_range_AS     [0.023003745000096387, 0.023848425998949097, 0.024875303000953863]
lcm_range_primes [0.028887982000014745, 0.029422679001072538, 0.029940758000520873]
lcm_range_PM     [0.03780223299872887, 0.03925949299991771, 0.04462484900068375]

num = 32, loops = 512
lcm_range_fast   [0.018606906000059098, 0.02557359899947187, 0.03725786200084258]
lcm_range_primes [0.021675119000065024, 0.022790905999499955, 0.03934840099827852]
lcm_range_AS     [0.025330593998660333, 0.02545427500081132, 0.026093265998497372]
lcm_range_PM     [0.044320442000753246, 0.044836185001258855, 0.05193238799984101]

num = 64, loops = 256
lcm_range_primes [0.01650579099987226, 0.02443148000020301, 0.033489004999864846]
lcm_range_fast   [0.018367127000601613, 0.019002625000211992, 0.01955779200034158]
lcm_range_AS     [0.026258470001266687, 0.04113643799973943, 0.0436801750001905]
lcm_range_PM     [0.04854909000096086, 0.054864030998942326, 0.0797669980001956]

num = 128, loops = 128
lcm_range_primes [0.013294352000229992, 0.013383581999732996, 0.024317635999977938]
lcm_range_fast   [0.02098568399924261, 0.02108044199849246, 0.03272008299973095]
lcm_range_AS     [0.028861763999884715, 0.0399744570004259, 0.04660961700028565]
lcm_range_PM     [0.05302166500041494, 0.059346372001527925, 0.07757829000001948]

num = 256, loops = 64
lcm_range_primes [0.010487794999789912, 0.010514846000660327, 0.01055656300013652]
lcm_range_fast   [0.02619308099929185, 0.02637610199963092, 0.03755473099954543]
lcm_range_AS     [0.03422451699952944, 0.03513622399987071, 0.05206341099983547]
lcm_range_PM     [0.06851765200008231, 0.073690847000762, 0.07841700100107118]

num = 512, loops = 32
lcm_range_primes [0.009275872000216623, 0.009292663999076467, 0.009309271999882185]
lcm_range_fast   [0.03759837500001595, 0.03774761099884927, 0.0383951439998782]
lcm_range_AS     [0.04527828100071929, 0.046646228000099654, 0.0569303670017689]
lcm_range_PM     [0.11064135100059502, 0.12738902800083451, 0.13843623499997193]

num = 1024, loops = 16
lcm_range_primes [0.009248070000467123, 0.00931658900117327, 0.010279963000357384]
lcm_range_fast   [0.05642254200029129, 0.05663530499987246, 0.05796714499956579]
lcm_range_AS     [0.06509247900066839, 0.0652738099997805, 0.0658949799999391]
lcm_range_PM     [0.11376448099872505, 0.11652833600055601, 0.12083648199950403]

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

num = 30, loops = 1000
lcm_range_fast   [0.03275446999941778, 0.033530079999763984, 0.04002811799909978]
lcm_range_primes [0.04062690899991139, 0.040886697999667376, 0.04130547800014028]

num = 31, loops = 1000
lcm_range_fast   [0.03423191600086284, 0.039976395999474335, 0.04078094900069118]
lcm_range_primes [0.04053011599899037, 0.04140578700025799, 0.04566663300101936]

num = 32, loops = 1000
lcm_range_fast   [0.036124262000157614, 0.036700047998238006, 0.04392546200142533]
lcm_range_primes [0.042666604998885305, 0.04393434200028423, 0.05142524700022477]

num = 33, loops = 1000
lcm_range_fast   [0.03875456000059785, 0.03997290300139866, 0.044469664000644116]
lcm_range_primes [0.04280027899949346, 0.0437891679994209, 0.04381238600035431]

num = 34, loops = 1000
lcm_range_fast   [0.038203157999305404, 0.03937257799952931, 0.04531203700025799]
lcm_range_primes [0.043273317998682614, 0.043349457999283914, 0.04420187600044301]

num = 35, loops = 1000
lcm_range_fast   [0.04228670399970724, 0.04346491300020716, 0.047442203998798504]
lcm_range_primes [0.04332462999991549, 0.0433610400014004, 0.04525857199951133]

num = 36, loops = 1000
lcm_range_fast   [0.04175829099949624, 0.04217126499861479, 0.046840714998324984]
lcm_range_primes [0.04339772299863398, 0.04360795700085873, 0.04453475599984813]

num = 37, loops = 1000
lcm_range_fast   [0.04231068799890636, 0.04373836499871686, 0.05010528200000408]
lcm_range_primes [0.04371378700125206, 0.04463105400100176, 0.04481986299833807]

num = 38, loops = 1000
lcm_range_fast   [0.042841554000915494, 0.043649038998410106, 0.04868016199907288]
lcm_range_primes [0.04571479200058093, 0.04654245399979118, 0.04671720700025617]

num = 39, loops = 1000
lcm_range_fast   [0.04469198100014182, 0.04786454099848925, 0.05639159299971652]
lcm_range_primes [0.04572433999965142, 0.04583652600013011, 0.046649005000290344]

num = 40, loops = 1000
lcm_range_fast   [0.044788433999201516, 0.046223339000789565, 0.05302252199908253]
lcm_range_primes [0.045482261000870494, 0.04680115900009696, 0.046941823999077315]

num = 41, loops = 1000
lcm_range_fast   [0.04650144500010356, 0.04783133000091766, 0.05405569400136301]
lcm_range_primes [0.04678159699869866, 0.046870936999766855, 0.04726529199979268]

num = 42, loops = 1000
lcm_range_fast   [0.04772527699969942, 0.04824955299955036, 0.05483534199993301]
lcm_range_primes [0.0478546140002436, 0.048954233001495595, 0.04905354400034412]

num = 43, loops = 1000
lcm_range_primes [0.047872637000182294, 0.048093739000250935, 0.048502418998396024]
lcm_range_fast   [0.04906317900167778, 0.05292572700091114, 0.09274570399975346]

num = 44, loops = 1000
lcm_range_primes [0.049750300000596326, 0.050272532000235515, 0.05087747600009607]
lcm_range_fast   [0.050906279000628274, 0.05109869400075695, 0.05820328499976313]

num = 45, loops = 1000
lcm_range_primes [0.050158660000306554, 0.050309066000409075, 0.054478109999763547]
lcm_range_fast   [0.05236714599959669, 0.0539534259987704, 0.058996140000090236]

num = 46, loops = 1000
lcm_range_primes [0.049894845999006066, 0.0512076260001777, 0.051318084999365965]
lcm_range_fast   [0.05081920200063905, 0.051397655999608105, 0.05722950699964713]

num = 47, loops = 1000
lcm_range_primes [0.04971165599999949, 0.05024208400027419, 0.051092388999677496]
lcm_range_fast   [0.05388393700013694, 0.05502788499870803, 0.05994341699988581]

num = 48, loops = 1000
lcm_range_primes [0.0517014939996443, 0.05279760400117084, 0.052917389999493025]
lcm_range_fast   [0.05402479099939228, 0.055251746000067214, 0.06128628700025729]

num = 49, loops = 1000
lcm_range_primes [0.05412415899991174, 0.05474224499994307, 0.05610057699959725]
lcm_range_fast   [0.05757830900074623, 0.0590323519991216, 0.06310263200066402]

num = 50, loops = 1000
lcm_range_primes [0.054892387001018506, 0.05504404100065585, 0.05610281799999939]
lcm_range_fast   [0.0588886920013465, 0.0594741389995761, 0.06682244199873821]

num = 51, loops = 1000
lcm_range_primes [0.05582956999933231, 0.055921465000210446, 0.06004790299994056]
lcm_range_fast   [0.060586288000195054, 0.061715600999377784, 0.06733965300009004]

num = 52, loops = 1000
lcm_range_primes [0.0557458109997242, 0.05669860099988, 0.056761407999147195]
lcm_range_fast   [0.060323355999571504, 0.06177857100010442, 0.06778404599936039]

num = 53, loops = 1000
lcm_range_primes [0.05501838899908762, 0.05541463699955784, 0.0561610999993718]
lcm_range_fast   [0.06281833000139159, 0.06334177999997337, 0.06843207200108736]

num = 54, loops = 1000
lcm_range_primes [0.057314272000439814, 0.059501444000488846, 0.060004871998899034]
lcm_range_fast   [0.06634221600143064, 0.06662889200015343, 0.07153233899953193]

num = 55, loops = 1000
lcm_range_primes [0.05790564500057371, 0.05824322199987364, 0.05863306900027965]
lcm_range_fast   [0.06693624800027465, 0.06784769100158883, 0.07562533499913116]

num = 56, loops = 1000
lcm_range_primes [0.057219010001063, 0.05858367799919506, 0.06246676000046136]
lcm_range_fast   [0.06854197999928147, 0.06999059400004626, 0.07505119899906276]

num = 57, loops = 1000
lcm_range_primes [0.05746709300001385, 0.0587476679993415, 0.0606189070003893]
lcm_range_fast   [0.07094627400147147, 0.07241532700027165, 0.07868066799892404]

num = 58, loops = 1000
lcm_range_primes [0.0576490580006066, 0.058481812999161775, 0.05857339500107628]
lcm_range_fast   [0.07127979200049595, 0.07549924399972952, 0.07849203499972646]

num = 59, loops = 1000
lcm_range_primes [0.057503377998727956, 0.058632499998566345, 0.060360438999850885]
lcm_range_fast   [0.07332589399993594, 0.07625177999943844, 0.08087236799838138]

Ce calendrier info a été généré à l'aide de Python 3.6 en cours d'exécution sur un dérivé de Debian de Linux, sur un ancien processeur à 2 ghz Pentium IV de la machine.

Answer 3

 if all(n % i == 0 for i in range(2, 21)):
 

all accepte un itérable et renvoie True si tous ses éléments sont évalués à True , False sinon. La partie n % i == 0 for i in range(2, 21) renvoie une valeur itérable avec 19 True ou False valeurs, selon que n est divisible par les i valeur.

Answer 4

Construit en tout aidera.

Renvoie True si tous les éléments de l'itérable sont vrais (ou si l'itérable est vide).

 if all(n % i == 0 for i in xrange(2, 21))
 

Answer 5

C'est juste une astuce mathématique, utilisez quelque chose comme n % "LCM(1,2,...,20) == 0 qui pourrait être codé comme:

 if n % 232792560 == 0:
    #do whatever you want