如何使python代码块简洁高效
如何使python代码块简洁高效
提问于 2016-08-03 11:56:13
我完全是编程和python的新手。我在解决一个问题。我找到了解决办法，但似乎太慢了。
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的所有数字整除的代码。
我怎样才能使它更短更高效。
回答 11
Stack Overflow用户
回答已采纳
发布于 2016-08-03 12:17:35
有更聪明的方法可以做到这一点。如果n可被(1，21)范围内的每个整数整除，那么它必须是这些整数的最小公倍数的倍数。
您可以使用GCD (最大公因子)逐步计算一组数字的LCM。您可以从fractions模块导入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)
# 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是否可以被所有数字整除，范围是(1，21)，您可以这样做。
n % lcm20 == 0或者将常量硬编码到脚本中：
# 232792560 is the LCM of 1..20
n % 232792560 == 0正如Anton在他的评论中指出的那样，我们可以通过仅取范围上半部分的LCM来加快查找所需LCM的过程。这是因为范围的下半部分中的每个数字都是范围上半部分中的一个数的除数。
我们可以通过内衬GCD和LCM计算来进一步提高速度，而不是调用函数来执行这些操作。由于额外的开销，Python函数调用明显比C函数调用慢。
Yakk提到了另一种寻找所需的LCM的方法:计算范围内的素数幂的乘积。这是相当快，如果范围是足够大(约40左右)，但对于小数字，简单的LCM循环更快。
下面是一些比较这些不同方法的速度的timeit代码。这个脚本运行在Python 2和3上，我已经在Python2.6和Python3.6上测试过它。它使用罗伯特·威廉·汉克斯()的一个主要列表函数来实现雅克的建议。我稍微修改了Robert的代码，使其与Python 3兼容。我想可能有一种更有效的方法来找到质数；如果是的话，我希望看到它。:)
我在前面提到过，fractions模块中有一个GCD函数。我对它做了一些时间测试，但它明显比我的代码慢。这大概是因为它对参数进行了错误检查。
#!/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]这个计时信息是使用Python3.6生成的，它运行在Linux的Debian派生程序上，运行在一台古老的2 2GHz奔腾IV机器上。
Stack Overflow用户
发布于 2016-08-03 12:02:46
在短时间和高效率之间有一种权衡。
捷径是if all(n % i == 0 for i in range(2, 21)):
有效的方法是注意到，像n % 20 == 0这样的东西也意味着n % f == 0，其中f是20的任何因子，例如，您可以放弃n % 2 == 0。因此，你将得到更少的比较，这将运行得更快。在执行此操作时，您将注意到一个模式，并注意到整个语句简化为if n % 232792560 == 0！但是，这已经深深地嵌入了其中的20，所以如果你需要一个不同的上限，就很难解开它。
因此，您可以看到，有效的方法并不是那么容易阅读和维护。因此，选择一个最适合您的需求。
Stack Overflow用户
发布于 2016-08-03 11:57:49
if all(n % i == 0 for i in range(2, 21)):如果所有元素都被计算为all，则True将接受可迭代性，并返回False。n % i == 0 for i in range(2, 21)部件返回一个可迭代的值，其中包含19个True或False值，这取决于n是否可被相应的i值所除。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/38742938
复制相关文章
相似问题
腾讯云开发者
