Gracias nuevamente a quienes participaron y gracias por su paciencia con esta última publicación. Todos pudieron completar los desafíos. Tanto los desafíos con los números más grandes agregados (~2 millones de dígitos) como con la lista más grande de 1000 dígitos (~2000 elementos) para el personal que no pertenece al JMP fueron superados por @David_Burnham . Para las entradas de personal, los dos números más grandes agregados en menos de 5 segundos fueron aproximadamente 22 millones ( @brady_brady y @Craige_Hales ) y la lista más grande era de unos 61.500 elementos ( Desafío 3 Ejemplo 3.JSL ). Estos scripts se han publicado a continuación.
Aquí están los totales de puntos a través de tres desafíos:
Comencemos con operaciones que involucran dos números. Desafío 3 Ejemplo 1: slow.JSL proporciona una implementación similar a la mayoría de las entradas:
- Determina si los números tienen el mismo signo (suma) o el signo opuesto (resta).
- Analiza la cadena numérica.
- Realizar las operaciones de suma/resta.
- Concatena los resultados para construir la respuesta.
Si las operaciones de suma y resta se realizan en una sola función o en múltiples funciones es una cuestión de estilo y solo debería afectar la claridad y legibilidad del programa, pero no el tiempo de ejecución. Sin embargo, lo que marcará una gran diferencia es cómo se analizan y se vuelven a unir los números de entrada. Analizar las cadenas de entrada antes de recorrer los dígitos individuales ( Desafío 3 Ejemplo 1: más rápido.JSL ) en lugar de dentro del bucle, acelera la operación aproximadamente 5 veces (2,28 segundos frente a 0,464 segundos para sumar 2 números de 16.000 dígitos). Eliminar las concatenaciones de cadenas individuales desde el interior de los bucles recopilando los resultados en una lista y luego concatenando los elementos al final acelera las cosas más de 10 veces (0,04054 segundos); consulte (Desafío 3, ejemplo 1: más rápido.JSL).
Antes de hablar sobre cómo hacer esto aún más rápido, deberíamos hablar sobre agregar números en una lista. Casi todos manejaron este problema recorriendo la lista un elemento a la vez, sumando cada uno a un total acumulado. Si bien, en última instancia, este no fue el enfoque más rápido, podría hacerse excepcionalmente rápido ( Desafío 3 - Hales.JSL añadido 51.000 números de 1.000 dígitos en menos de 5 segundos). Como ocurre con la mayoría de las operaciones, la clave para acelerar las mejoras es minimizar el número de operaciones, en igualdad de condiciones. En el ejemplo proporcionado, Desafío 3 Ejemplo 2.JSL , la solución fue reducir las operaciones de acarreo/préstamo de una vez establecidas para cada par de números a tres conjuntos en total. Esto se logró mediante:
- Cargando los números de entrada en dos matrices, una para números positivos y otra para números negativos.
- Agregue cada matriz por separado usando V suma , realice un conjunto de operaciones de acarreo para las dos matrices de resultados.
- Resta el número menor del número mayor. Realice un conjunto de operaciones de préstamo una vez para obtener los resultados. La resta final se realiza utilizando el algoritmo de dos números discutido anteriormente.
Tanto las operaciones de dos números como las de lista se pueden realizar aún más rápido considerando más de un dígito a la vez durante las operaciones de acarreo/préstamo. Esto se hizo en ambos Desafío 3 - Hales.JSL y Desafío 3: Brady.JSL . Si bien la inclinación natural es sumar/restar/llevar/tomar prestado con un número, el procedimiento puede, con un poco de ingenio, generalizarse a tantos números como sea posible, siempre que no se produzca un desbordamiento. En JMP , esto sería 14 dígitos para el caso de dos números y 14 – Piso(Registro10( tamaño de lista – 1)) dígitos , dónde tamaño de lista es el número de elementos en la lista de entrada, en el caso de lista. Para entender por qué esto es así, recuerde que el desbordamiento ocurre aproximadamente en 9e16. Sumar los dos números más grandes de 15 dígitos (quince 9) provoca un error de desbordamiento. Sumar los dos números más grandes de 14 dígitos no. De manera similar, sumar 9,999,999,999,999 a sí mismo provocará un desbordamiento cuando se realice entre 11 y 100 veces (91 veces, para ser exactos).
Como ejemplo de cómo podría funcionar esto, considere sumar tres números donde cada número esté organizado en registros de 14:
11 99999999999999
22 99999999999999
33 99999999999999
Sumar los valores del primer registro (los 14 9) te da
2 99999999999997
Llevar el 2 y sumar el segundo registro te da
68
El número final es
68 99999999999997
La aplicación de este enfoque se da en Desafío 3 Ejemplo 3.JSL . El tiempo de procesamiento promedio para sumar dos números de 2 millones de dígitos mejora de 4,7 a 0,82 segundos, una mejora de velocidad de más de 5 veces. Los ajustes adicionales pueden mejorar la velocidad otro 2 veces, como lo demuestra Desafío 3 - Hales.JSL y Desafío 3: Brady.JSL El tiempo necesario para sumar 10.000 números de 1.000 dígitos se reduce de 4,5 a 0,88 segundos (5 veces). Esto da como resultado el método de adición de listas más rápido.
20 de julio de 2020: Una corrección de errores más, esta vez para Desafío 3 Ejemplo 3.JSL . Se agregaron mensajes de advertencia al usar un argumento de matriz para los tres archivos del Ejemplo 1 (no implementado hasta el Ejemplo 2).
17 de julio de 2020: Encontré otro error en los scripts del Ejemplo 1 del Desafío 3 y los tres han sido corregidos y reemplazados.
16 julio 2020 : reemplacé los guiones Desafío 3 Ejemplo 1: slow.JSL y Desafío 3 Ejemplo 1: más rápido.JSL porque contenían una línea al final que causa un problema (hacen referencia a una tabla que estaba usando para probar el código). Si descargó estos archivos y no solucionó el problema usted mismo, reemplace sus copias anteriores.
