Ngạc nhiên về hiệu suất đệ quy tốt trong python

Question

tôi đã viết chức năng Python khá nghèo này cho nguyên tố:

import math 

def factor(n): 
    for i in range(2, int(math.sqrt(n)+1)): 
     if not n % i: 
      return [i] + factor(n//i) 
    return [n] 

và nó làm việc như mong đợi, bây giờ tôi đã quan tâm đến việc thực hiện có thể tốt hơn khi sử dụng một cách tiếp cận lặp đi lặp lại :

def factor_it(n): 
    r = [] 
    i = 2 
    while i < int(math.sqrt(n)+1): 
     while not n % i: 
      r.append(i) 
      n //= i 
     i +=1 
    if n > 1: 
     r.append(n) 
    return r 

Nhưng những gì tôi quan sát thấy (trong khi các chức năng đưa ra kết quả tương tự) là chức năng lặp mất nhiều thời gian để chạy. Ít nhất tôi có cảm giác, khi làm điều này:

number = 31123478114123 
print(factor(number)) 
print(factor_it(number)) 

vì vậy tôi đo:

setup = ''' 
import math 

def factor(n): 
    for i in range(2, int(math.sqrt(n)+1)): 
     if not n % i: 
      return [i] + factor(n//i) 
    return [n] 

def factor_it(n): 
    r = [] 
    i = 2 
    while i < int(math.sqrt(n)+1): 
     while not n % i: 
      r.append(i) 
      n //= i 
     i +=1 
    if n > 1: 
     r.append(n) 
    return r 
''' 

import timeit 

exec(setup) 

number = 66666667*952381*290201 
print(factor(number)) 
print(factor_it(number)) 

print(timeit.Timer('factor('+str(number)+')',setup=setup).repeat(1,1)) 
print(timeit.Timer('factor_it('+str(number)+')',setup=setup).repeat(1,1)) 

Và đây là những gì tôi nhận:

[290201, 952381, 66666667] 
[290201, 952381, 66666667] 
[0.19888348945642065] 
[0.7451271022307537] 

Tại sao là cách tiếp cận đệ quy trong này trường hợp nhanh hơn phiên bản lặp lại?

^{Tôi sử dụng WinPython-64bit-3.4.4.2 (Python 3.4.4 64bits).}

Answer 1

Đó là vì bạn đang tính toán lại sqrt mỗi lần. sửa đổi này chạy nhanh như phiên bản đệ quy của bạn:

def factor_it2(n): 
    r = [] 
    i = 2 
    lim = int(math.sqrt(n)+1) 
    while i < lim: 
     while not n % i: 
      r.append(i) 
      n //= i 
     lim = int(math.sqrt(n)+1) 
     i += 1 
    if n > 1: 
     r.append(n) 
    return r 

timeit mang lại cho tôi những thời gian này:

factor  0.13133816363922143 
factor_it 0.5705408816539869 
factor_it2 0.14267319543853973 

Tôi nghĩ rằng sự khác biệt nhỏ gì còn lại là do for … in range(…) là nhanh hơn so với while vòng lặp tương đương, như các for vòng lặp có thể sử dụng một máy phát điện thay vì phải thực hiện một loạt các so sánh.