Nota: Una entrada de desafío de @David_Burnham Se envió antes de la fecha límite pero mi sistema de correo electrónico lo puso en cuarentena. Solo lo descubrí después de que se publicó la publicación original del blog. Estoy actualizando los resultados para reflejar los cambios basados en la nueva entrada.
Gracias a todos los que enviaron código para el Desafío 2. La puntuación fue un desafío, ya que algunos códigos funcionaban mejor con valores más pequeños y otros con valores más grandes. La siguiente tabla muestra los resultados de cada parte del desafío. Hubo tres carreras para es Prime , 1000 números impares aleatorios de 5 dígitos no divisibles por 5, números impares de 8 y 9 dígitos no divisibles por 5 y números impares de 12 a 15 dígitos no divisibles por 5. Los resultados se basaron en las dos condiciones finales. Los puntos se dividieron entre los desafíos, 1,5 puntos por 1. calle , 1 por 2 Dakota del Norte y 0,5 por 3 tercero . También se proporcionan los tiempos de los envíos más rápidos (en segundos).
@leelaim El tiempo isPrime(Small) fue más rápido que cualquier otro miembro del personal de JMP (+3 puntos). @aterrizar El script isPrime(Big) utiliza la función Parallel Assign para mejorar la velocidad. Dos de las entradas almacenaron en caché sus resultados para obtener números primos usando Espacio de nombres . Este enfoque es útil cuando es necesario acceder a los resultados más de una vez (sin embargo, los tiempos de ejecución se basan en resultados no almacenados en caché). Las cuatro entradas se incluyen a continuación.
Aquí está la clasificación después de dos desafíos:
El desafío 3 se publicará el miércoles 1 de junio.
El desafío 2 pedía encontrar números primos de dos formas posibles. Dado un valor entero positivo norte , tenías que encontrar: 1) norte primos o 2) todos los primos bajo norte . Empecemos por 2) ya que es algo más fácil de implementar. El método más sencillo para encontrar números primos es la división de prueba. Comenzando con 2 como candidato y un conjunto vacío de primos, verifique si algo del conjunto actual de primos divide el número candidato de manera uniforme. Si no, agréguelo al conjunto de números primos y continúe con el siguiente candidato. Como no hay nada en el conjunto principal para comenzar, se suma 2. Al marcar 3, no divide nada en {2} y se suma al conjunto primo. El número 4, sin embargo, divide algo en {2,3} y no se suma. A continuación se muestra un ejemplo de implementación.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
Este enfoque tiene algunas ventajas: es fácil de entender, el código es conciso y se puede adaptar fácilmente para ambos desafíos de búsqueda principal. Desafortunadamente, es extremadamente lento. Encontrar los números primos por debajo de 100.000 me tomó 19.43 segundos .
Un método un poco más complejo es utilizar un colador. En lugar de probar un número para determinar su primalidad, tamiza los números de prueba para eliminar su primalidad. El más antiguo y conocido es el Tamiz de Eratóstenes . Empiece por asumir que todo es primo. Comenzando con 2 como primer primo, encuentre todos los números que lo dividen uniformemente y elimínelos del conjunto primo. Continúe con el siguiente número que todavía está en el conjunto primo. A continuación se muestra una versión no optimizada.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
La ventaja más obvia es la velocidad. Mi tiempo para encontrar todos los números primos por debajo de 100.000 fue de 0,2811 segundos, aproximadamente 70 veces más rápido, y 3,4025 segundos para 1.000.000. El código sigue siendo conciso y fácil de entender. Una desventaja menor es que necesita crear un vector para rastrear números no primos (es decir, no puede hacer crecer la lista mediante concatenación, lo cual veremos más adelante no es necesariamente una ventaja). Esto hace que el problema de encontrar norte los primos son más difíciles porque no sabes exactamente qué tan grande será el vector que necesitarás.
A continuación se muestran dos versiones optimizadas. El primero comienza eliminando todos los múltiplos de dos, luego solo recorre los números impares desde 3 en adelante. cuadrado( norte ) se utiliza para el límite superior del bucle exterior porque todos los no primos menores que ese ya habrán sido eliminados. Por ejemplo, para encontrar todos los números primos menores de 100, solo necesitas tamizar hasta 10. Los números tamizados de cualquier primo mayor que 10 serán el producto de ese primo por un número menor que 10, que se habrá eliminado con algún otro número primo (por ejemplo, 11*5 se elimina con el tamiz de 5, 11*9 con el colador para 3, etc.). Estas mejoras redujeron el tiempo de ejecución a más de la mitad a 1,3545. El segundo muestra la ventaja de utilizar las operaciones matriciales de JSL para el bucle interno, con tiempos de 0,01625 para 1.000.000 y 2,6694 para 100.000.000, ¡una mejora de casi 100 veces!
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
¿Puedes hacerlo mejor? El Tamiz de Atkin es teóricamente más eficiente y se implementó en Ejemplo de primos Atkins.JSL y Primes Atkins (optimizado).JSL . El primero ofrece una implementación no optimizada y más fácil de entender (2,236 segundos para 1.000.000). Mejor que la versión no optimizada de Eratóstenes. La versión optimizada, sin embargo, no pudo vencer a Eratóstenes optimizado (4,914 segundos por 100.000.000). Además, es mucho más largo y complejo, programática y teóricamente.
¿Qué tal leer de una tabla de números? Si bien esto no tiene el espíritu de escribir un algoritmo, no dije que no se pudiera. @Craige_Hales proporcionó una solución utilizando este enfoque. Dada la especificación del problema de norte Para no exceder 1e8, el tamaño del script que contiene los valores comprimidos tomó más de 4 millones de caracteres de código, 4,6 MB de espacio en disco y aproximadamente 5,5 segundos para cargarse, independientemente del tamaño de norte . Más lento que las otras soluciones. Aunque no es ni el más rápido ni el más corto, he incluido el guión de Craige debido a su enfoque único del problema, el uso de la compresión y Asignación paralela .
Hallazgo norte Los números primos son un problema más desafiante. Suponiendo que utiliza un tamiz, necesitará crear un vector de valores hasta el norte décimo primo. Para hacer esto, es necesario estimar un límite superior para ese valor. Se debe evitar la subestimación, ya que puede ser necesario volver a ejecutar parte o la totalidad del algoritmo para encontrar valores no tamizados. Valor estimado de nth prime.jmp muestra 6 estimaciones diferentes. Est1 Da un caso donde los valores se subestiman para pequeñas norte . Muchas estimaciones sólo se aplican a norte mayor que un valor específico y se debe tener cuidado de proporcionar estimaciones alternativas en estos casos. Est2 es bueno para norte ≥ 13 y Est3 mejora eso para valores más grandes. Desafortunadamente, los buenos límites rara vez son simples. Est4 fue utilizado en Prepara el envío rápido.jsl . Si bien no hace un buen trabajo y subestima valores muy grandes de norte , es simple y fácil de recordar. Est5 se derivó utilizando No lineal con los valores reales. Est6 mejora en Est5 perturbando ligeramente los valores para que ninguno de los valores de la tabla se subestime. No se garantiza que no existan subestimaciones entre 100 y 1e8. Las otras columnas de la tabla dan las subestimaciones/sobreestimaciones para cada técnica.
La determinación de la primalidad podría seguir un camino similar al de la generación de números primos. dado un numero X , podrías dejar i = 2. Si Modificación( norte , i ) == 0 detener, en caso contrario incrementar i . Continuar hasta Modificación( norte , i ) == 0 o i == norte . Este código a continuación se beneficia al verificar solo los impares i después de la prueba inicial en i = 2 y deteniéndose cuando i > = Techo(Sqrt( norte )) .
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
El script anterior tarda aproximadamente 1,4 segundos en comprobar los 1.000 números de ocho y nueve dígitos de la tabla. Tabla de números grandes.jmp ( Pequeño ).
Para mejorar esto aún más, puede generar un vector de números primos (hasta Techo(Sqrt( norte )) ) y recorrerlos en iteración.
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
Esto reduce el tiempo en más de la mitad, hasta menos de 0,6 segundos.
Dos notas generales para mejorar la velocidad: En situaciones en las que es necesario utilizar un valor de matriz más de una vez, es más rápido asignar el valor a una variable, utilizando la variable en lugar de la matriz indexada. Si bien esto puede hacer que el código sea más largo, ahorrará tiempo. Pruebe esto reemplazando siguienteVal en el código anterior con su valor de matriz indexado ( inVals[i] ). Segundo, ubicación y la concatenación de matrices es lenta a medida que crece el tamaño de la matriz. Si puedes trabajar con una matriz ordenada, Ubicación ordenada Realiza una búsqueda binaria y es mucho más rápida.Ver Operaciones de matriz de pruebas de velocidad.jsl para obtener ejemplos adicionales sobre referencias de matrices y concatenación.
Intentando encontrar números primos en la columna de números grandes ( Grande ) es más problemático. Encontrar los primeros 10 lleva aproximadamente 1,9 segundos. En este punto, debes confiar en un algoritmo especializado para realizar mejoras. Miller-Rabin (MR) es una técnica comúnmente utilizada y relativamente fácil de implementar para probar la primalidad. Una versión determinista se da en millerRabin1.jsl . MR se basa en la exponenciación modular y se debe tener cuidado para evitar incurrir en errores de desbordamiento. Por sí solo, MR tarda 5,28 segundos en recorrer los 1000 Grande números. Puede que le sorprenda que MR sea más lento que el primer algoritmo isPrime anterior (2,34 segundos) a la hora de trabajar con el Pequeño números. Es probable que esto se deba a que se vuelve más eficiente computacionalmente a medida que los números aumentan de tamaño, lo que sugiere una mejora: pruebe hasta un cierto tamaño primo usando 2) arriba. Si el número es primo, detente. De lo contrario, cambie a MR. Este enfoque se puede encontrar en millerRabin2.jsl . Se realizaron algunos ajustes para encontrar el número ideal de números primos para verificar. Esto redujo el tiempo a la mitad, a 2,33 segundos.
