¡Qué pregunta tan interesante!
La respuesta ingenua es usar un algoritmo eficiente para [math] {n \ choose r} [/ math] (ver ¿Cuáles son algunos algoritmos eficientes para calcular nCr?) Y luego usar un algoritmo de exponenciación eficiente como la cuadratura repetida (¿Cuáles son algunos algoritmos rápidos para calcular la enésima potencia de un número?) Esto en realidad podría ser el mejor.
Pero, la multiplicación es más eficiente cuando los términos tienen aproximadamente el mismo tamaño. Por lo tanto, es posible que podamos obtener un poco de jugo extra entrelazando el cálculo combinatorio con la exponenciación, si pudiéramos dividir este último en piezas de tamaño conveniente. (El costo real de la computación [matemática] {n \ elegir r} [/ matemática] es trivial en comparación con la exponenciación.) Una forma de calcular [matemática] {n \ elegir r} [/ matemática] es con la recurrencia [matemática ] {n \ choose r} = {n-1 \ choose r} + {n – 1 \ choose r – 1} [/ math]. En el medio del triángulo de Pascal, esos dos términos serían aproximadamente del mismo tamaño. En los bordes, sin embargo, terminaríamos con un cálculo definitivamente ineficiente en el que solo agregamos uno al exponente cada vez. De manera similar, la recurrencia [matemática] {n \ elegir r} = {n \ elegir r-1} \ frac {n-r + 1} {r} [/ matemática] terminará con muchos exponentes pequeños (y no siempre enteros.)
- ¿Cuál es el programa de clasificación rápida que tiene su mediana como pivote?
- ¿Qué debe saber todo programador sobre tablas hash y funciones hash?
- ¿Existe un algoritmo de tiempo O (N) para esta pregunta?
- Preguntado por un no experto en tecnología, ¿qué tan impactante sería si una tecnología pudiera mitigar el ruido impulsivo en tiempo real usando un algoritmo no lineal simple que usa la mediana (en lugar de la media)? Por ejemplo, podría usarse para reemplazar filtros lineales analógicos en teléfonos móviles, esencialmente actuando como un filtro lineal a menos que detecte ruido impulsivo y actúe para condicionarlo.
- ¿Cuál será el algoritmo de rotación correcto en C?
Aún así, vamos a intentarlo. Aquí hay una implementación muy simple de la idea en Python. La memoria es una especie de memoria ineficiente porque mantiene los resultados después de que ya no los necesitamos.
def pow2_memoize (a, n, r, tabla):
si r == 0 o r == n:
devolver un
if (n, r) en la tabla:
tabla de retorno [(n, r)]
if (n, n – r) en la tabla:
tabla de retorno [(n, nr)]
left = pow2_memoize (a, n-1, r-1, tabla)
right = pow2_memoize (a, n-1, r, tabla)
x = izquierda * derecha
tabla [(n, r)] = x
volver x
def pow2_pascal (a, n, r):
return pow2_memoize (a, n, r, {})
def pow2_native (a, n, r):
return pow (a, ncr (n, r))
Escribí un pequeño script de prueba que multiplica [math] 2 ^ {n \ choose r} [/ math] y, francamente, me sorprendieron los resultados:
prueba de def (n, r):
inicio = time.time ()
a1 = pow2_native (2, n, r)
end = time.time ()
imprima “Native:”, end – start
inicio = time.time ()
a2 = pow2_pascal (2, n, r)
end = time.time ()
imprimir “Pascal:”, final – inicio
afirmar a1 == a2
>>> prueba (30, 9)
Nativo: 0.256000041962
Pascal: 0.103999853134
>>> prueba (30, 15)
Nativo: 3.33800005913
Pascal: 2.78699994087
>>> prueba (40, 9)
Nativo: 6.36199998856
Pascal: 2.13499999046
>>> prueba (40, 10)
Nativo: 20.5440001488
Pascal: 12.3759999275
>>> prueba (40, 15)
MemoryError
El enfoque del triángulo de Pascal pirateado es sustancialmente más rápido que el uso de la función nativa pow (), que realiza la cuadratura repetida debajo del capó. (¡En C, incluso!)
Todavía siento que debo haber arruinado algo … y, sin embargo, la respuesta es correcta y el beneficio de rendimiento está ahí. pow () vs ** no parece hacer la diferencia; Todavía no he puesto un algoritmo de exponenciación de Python puro para asegurarme de que realmente estamos obteniendo una cuadratura repetida.
EDITAR 10/31: Cambiar la base cambia el resultado. Si usamos ‘3’ como base en su lugar:
>>> prueba (25, 12)
Nativo: 4.22799992561
Pascal: 8.97300004959
>>> prueba (30, 9)
Nativo: 21.135999918
Pascal: 67.4400000572
Esto sugiere que el costo puede no ser la multiplicación, ¡sino quizás la asignación de memoria!
Escribí una pequeña prueba que simplemente multiplica dos números grandes.
La cuadratura parece más eficiente para la base 3:
[matemáticas] 3 ^ {2704156} \ veces 3 ^ {2496144} [/ matemáticas]: 4,72 segundos
[matemáticas] 3 ^ {2600150} \ veces 3 ^ {2600150} [/ matemáticas]: 4,52 segundos
Tamaños desiguales parecen más eficientes para la base 2:
[matemáticas] 2 ^ {2704156} \ veces 2 ^ {2496144} [/ matemáticas]: 0,017 segundos
[matemáticas] 2 ^ {2600150} \ veces 2 ^ {2600150} [/ matemáticas]: 0,055 segundos
Multiplicar por un valor pequeño sigue siendo eficiente, a diferencia de lo que pensé que podría suceder:
[matemáticas] 2 ^ {5200299} \ veces 2 ^ {1} [/ matemáticas]: 0,00067 segundos
[matemáticas] 3 ^ {5200299} \ veces 3 ^ {1} [/ matemáticas]: 0.00100 segundos
Entonces, el resultado anterior es solo algo extraño con cómo Python maneja potencias de 2.
