找到三个整数,使得它们的余弦值之和变为最大值

Question

有三个整数x,y并且z(每个> = 1)和给定的上限整数n<10 ^ 6.还有,n = x + y + z和output = cos(x) + cos(y) + cos(z).

练习是最大化output.

我为此编写了一个简单的脚本,但时间复杂度为O(n ^ 3).有什么方法可以简化这个吗？

from math import cos

n = 50
x = 1
y = 1
z = 1

total = cos(x) + cos(y) + cos(z)

for x in xrange(n):
    for y in xrange(n):
        for z in xrange(n):
            if x + y + z == n:
                temp = cos(x) + cos(y) + cos(z)
                if temp > total: total = temp

print round(total, 9) 

Answer 1

正如Jean-FrançoisFabre在评论中指出的那样,你可以用很多技巧来提高性能,但首先

• 注意到的价值a和b确定的价值c,
• 注意到三个变量WLOG中至少有一个a小于或等于N/3,
• 使用剩余的对称性b并在1和之间c绑定ba
• 预先计算所有相关的cos值,并尽量避免快速连续查找相同的值,
• 使用Numba进行JIT编译代码并免费获得一些性能(大约400倍(N - a)//2 + 1),

那么否则brutforcy解决方案会相对快速地终止cos(a)(因此也适用于任何给定的N = 500):

import numpy as np
from numba import jit

@jit
def maximize(N):
    cos = np.cos(np.arange(N))
    m = -3
    for a in range(1, N//3 + 1):
        cosa = cos[a]
        if m - 2 > cosa:
            continue
        for b in range(a, (N - a)//2 + 1):
            c = N - a - b
            res = cosa + cos[b] + cos[c]
            if res > m:
                m = res
                bestabc = (a, b, c)
    return m, bestabc

maximize(1000000)  # (2.9787165245899025, (159775, 263768, 576457))

Answer 2

理想情况下,您只想计算一次可能的组合.忽略几何属性cos,并将其视为从数字到数字的简单映射(例如,将其用作随机属性,如@Jean在其第二条评论中所述).
首先,你必须意识到,在挑选了2个数字之后,第三个被给出.你可以选择'智能'来避免多余的选择:

from math import cos
import time
import numpy as np
from numba import jit



def calc(n):
    x = 1
    y = 1
    z = 1
    total = cos(x) + cos(y) + cos(z)
    for x in range(n, int((n/3 - 1)),-1): #I only want to pick X from n-2 to  n/3 -1 , after that we will repeat.
        cosx = cos(x)
        for y in range(max(int(((n-x)/2))-1,1),min(int(n-x),int(n/3))): #I would only pick number that will not be choosen for the z
                z = n-x-y #Infer the z, taking the rest in account
                temp = cosx + cos(y) + cos(z)
                if temp > total: total = temp
    return total

tic = time.clock()
total = calc(10000)
print(time.clock()-tic)

print (total)

将1.3467099999999999(在我的机器上).
正如@fuglede所提到的,使用numba进行进一步优化是值得的.

编辑: 保存所有以前计算的cos值更实际,然后重新计算它们,当你访问np数组时,你不是简单地访问内存中的一个点,而是使用ndarray函数.使用python内置cos实际上更快:

import numpy as np

from math import cos
import time
import timeit

cos_arr = np.cos(np.arange(10000000))
tic = time.time()

def calc1():
    total = 0
    for j in range(100):
        for i in range(10000000):
            total += cos_arr[i]

def calc2():
    total = 0
    for j in range(100):
        for i in range(10000000):
            total += cos(i)

time1 = timeit.Timer(calc1).timeit(number=1)

time2 = timeit.Timer(calc2).timeit(number=1)
print(time1)
print(time2)

随着输出:

127.9849290860002
108.21062094399986

如果我在计时器内移动数组创建,它甚至更慢.