Pregunta Cómo hacer que este código de bloque de pitón sea corto y eficiente


Soy totalmente novato en programación y python. Estaba resolviendo un problema Encontré la solución, pero parece demasiado lento.

    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:

Esta es la pieza del código para verificar si n es divisible por todos los números del 2 al 20 o no.

Cómo puedo hacerlo breve y eficiente.


31
2017-08-03 11:56


origen


Respuestas:


Hay una manera más inteligente de hacer esto. Si n es divisible por cada número entero en el rango (1, 21) luego debe ser un múltiplo de minimo común multiplo de esos enteros.

Puede calcular el MCM de un conjunto de números progresivamente, utilizando el GCD (máximo divisor común). Puede importar la función gcd desde fractions módulo, o implementarlo directamente en su código.

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)

salida

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

Ahora, para probar si hay algún número n es divisible por todos los números es el rango (1, 21) que puede hacer

n % lcm20 == 0

o codifique la constante en su script:

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

Como Anton Sherwood señala en su comentario podemos acelerar el proceso de encontrar el LCM requerido simplemente tomando el LCM de la mitad superior del rango. Esto funciona porque cada número en la mitad inferior del rango es un divisor de un número en la mitad superior del rango.

Podemos mejorar aún más la velocidad al alinear los cálculos de GCD y LCM, en lugar de llamar a funciones para realizar esas operaciones. Las llamadas de función de Python son notablemente más lentas que las llamadas de función C debido a los gastos indirectos adicionales implicados.

Yakk menciona un enfoque alternativo para encontrar el LCM requerido: calcule el producto de las potencias principales en el rango. Esto es bastante rápido si el rango es lo suficientemente grande (alrededor de 40 o así), pero para números pequeños, el bucle LCM simple es más rápido.

A continuación hay algunos timeit código que compara la velocidad de estos diversos enfoques. Este script se ejecuta en Python 2 y 3, lo he probado en Python 2.6 y Python 3.6. Utiliza una función de lista principal de Robert William Hanks para implementar la sugerencia de Yakk. Modifiqué ligeramente el código de Robert para hacerlo compatible con Python 3. Supongo que puede haber una manera más eficiente de encontrar los poderes principales; si es así, me gustaría verlo. :)

Mencioné anteriormente que hay una función GCD en el fractions módulo. Hice algunas pruebas de tiempo con él, pero es notablemente más lento que mi código. Presumiblemente eso se debe a que hace un error al verificar los argumentos.

#!/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)

salida

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]

Esta información de tiempo se generó usando Python 3.6 ejecutándose en un derivado de Debian de Linux, en una antigua máquina Pentium IV de 2 GHz.


56
2017-08-03 12:17



Hay una compensación entre corta y eficiente.

los Corto es el camino if all(n % i == 0 for i in range(2, 21)):

los Eficiente forma es darse cuenta de que cosas como n % 20 == 0 también significa que n % f == 0 dónde f es cualquier factor de 20. Por ejemplo, puede soltar n % 2 == 0. Por lo tanto, terminará con menos comparaciones que se ejecutarán más rápido. Al hacer esto, notarás un patrón y notarás que todo declaración se reduce a if n % 232792560 == 0! Pero eso ahora tiene profundamente integrado el 20 dentro de él, por lo que será difícil desentrañarlo si necesita un límite superior diferente.

Entonces ves que el eficiente manera no es tan fácil de leer y mantener. Elija el que mejor se adapte a sus necesidades.


79
2017-08-03 12:02



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

all acepta un iterable y regresa True si todos sus elementos son evaluados para True, False de otra manera. los n % i == 0 for i in range(2, 21) parte devuelve un iterable con 19 True o False valores, dependiendo si n es divisible por el correspondiente i valor.


48
2017-08-03 11:57



Construido en todas  ayudará.

Devuelve True si todos los elementos de iterable son verdaderos (o si el iterable está vacío).

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

6
2017-08-03 11:58



Por variedad, la forma en que podría haber usado un ciclo para esto es

test = True
for modulus in range(2, 21):
    if n % modulus != 0:
        test = False
        break
if test:
    # Do stuff

Si te sientes cómodo con for-else, puedes mejorar la brevedad

for modulus in range(2, 21):
    if n % modulus != 0:
        break
else:
    # Do stuff

aunque ese patrón puede ser lo suficientemente inusual como para no querer usarlo.

Otra opción es escribir una función auxiliar

def is_divisible_by_integers_up_to(n, bound):
    for modulus in range(2, bound + 1):
        if n % modulus != 0:
            return False
    return True

if is_divisible_by_integers_up_to(n, 20):
    # Do stuff

Sin embargo, este ejemplo particular es lo suficientemente simple como para all con una expresión de generador como se describe en las otras respuestas es la mejor manera de hacerlo.


4
2017-08-03 18:26



Es solo un truco matemático, usar algo como n % "LCM(1,2,...,20) == 0 que podría codificarse como:

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

4
2017-08-03 12:18



Necesita una condición que evalúe Verdadero cuando todas las divisiones dan un cero restante. Las dos soluciones propuestas hasta ahora no parecen hacer eso. Sospecho que la condición que necesitas es

if not any(n % i for i in range(2, 21)):

3
2017-08-03 12:05