program - time benchmark python

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

Question

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.

Answer 1

Construido en all 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))

Answer 2

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

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

Answer 3

Hay una compensación entre corta y eficiente.

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

La forma Eficiente es notar que cosas como n % 20 == 0 también significan que n % f == 0 donde f es cualquier factor de 20. Por ejemplo, puedes 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 la declaración completa 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 la forma eficiente no es tan fácil de leer y mantener. Elija el que mejor se adapte a sus necesidades.

Answer 4

Hay una manera más inteligente de hacer esto. Si n es divisible por cada número entero en el rango (1, 21), entonces debe ser un múltiplo del múltiplo menos común 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 el módulo de fractions , 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 cualquier número n es divisible por todos los números, es el rango (1, 21) lo que puedes hacer

n % lcm20 == 0

o codifique la constante en su script:

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

Como señala Anton Sherwood 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 se muestra un código de tiempo 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 módulo de fractions . 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://.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.

Answer 5

Muchos de los ejemplos de código anteriores son más cortos, pero (probablemente) no lo suficientemente eficientes:

n%2 == 0 =>
n%4 6 8... ==0
n%3 == 0 =>
n%3 6 9... ==0

Solo podemos usar primos para verificar dentro del rango:

if all(n % i == 0 for i in [2,3,5,7,11,13,17,19])

Además, si n divide todo de 2 a 20, divide el LCM de 2 a 20.

Answer 6

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)):

Answer 7

No sé si responder tu propia pregunta es bueno o no.

Como necesito verificar si un número es divisible por números del 1 al 20 o no. Entonces tomará mucho tiempo verificarlo. Pero si pudiera hacer la lista de verificación más corta, sería eficiente.

Por ejemplo, si un número es divisible entre 18 , también debería ser divisible entre 2 3 6 y 9 . Entonces, basado en esto, hice mi lista de verificación:

if all(n % i == 0 for i in [7,11,13,16,17,18,19,20]):
# some code

Y para 14 15 y 12 piensan así.

14 : Si un número es divisible por ambos, 2 y 7 , debe ser divisible por 14 .

15 : Entonces en el caso de 15 que si un número es divisible por 20 entonces también debería ser divisible por 5 y si un número es divisible por 18 entonces también debería ser divisible por 3 y si un número es divisible por ambos 3 y 5 entonces debe ser divisible por 15 .

Esto es más eficiente que verificar todos los números y también asegura que el número sea divisible por todos los números entre 1 y 20.

Answer 8

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 - 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 tan simple que hacer all con una expresión de generador como se describe en las otras respuestas es la mejor manera de hacerlo.

Answer 9

Similar a las respuestas anteriores:

import operator
x = 232792560
if reduce(operator.__and__, [x % n == 0 for n in xrange(2, 21, 2)]):
print("ok")

Answer 10

Soy un usuario de Python muy ligero y no sabía nada de todo. Esas soluciones son geniales (y probablemente más eficientes que la que estoy a punto de publicar). Pero solo si quieres ver otra forma de hacerlo, aquí hay otra opción:

def IsDivUpTo20(n):
for i in range(2, 21):
if n % i != 0:
return False
return True

Y llámalo así

if IsDivUpTo20(50):
#what to do if it is divisible
else:
#what to do if it isn''t
#for the example of 50, it''ll be false and jump to the else part, but you can put any number of variable in there

Funcionalmente funciona más o menos de la misma manera que "todo", pero si no está acostumbrado a la sintaxis y los complementos de lujo, este es un poco más intuitivo.

* Nota: uso Python 3, no Python 2.7, ya que la pregunta está etiquetada. Estoy bastante seguro de que esto funciona en esa versión, pero si no, alguien por favor corrígeme.

Answer 11

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

all acepta un iterable y devuelve True si todos sus elementos se evalúan a True , False caso contrario. La parte n % i == 0 for i in range(2, 21) devuelve un iterable con 19 valores True o False , dependiendo de si n es divisible por el correspondiente valor i .