Con el reciente ataque a Python , aquí hay un intento de mostrar las fortalezas de Python. Su desafío es escribir un programa que calcule el factorial de un número tan alto como sea posible en 10 segundos.n
Tu puntaje será (highest n for your program on your machine)/(highest n for my program on your machine)
Reglas
- Debe calcular una solución entera exacta. Dado que el factorial sería mucho más alto de lo que cabe en un entero sin signo de 64 bits, puede usar cadenas si su idioma no admite enteros grandes
- Las lagunas estándar están prohibidas. En particular, no puede utilizar ningún recurso externo.
- Solo la parte de cálculo (esto incluye el tiempo para cualquier solución alternativa que use cadenas) se suma al tiempo total que debe ser inferior a 10 segundos en promedio.
- Solo programas de subproceso único.
- Debe almacenar la salida en una forma fácilmente imprimible (ya que la impresión lleva tiempo) (vea mi programa a continuación), cadena, variable, matriz de caracteres, etc.
EDITAR:
- Su programa debe dar la salida correcta para todos
n
:1 <= n <= (your highest n)
EDIT2:
- Odio decir esto explícitamente, pero el uso de las funciones factoriales incorporadas en su idioma se encuentra dentro de las lagunas estándar http://meta.codegolf.stackexchange.com/a/1078/8766 Lo sentimos, Mathematica y Sage
Mi programa
from __future__ import print_function
import time
def factorial( n ):
return reduce( ( lambda x , y : x * y ) , xrange( 1 , n + 1 ) , 1 )
start = time.clock()
answer = factorial( 90000 )
end = time.clock()
print ( answer )
print ( "Time:" , end - start , "sec" )
La puntuación más alta gana. Para el registro, mi código puede administrar n = 90000
en unos 9.89
segundos en un Pentium 4 3.0 GHz
EDITAR: ¿Pueden todos agregar la puntuación en lugar de solo la n más alta ? Solo lo más alto n
no tiene sentido en sí mismo, ya que depende de su hardware. De lo contrario, es imposible tener un criterio ganador objetivo. La respuesta de ali0sha hace esto correctamente.
Tenemos un ganador. No acepté la respuesta de Java /codegolf//a/26974/8766, ya que se trata de faldas cercanas a http://meta.codegolf.stackexchange.com/a/1080/8766
fuente
operator.mul
lugar de la función lambdafactorial(Inf)
regresaInf
en una fracción de segundo.Respuestas:
C ++ con GMP, puntaje = 55.55 (10,000,000 / 180,000)
fuente
Python 2.7
42.575 = (6,812,000 / 160,000) aprox.
Código:
Prueba:
Salida:
Cómo funciona:
Las multiplicaciones más grandes toman más tiempo, por lo tanto, queremos hacer tantas multiplicaciones pequeñas como sea posible. Esto es especialmente cierto en Python, donde para números menores
2^64
usamos aritmética de hardware y, por encima, usamos software. Entonces, enm(L)
, comenzamos con una listaL
; Si tiene una longitud impar, eliminamos un número de la consideración para que sea par nuevamente. Luego multiplicamos elemento1
con elemento-2
, elemento3
con-4
, etc., para queEste enfoque asegura que estemos usando aritmética de hardware durante el mayor tiempo posible, después de lo cual cambiamos a la eficiente biblioteca aritmética gmc.
En
fac2
, tomamos un enfoque más clásico de dividir y conquistar, donde dividimos cada múltiplo de 2 y los desplazamos al final para obtener un aumento de rendimiento trivial. Lo he incluido aquí porque generalmente es alrededor de 0.5% más rápido quefac1
.Versión de golf de
fac1
(porque puedo), 220Bfuente
gmpy2
a partir de? $ python Python 2.7.3 (predeterminado, 27 de febrero de 2014, 19:58:35) [GCC 4.6.3] en linux2 Escriba "ayuda", "copyright", "créditos" o "licencia" para obtener más información. >>> desde gmpy2 import mpz Traceback (última llamada más reciente): Archivo "<stdin>", línea 1, en <module> ImportError: Ningún módulo llamado gmpy2 >>>while len(L): ...
lugar dewhile len(L)>1: ...
?Java - 125.15 (21,400,000 / 171,000)
También copiado descaradamente del repositorio Github de Peter Luschny (gracias @ semi-extrínseco) y con licencia bajo la licencia MIT, esto utiliza el algoritmo de "cuadratura anidada de factorización principal" propuesto por Albert Schönhage et al. (según la página de descripción de algoritmos factoriales de Luschny ).
Adapte ligeramente el algoritmo para usar BigInteger de Java y no usar una tabla de búsqueda para n <20.
Compilado con gcj, que usa GMP para su implementación BigInteger, y se ejecutó en Linux 3.12.4 (Gentoo), en un Core i7 4700MQ a 2.40GHz
fuente
gcj -O3 --main=PrimeSieveFactorialSchoenhage PrimeSieveFactorialSchoenhage.java -o pf_nest_square_fact
Python 3, n = 100000
Un simple cambio de algoritmo fue todo lo que se necesitó para aumentar el código de muestra en 10000.
Obviamente no es la respuesta más creativa, pero en realidad solo hay una forma de hacer un factorial ...
fuente
Perl + C, n = aproximadamente 3 millones
Aquí estoy usando la biblioteca Math :: BigInt :: GMP disponible en CPAN, que proporciona un aumento de velocidad masivo para los objetos básicos Math :: BigInt de Perl.
Tenga en cuenta que mi computadora es probablemente un poco más lenta que la suya. Usando su script Python original, solo puedo calcular
factorial(40000)
en 10 segundos;factorial(90000)
Toma mucho más tiempo. (Golpeé Ctrl + C después de un minuto.) En su hardware, usando Math :: BigInt :: GMP, es posible que pueda calcular el factorial de 5 millones o más en menos de 10 segundos.Una cosa que puede notar es que, aunque el factorial se calcula increíblemente rápido, la impresión del resultado es muy lenta, ya que tarda aproximadamente tres veces más que el cálculo original. Esto se debe a que GMP usa internamente una representación binaria en lugar de decimal, e imprimirla requiere una conversión binaria a decimal.
fuente
Math::BigInt
Python 2.7
5.94 = 1'200'000 / 202'000
Hace uso de la relativa facilidad de multiplicación de muchos grupos de números pequeños y luego los multiplica en comparación con un gran número de multiplicaciones que involucran un gran número.
fuente
C #: 0,48 (77,000 / 160,000)
No estoy contento con esto.
¿C # es tan lento?
Pero aquí está mi entrada de todos modos.
Cuando n = 77000 se tarda
00:00:09:8708952
en calcular.Estoy corriendo en modo Release, fuera de Visual Studio, usando un Core i3-2330M @ 2.2GHz.
Editar: Como no estoy haciendo nada inteligente, acepto ese resultado. Tal vez .NET Framework 4.5 está agregando algunos gastos generales (o BigInteger no es tan rápido).
fuente
n
zero approached by
operador para hacerlo más bonito (como comenzar conn = ... + 1
luego hacerwhile (0 <-- n) result *= n;
)bc, puntaje = 0.19
Qué diablos, aquí está mi contendiente para "¿Cuánto puedes multiplicar lentamente?"
bc es "Un lenguaje de calculador de precisión arbitrario", pero desafortunadamente bastante lento:
En aproximadamente 10 segundos en mi MacBook Pro de mediados de 2012 (Intel Core i7 de 2.3 GHz), la respuesta de Python de referencia puede calcular 122000, ¡pero este script bc solo puede calcular 23600 !.
Por el contrario 10000! toma 1.5s con el script de referencia de python, pero el script bc toma 50s.
Oh querido.
fuente
read()
, así que corrítime sed 's/read()/28000/' factorial.bc | bc
.Bash: puntaje = 0.001206 (181/150000)
Robé las funciones matemáticas de Rosettacode: multiplicación larga que no analicé ni intenté optimizar.
Puede cambiar el algoritmo o probar un método diferente de división de cadenas.
fuente
Python 3, algo avanzado de Peter Luschny: 8.25x (1 280 000/155 000)
Copiado descaradamente de Peter Luschny,
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm ,
quien proporciona este código bajo la licencia "Creative Commons Attribution-ShareAlike 3.0".
Este es en realidad un algoritmo bastante avanzado, que utiliza algo llamado "factorial oscilante" y una lista de números primos. Sospecho que podría ser aún más rápido si le gustaran muchas de las otras respuestas y realizara la mayoría de las multiplicaciones con enteros de 32 bits.
fuente
Java - 10.9
n = 885000
Mergesort-y.
BigInteger
s son lentos.¿Recomendaciones para bibliotecas de enteros Java de alta velocidad y precisión arbitraria? :PAG
fuente
C ++ (específico x86_64) - 3.0 (390000/130000)
(fácilmente portátil a x86-32, portar a otras arquitecturas implica una pérdida de velocidad significativa)
Aquí está mi propia micro implementación de aritmética larga.
El cálculo en sí mismo toma 10 segundos, y aunque la salida está en forma fácilmente imprimible (vea la
operator<<
sobrecarga), toma más tiempo imprimirla.fuente
g++ -O2 factorial.cc -o factorial
un puntaje de 3.90 = 382000 / 98000.r
aumenta. Si es así, y puede hacer un mayorr
en 10 segundos, entonces su puntaje baja.Python 3: 280000/168000
Tiempo de ejecución de su programa: entre
9.87585953253
y10.3046453994
. Tiempo de ejecución de mi programa: aproximadamente10.35296977897559
.Leí esta respuesta en cs.SE y decidí intentar implementarla en Python. Sin embargo, descubrí accidentalmente que
n! = (⌊n / 2⌋)! * 2**(⌊n / 2⌋) * n!!
(nota:!!
es el factorial doble ). Entonces lo convertí a una forma no recursiva.Los comentarios muestran mi intento de evitar volver a calcular el factorial doble, pero descubrí que almacenar cada valor era demasiado costoso para la memoria y hacía que mi computadora funcionara aún más lentamente. Puedo mejorar esto almacenando solo lo que se necesita.
Curiosamente, implementé la ingenua multiplicación directa en Python 3, y funciona mejor que su programa:
n = 169000
en 10 segundos .:fuente
Ruby 2.1
puntuación = 1.80 = 176_000 / 98_000
EDITAR: mejorado de
1.35 = 132_000 / 98_000Tomé ideas del algoritmo factorial GMP . Este programa usa la biblioteca estándar para generar números primos. Ruby es una mala elección porque la multiplicación parece más lenta en Ruby que en Python.
Sí, mi binario de
ruby 2.1.0p0 (2013-12-25 revision 44422) [x86_64-openbsd]
enlaces contra GMP. Ruby 2.1 agregó una función para usar GMP para una multiplicación grande, pero aún parece más lenta que Python 2.7.fuente
Julia - Puntuación = 15.194
Utilizando exactamente el mismo enfoque que el del programa de referencia ... es decir,
Por lo tanto, utiliza reducir, la operación básica de multiplicación binaria y un rango (en este caso, usar big (n) para forzar el cálculo a realizar en BigInt en lugar de Int64). De esto, obtengo
En mi computadora, con el programa de referencia ejecutándose con una entrada de 154000, obtengo
Time: 10.041181 sec
salida (ejecutar usandopython ./test.py
, donde test.py es el nombre del archivo que contiene el código de referencia)fuente
tcl, 13757
Mi respuesta es verificar los límites de tcl.
La primera línea es solo para establecer un parámetro de entrada:
Los otros son el algoritmo mismo:
Probé mi código en http://rextester.com/live/WEL36956 ; Si hago n más grande, obtengo un SIGKILL; may n puede crecer en un intérprete tcl local, que no tengo.
fuente