如何使这块 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.
我如何使它简短而有效.
How I can make it short and efficient.
推荐答案
有一个更聪明的方法来做到这一点.如果 n 可以被 range(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(最大公约数)逐步计算一组数字的 LCM.您可以从 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 可以被所有数字整除是 range(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. :)
我之前提到过 fractions 模块中有一个 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('
num = {0}, loops = {1}'.format(num, loops))
time_test(loops, reps)
num *= 2
loops //= 2
print('
' + '- ' * 40)
funcs = (
lcm_range_fast,
lcm_range_primes
)
loops = 1000
for num in range(30, 60):
print('
num = {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]
此时间信息是使用 Python 3.6 生成的，该 Python 3.6 在 Linux 的 Debian 衍生产品上运行，在古老的 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屋！
