python optimization numbers combinations

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



optimization numbers (5)

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))

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)


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.


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.


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.


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.