python - Encontrar tres enteros tales que su suma de valores de coseno se convierta en max

optimization numbers

Question

Hay tres enteros x , y y z (cada uno de ellos> = 1) y un entero superior dado dado n <10 ^ 6. Además, n = x + y + z y output = cos(x) + cos(y) + cos(z) .

El ejercicio es maximizar el output .

Escribí un script simple para esto, pero la complejidad del tiempo es O (n ^ 3). ¿Hay alguna manera de simplificar esto?

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

Como lo señaló Jean-François Fabre en los comentarios, hay muchos trucos que podría aplicar para mejorar el rendimiento, pero en primer lugar

• notando que los valores de a y b determinan el valor de c ,
• teniendo en cuenta que al menos una de las tres variables, WLOG a , es menor o igual a N/3 ,
• utilizando la simetría restante en b y c para unir b entre 1 y (N - a)//2 + 1
• precomputar todos los valores relevantes de cos, y tratar de evitar buscar los mismos valores en rápida sucesión,
• usando Numba para compilar el código JIT y obtener algo de rendimiento gratis (aproximadamente un factor de 400 para N = 500 ),

luego, la solución de fuerza bruta de otro modo termina relativamente rápido para N = 1000000 (y también para cualquier N < 1000000 ):

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):
        for b in range(1, (N - a)//2 + 1):
            c = N - a - b
            res = cos[a] + 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

Esto es puramente un problema básico de trigonometría. El valor máximo para su ecuación será cuando todos los cosenos tengan un valor de 1. En cos (n), donde n es cualquier número, para todos los valores formados por el conjunto de n = 2 * pi * k, donde k > = 0 y k es un número entero; su coseno tendrá un valor de 1. Sus valores x, y, z pertenecen a este conjunto y la permutación de estos valores le proporcionará el valor deseado. Además, no olvide comprobar si n en el conjunto es un número entero para reducir el espacio muestral.

Answer 3

Idealmente, usted desea calcular cada combinación posible solo una vez. Ignorar las propiedades geométricas de cos y tratarlo como simplemente un mapeo de número a número (por ejemplo, usarlo como una propiedad aleatoria, como @Jean mencionó en su segundo comentario).
Primero, debes darte cuenta que después de escoger 2 números, se da el tercero. y puede elegir ''inteligente'' para evitar selecciones redundantes:

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)

Tomará 1.3467099999999999 (en mi máquina).
Y como mencionó @fuglede, vale la pena usar numba para una mayor optimización.

Edición: guardar todos los valores de cos calculados anteriormente es en realidad más costoso que recalcularlos. Cuando accede a la matriz np, no solo accede a un punto de la memoria, sino que utiliza una función ndarray. Usar Python incorporado en cos es en realidad más rápido:

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)

Con salida:

127.9849290860002
108.21062094399986

Si muevo la creación de matriz dentro del temporizador, es aún más lento.

Answer 4

No hay absolutamente ninguna necesidad de calcular 3 xn ^ 3 valores de coseno.

Podemos suponer que x ≤ y ≤ z. Por lo tanto, x puede ser cualquier número entero en el rango de 1 a n / 3. y puede ser cualquier número entero en el rango de x a (n - x) / 2. Y z debe ser igual a n - x - y. Esto solo reduce el número de triples (x, y, z) que prueba desde n ^ 3 hasta aproximadamente n ^ 2/6.

A continuación, suponga que encontró tres números con un total de 2.749. E intentas una x con coseno (x) = 0.748. Cualquier total que incluya este x no puede ser más de 2.748, por lo que puede rechazar x directamente. Una vez que haya encontrado una buena suma, puede rechazar muchos valores de x.

Para hacer esto más efectivo, ordena los valores x del valor más alto al más bajo del coseno (x), porque eso hace que sea más probable que encuentres un total alto que te permita eliminar más valores.

Y el cálculo de cos (x) es lento, por lo que almacena los valores en una tabla.

Asi que:

Set c[i] = cos (i) for 1 ≤ i ≤ n. 
Set x[i] = integers 1 to n/3, sorted in descending order by value of c[i]. 
Set (bestx, besty, bestz) = (1, 1, n-2) and total = c[bestx] + c [besty] + c [bestz].

for x = elements of array x where c[x] + 2 ≥ bestTotal
    for y = x to (n-x)/2
        z = n - x - y
        total = c[x] + c[]y] + c[z]
        if total > bestTotal
            (bestx, besty, bestz) = (x, y, z)
            bestTotal = total

Puedes mejorar esto con un poco de matemáticas. Si la suma de y + z es constante, como aquí donde y + z = n - x, la suma de cos (y) + cos (z) es limitada. Sea P el entero más cercano a (n - x) / 2pi, y sea d = (n - x) - P * 2pi, entonces la mayor suma posible de cos (y) + cos (z) es 2 * cos (d) / 2).

Entonces, para cada x, 1 ≤ x ≤ n / 3, calculamos este valor d y cos (x) + 2 * cos (d / 2), almacenamos estos valores como el total máximo que se puede alcanzar con algunos x, orden x de modo que estos valores estén en orden descendente, e ignore aquellos x donde el total alcanzable es menor que el mejor total hasta el momento.

Si n es realmente grande (digamos mil millones), entonces puede usar el algoritmo de Euclides para encontrar todos los enteros y que estén cerca de 2k * pi + d rápidamente, pero eso será un poco complicado.

for x in 1 to n/3
    let s = n - x
    let P = s / 2pi, rounded to the nearest integer
    let d = (s - P * 2pi) / 2
    let maxSum [x] = cos(x) + 2*cos(d)

Set x[i] = integers 1 to n/3, sorted in descending order by value of maxSum[i]. 
Set (bestx, besty, bestz) = (1, 1, n-2)
Set bestTotal = c[bestx] + c [besty] + c [bestz].

for x = elements of array x where maxSum[x] ≥ bestTotal
    for y = x to (n-x)/2
        z = n - x - y
        total = c[x] + c[]y] + c[z]
        if total > bestTotal
            (bestx, besty, bestz) = (x, y, z)
            bestTotal = total

PD. En realidad intenté esto para algunos valores de N alrededor de 100 millones. Resulta que puedo ordenar la matriz para probar los valores más prometedores para x primero, lo que lleva mucho tiempo, pero a menudo el primer valor para x es el único que se prueba. O puedo usar x = 1, 2, 3, etc., lo que significa que se intentarán algunas docenas de valores para x, que es más rápido que la clasificación.

Answer 5

No hay necesidad de calcular un coseno para responder a esta pregunta. Simplemente haga un seguimiento de los tres (dos si n = 0 está permitido) los valores más pequeños de la función f(n) = abs(2pi*n-round(2pi*n)) ya que n va de 1 a N, donde N es su parte superior límite de búsqueda.

El coseno es 1 en múltiplos de 2*pi por lo que buscamos los dos o tres múltiplos más cercanos a un entero dentro del límite de búsqueda.

Todavía no he ejecutado un programa para hacer esto, pero debería ser fácil en cualquier idioma de programación. Usaré Mathematica.