如何使这个python代码块简洁高效 [英] How to make this Block of python code short and efficient
问题描述
我是编程和python的全新手。我正在解决一个问题。我找到了解决方案，但似乎太慢了。
I am total newbie to programming and python. I was solving a problem. I found the solution but it seems like too slow.
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:
这是代码的代码检查 n 是否可被2到20之间的所有数字整除。
This is the piece the code to check whether n is divisible by all numbers from 2 to 20 or not.
我如何缩短它高效。
推荐答案
有一种更聪明的方法可以做到这一点。如果 n 可以被范围内的每个整数（1,21）整除，那么它必须是这些整数的最小公倍数。
There's a smarter way to do this. If n is divisible by every integer in range(1, 21) then it must be a multiple of the least common multiple of those integers.
您可以使用GCD（最大公约数）逐步计算一组数字的最小公倍数。您可以从 fractions 模块导入gcd函数，或直接在代码中实现它。
You can calculate the LCM of a set of numbers progressively, using the GCD (greatest common divisor). You can import the gcd function from the fractions module, or implement it directly in your 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)
输出
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
现在，测试是否有任何数字 n 可被所有t整除他的数字是你可以做的范围（1,21）
Now, to test if any number n is divisible by all the numbers is range(1, 21) you can just do
n % lcm20 == 0
或将常量硬编码到脚本中：
or hard-code the constant into your script:
# 232792560 is the LCM of 1..20
n % 232792560 == 0
正如Anton Sherwood在他的评论我们可以通过仅采用范围上半部分的LCM来加快寻找所需LCM的过程。这是有效的，因为范围的下半部分中的每个数字都是范围上半部分中数字的除数。
As Anton Sherwood points out in his comment we can speed up the process of finding the required LCM by just taking the LCM of the upper half of the range. This works because each number in the lower half of the range is a divisor of a number in the upper half of the range.
我们可以进一步提高速度 - 计算GCD和LCM计算，而不是调用函数来执行这些操作。由于涉及额外的开销，Python函数调用明显慢于C函数调用。
We can improve the speed even further by in-lining the GCD and LCM calculations, rather than calling functions to perform those operations. Python function calls are noticeably slower than C function calls due to the extra overheads involved.
Yakk提到了另一种寻找所需LCM的方法：计算主要权力的乘积在范围中。如果范围足够大（大约40左右），这是非常快的，但对于小数字，简单的LCM循环更快。
Yakk mentions an alternative approach to finding the required LCM: calculate the product of the prime powers in the range. This is quite fast if the range is large enough (around 40 or so), but for small numbers the simple LCM loop is faster.
下面是一些 timeit 比较这些不同方法的速度的代码。这个脚本在Python 2和3上运行，我在Python 2.6和Python 3.6上测试过它。它使用Robert William Hanks的主要列表功能来实现Yakk的建议。我稍微修改了Robert的代码，使其与Python 3兼容。我想可能有一种更有效的方法来找到主要权力;如果是的话，我想看看。 ：）
Below is some timeit code that compares the speed of these various approaches. This script runs on Python 2 and 3, I've tested it on Python 2.6 and Python 3.6. It uses a prime list function by Robert William Hanks to implement Yakk's suggestion. I've modified Robert's code slightly to make it compatible with Python 3. I suppose there may be a more efficient way to find the prime powers; if so, I'd like to see it. :)
我之前提到过，分数模块中有一个GCD函数。我用它做了一些时间测试，但它明显慢于我的代码。大概是因为它对参数进行了错误检查。
I mentioned earlier that there's a GCD function in the fractions module. I did some time tests with it, but it's noticeably slower than my code. Presumably that's because it does error checking on the 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)
输出
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]
这个时序信息是使用运行在Linux的Debian衍生物上的Python 3.6，在古老的2GHz Pentium IV机器上生成的。
This timing info was generated using Python 3.6 running on a Debian derivative of Linux, on an ancient 2GHz Pentium IV machine.
这篇关于如何使这个python代码块简洁高效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
