Wie bekomme ich schnell Antwort von LCM von Python

Question

def getLCM(a, b): 
    c, d = max(a, b), min(a, b) 
    while c != d: 
     temp = c - d 
     c, d = max(temp, d), min(temp, d) 

    return a * b // c 


def nlcm(num): 
    temp = 1 
    while len(num) != 0: 
     temp = getLCM(temp, num[-1]) 
     num.pop() 
    return temp 

print(nlcm([2,6,8,14,5])); 

Ich muss "schnell" bekommen dieses Problem zu beantworten. im Testfall ist mein Code sehr langsam.

Answer 1

Es gibt bestehende gcd Implementierungen in Python, und LCM ist in Bezug auf gcd definierbar, so dass Sie genauso gut vermeiden können, das Rad neu zu erfinden. Im Einzelnen:

ggT (a, b) x LCM (a, b) = a × b

mit Python 3.5 und höher, wird eine beschleunigte gcd Funktion auf dem math Modul, so lcm kann vereinfacht zu:

from math import gcd 

def getLCM(a, b): 
    return a * b // gcd(a, b) 

auf älteren Python, ist es nicht beschleunigt, sondern fractions.gcd ist eine anständige Implementierung für Sie zur Verfügung gestellt, so dass Sie es stattdessen verwenden können, oder die bestmöglichenzu verwendenauf, was Version Sie laufen auf einem verschachtelten Importversuch funktioniert:

try: 
    from math import gcd 
except ImportError: 
    from fractions import gcd 

Ihre nlcm Schleife auch vereinfacht werden: Sie müssen manuell, nur Schleife nicht destruktiv iterieren:

def nlcm(num): 
    temp = 1 
    for x in num: 
     temp = getLCM(temp, x) 
    return temp 

Or wenn Sie bekommen klug, verwenden Sie reduce (functools.reduce auf Python 3.x), da es tut genau das, was das vereinfachte Schleife bereits tut:

from functools import reduce 

def nlcm(nums): 
    return reduce(getLCM, nums, 1) 

Answer 2

die „lange Ausführung“ Unter der Annahme, ist nicht in dem Beispiel, das Sie zur Verfügung gestellt, sondern mit größeren Eingängen können Sie memoization und increate die Zeit getLCM() im Fall berechnet wird es genannt wieder mit den gleichen Zahlen addieren:

hash = dict() # we'll save here the calculated results 

def getLCM(a, b): 
    global hash 
    if (a, b) in hash: # if it was already calculated 
     return hash[(a, b)] # use the cached result 
    c, d = max(a, b), min(a, b) 
    while c != d: 
     temp = c - d 
     c, d = max(temp, d), min(temp, d) 

    hash[(a, b)] = a * b // c. # cash the result 
    return a * b // c