python之找到最近的三角形数的最快方法

在 python 中，我需要一个函数，它接受一个整数并返回 n 减去最近的 triangle number 的绝对值。至我现在这样做的方式是生成一个包含最多 n 个三角形数字的列表。 然后使用:

def closest(myList, myNumber): 
    c = min(myList, key=lambda x:abs(x-myNumber)) 

寻找最近的三角形数。

最终结果列表应该是这样的:

[0, 0, 1 , 0 , 1 ,1 , 0 , 1, 2 , 1, 0 , 1, 2, 2, 1, 0, etc.] 

如果您有另一种方法可以更快地生成相同的结果，那就去做吧。

请您参考如下方法:

一点点数学会带来更具分析性的解决方案:

from math import sqrt 
def close_triangle2(n): 
    m=int(0.5*(-1+sqrt(1+8*n))) #solve it for the explicit formula 
    tan0=(m*m+m)/2              #the closest one is either this 
    tan1=(m*m+3*m+2)/2          #or this 
    if (n-tan0)>(tan1-n): 
        return tan1-n 
    else: 
        return n-tan0 

当数字很大时，它会变得比@perreal 的循环版本稍微快一些:

In [87]: 
 
%timeit close_triangle(111111111) 
100000 loops, best of 3: 5 µs per loop 
In [86]: 
 
%timeit close_triangle2(111111111) 
100000 loops, best of 3: 4.13 µs per loop 

如果你想知道:

In [94]: 
 
close_triangle2((30**10 * (30**10+1)) / 2 + 100) 
Out[94]: 
100L 
In [95]: 
 
close_triangle((30**10 * (30**10+1)) / 2 + 100) 
Out[95]: 
100L 
 
In [102]: 
 
%timeit close_triangle((30**10 * (30**10+1)) / 2 + 100) 
10000 loops, best of 3: 17.9 µs per loop 
In [103]: 
 
%timeit close_triangle2((30**10 * (30**10+1)) / 2 + 100) 
100000 loops, best of 3: 12 µs per loop