Grazie ancora a coloro che hanno partecipato e grazie per la pazienza con questo post in ritardo. Tutti sono stati in grado di completare le sfide. Sia la sfida con i numeri più grandi aggiunti (~2 milioni di cifre) sia quella con l'elenco più grande di 1.000 cifre (~2.000 elementi) per il personale non JMP sono state superate da @David_Burnham . Per le voci dello staff, i due numeri più grandi aggiunti in meno di 5 secondi sono stati di circa 22 milioni ( @brady_brady E @Craige_Hales ) e l'elenco più grande era di circa 61.500 elementi ( Sfida 3 Esempio 3.JSL ). Questi script sono stati pubblicati di seguito.
Ecco i punti totali attraverso tre sfide:
Cominciamo con le operazioni che coinvolgono due numeri. Sfida 3 Esempio 1 – slow.JSL fornisce un'implementazione simile alla maggior parte delle voci:
- Determina se i numeri sono segni uguali (addizione) o opposti (sottrazione).
- Analizzare la stringa numerica.
- Eseguire le operazioni di addizione/sottrazione.
- Concatena i risultati per costruire la risposta.
Il fatto che le operazioni di addizione e sottrazione vengano eseguite in una singola funzione o in più funzioni è una questione di stile e dovrebbe influenzare solo la chiarezza e la leggibilità del programma, ma non il tempo di esecuzione. Ciò che farà un’enorme differenza, tuttavia, è il modo in cui i numeri di input verranno analizzati e rimessi insieme. Analisi delle stringhe di input prima di eseguire il loop sulle singole cifre ( Sfida 3 Esempio 1 – più veloce.JSL ) anziché all'interno del ciclo accelera l'operazione di circa 5 volte (2,28 secondi contro 0,464 secondi per l'aggiunta di 2 numeri da 16.000 cifre). La rimozione delle singole concatenazioni di stringhe dall'interno dei cicli raccogliendo i risultati in un elenco e quindi concatenando gli elementi alla fine accelera le cose più di 10 volte (0,04054 secondi) – vedere (Sfida 3 Esempio 1 – più veloce.JSL).
Prima di parlare di come renderlo ancora più veloce, dovremmo parlare dell'aggiunta di numeri in un elenco. Quasi tutti hanno gestito questo problema scorrendo l'elenco un elemento alla volta, aggiungendo ciascuno al totale parziale. Sebbene questo non fosse in definitiva l'approccio più veloce, poteva essere reso eccezionalmente veloce ( Sfida 3 - Hales.JSL aggiunti 51.000 numeri da 1.000 cifre in meno di 5 secondi). Come per la maggior parte delle operazioni, la chiave per accelerare i miglioramenti è ridurre al minimo il numero di operazioni, a parità di condizioni. Nell'esempio fornito, Sfida 3 Esempio 2.JSL , la soluzione è stata quella di ridurre le operazioni di riporto/prestito da una sola serie per ciascuna coppia di numeri a tre serie totali. Ciò è stato realizzato da:
- Caricamento dei numeri immessi in due matrici, una per i numeri positivi e l'altra per i numeri negativi.
- Aggiungi ciascuna matrice separatamente utilizzando V Somma , eseguire una serie di operazioni di riporto per le due matrici dei risultati.
- Sottrai il numero più piccolo dal numero più grande. Eseguire una serie di operazioni di prestito una volta per ottenere i risultati. La sottrazione finale viene eseguita utilizzando l'algoritmo a due numeri discusso sopra.
Sia le operazioni a due numeri che quelle su elenco possono essere rese ancora più veloci considerando più di una cifra alla volta durante le operazioni di riporto/prestito. Ciò è stato fatto in entrambi Sfida 3 - Hales.JSL E Sfida 3 - Brady.JSL . Mentre l'inclinazione naturale è quella di aggiungere/sottrarre/riportare/prendere in prestito un numero, la procedura può, con un po' di ingegnosità, essere generalizzata al maggior numero possibile di numeri, a condizione che non si verifichi un overflow. In JMP , questo sarebbe 14 cifre per il caso a due numeri e 14 – Piano(Log10( listSize – 1)) cifre , Dove listSize è il numero di elementi nell'elenco di input, nel caso dell'elenco. Per capire perché è così, ricordiamo che l’overflow avviene intorno alle 9e16. La somma dei due numeri più grandi di 15 cifre (quindici 9) provoca un errore di overflow. La somma dei due numeri più grandi di 14 cifre non lo fa. Allo stesso modo, aggiungere 9.999.999.999.999 a se stesso causerà un overflow quando viene eseguito da 11 a 100 volte (91 volte, per l'esattezza).
Come esempio di come potrebbe funzionare, considera l'aggiunta di tre numeri in cui ciascun numero è organizzato in registri di 14:
1199999999999999
2299999999999999
3399999999999999
Sommando i valori del primo registro (i 14 9) si ottiene
299999999999997
Portando il 2 e sommando il secondo registro si ottiene
68
Il numero finale è
6899999999999997
L'applicazione di questo approccio è riportata in Sfida 3 Esempio 3.JSL . Il tempo medio di elaborazione per l'aggiunta di due numeri da 2 milioni di cifre migliora da 4,7 a 0,82 secondi, con un miglioramento della velocità di oltre 5 volte. Ulteriori modifiche possono migliorare la velocità di un altro 2X, come evidenziato da Sfida 3 - Hales.JSL E Sfida 3 - Brady.JSL Il tempo necessario per aggiungere 10.000 numeri da 1.000 cifre è ridotto da 4,5 a 0,88 secondi (5X). Ciò si traduce nell'approccio di aggiunta dell'elenco più rapido.
20 luglio 2020: Un'altra correzione di bug, questa volta per Sfida 3 Esempio 3.JSL . Aggiunti messaggi di avviso quando si utilizza un argomento matrice per tutti e tre i file dell'Esempio 1 (non implementati fino all'Esempio 2).
17 luglio 2020: Ho trovato un altro bug negli script dell'Esempio 1 della Sfida 3 e tutti e tre sono stati corretti e sostituiti.
16 luglio 2020 : Ho sostituito gli script Sfida 3 Esempio 1 - slow.JSL E Sfida 3 Esempio 1 - Faster.JSL perché contenevano una riga alla fine che causa un problema (fanno riferimento a una tabella che stavo utilizzando per testare il codice). Se hai scaricato questi file e non hai risolto il problema da solo, sostituisci le copie più vecchie.
