La tarea es simplemente ver cuánto más rápido puede calcular n elegir n / 2 (para incluso n) que la función incorporada en python. Por supuesto, para n grande, este es un número bastante grande, por lo que en lugar de generar el número entero, debe generar la suma de los dígitos. Por ejemplo, para n = 100000
, la respuesta es 135702
. Pues n=1000000
lo es 1354815
.
Aquí está el código de Python:
from scipy.misc import comb
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n / 10
return r
sum_digits(comb(n,n/2,exact=True))
Tu puntaje es (highest n on your machine using your code)/(highest n on your machine using my code)
. Su código debe terminar en 60 segundos o menos.
Su programa debe dar la salida correcta para todos los n pares: 2 <= n <= (su n más alto)
No puede usar ningún código incorporado o bibliotecas que calculen coeficientes binomiales o valores que puedan transformarse rápidamente en coeficientes binomiales.
Puede usar cualquier idioma de su elección.
Respuesta principal La respuesta principal actual con un sorprendente 680.09 es solo la mitad.
n
a millones, mientras que dudo que la función Python maneje algo mayor quen = 1e5
sin asfixia.Respuestas:
C ++ (GMP) - (287,000,000 / 422,000) = 680.09
Combina descaradamente el teorema de Kummer por xnor y GMP por qwr.
Aún no está cerca de la solución Go, no estoy seguro de por qué.Editar: Gracias Keith Randall por el recordatorio de que la multiplicación es más rápida si el número es similar en tamaño. Implementé la multiplicación multinivel, similar al concepto de fusión de memoria en la gestión de memoria. Y el resultado es impresionante. Lo que solía tomar 51 segundos, ahora solo toma 0.5 segundos (es decir, ¡una mejora de 100 veces!)
La carrera por
n=287,000,000
El código. Compilar con
-lgmp -lgmpxx -O3
fuente
n
, 18s calculando el coeficiente binomial central, y el resto 37s en la conversión del resultado en cadena y sumando el dígito.Ir, 33.96 = (16300000/480000)
Funciona contando todos los factores primos en el numerador y el denominador y cancelando los factores coincidentes. Multiplica las sobras para obtener el resultado.
Más del 80% del tiempo se gasta en la conversión a la base 10. Tiene que haber una mejor manera de hacerlo ...
fuente
Python 3 (8.8 = 2.2 millones / 0.25 millones)
Esto está en Python, que no es conocido por la velocidad, por lo que probablemente pueda hacerlo mejor portando esto a otro idioma.
Generador de Primes tomado de este concurso StackOverflow .
La idea principal del algoritmo es utilizar el teorema de Kummer para obtener la factorización prima del binomio. Para cada cebado, aprendemos la potencia más alta que divide la respuesta, y multiplicamos el producto en ejecución por ese poder del cebado. De esta manera, solo necesitamos multiplicar una vez por cada primo en la factorización prima de la respuesta.
Salida que muestra el desglose del tiempo:
Sorprendentemente, la mayor parte del tiempo se dedica a convertir el número en una cadena para sumar sus dígitos. También sorprendentemente, la conversión a una cadena fue mucho más rápida que obtener dígitos repetidos
%10
y//10
, a pesar de que toda la cadena debe mantenerse en la memoria.Generar los números primos lleva un tiempo insignificante (y, por lo tanto, no me parece injusto copiar el código existente). Sumar dígitos es rápido. La multiplicación real toma un tercio del tiempo.
Dado que la suma de dígitos parece ser el factor limitante, quizás un algoritmo para multiplicar números en representación decimal ahorraría tiempo en total al atajar la conversión binaria / decimal.
fuente
Java (puntuación 22500/365000 = 0.062)
No tengo Python en esta máquina, así que si alguien pudiera calificar esto, estaría agradecido. Si no, tendrá que esperar.
El cuello de botella es la adición para calcular la sección relevante del triángulo de Pascal (90% del tiempo de ejecución), por lo que usar un mejor algoritmo de multiplicación realmente no ayudaría.
Tenga en cuenta que lo que llama la pregunta
n
es lo que yo llamo2n
. El argumento de la línea de comandos es lo que llama la preguntan
.fuente
javac CodeGolf37270.java
) y ejecutándose con Java 1.8 (java CodeGolf37270 n
). No estoy seguro de si hay opciones de optimización que desconozco. No puedo intentar compilar con Java 1.8, porque no se instala con mi paquete Java ...GMP - 1500000/300000 = 5.0
Aunque esta respuesta no competirá contra los tamices, a veces el código corto aún puede obtener resultados.
fuente
Java, clase entera grande personalizada: 32.9 (120000000/365000)
La clase principal es bastante sencilla:
Se basa en una gran clase entera que está optimizada para la multiplicación y
toString()
que son cuellos de botella significativos en una implementación conjava.math.BigInteger
.El gran cuello de botella es la multiplicación ingenua (60%), seguida de la otra multiplicación (37%) y el tamizado (3%). La
digsum()
llamada es insignificante.Rendimiento medido con OpenJDK 7 (64 bit).
fuente
Python 2 (PyPy), 1,134,000 / 486,000 = 2.32
Resultado: 1,537,506
Dato curioso: el cuello de botella de su código es agregar los dígitos, no calcular el coeficiente binomial.
fuente
Java (2,020,000 / 491,000) = 4.11
actualizado, previamente 2.24
Java
BigInteger
no es el generador de números más rápido, pero es mejor que nada.La fórmula básica para esto parece ser
n! / ((n/2)!^2)
, pero parece un montón de multiplicación redundante.Puede obtener una aceleración significativa al eliminar todos los factores primos que se encuentran tanto en el numerador como en el denominador. Para hacer esto, primero ejecuto un tamiz primario simple. Luego, para cada cebado, mantengo un recuento del poder al que necesita elevarse. Incremento cada vez que veo un factor en el numerador, decremento para el denominador.
Manejo dos por separado (y primero), ya que es fácil contarlos / eliminarlos antes de factorizar.
Una vez hecho esto, tiene la cantidad mínima de multiplicaciones necesaria, lo cual es bueno porque BigInt multiplica es lento .
Ah, y la suma de salida para n = 2020000 es
2735298
, para fines de verificación.fuente