Spero che vi siate divertiti con la Sfida 4. In futuro, se avete un'idea per qualcosa che potrebbe essere una buona Sfida, fatemelo sapere. Sono sempre alla ricerca di buon materiale!
Congratulazioni, @landon ! Hai avuto le voci più veloci (non-staff) per entrambe le sfide da 100 coppie di numeri da 1.000 cifre (9,88 sec) e da cifra più lunga (7.150). Non solo era l'unico script in grado di leggere tutte le 100 coppie di numeri da 1.000 cifre in meno di 10 secondi (il secondo più vicino riusciva a gestirne solo 10), ma poteva anche moltiplicare due numeri 3,5 volte più grandi del secondo più vicino! Inoltre, era il più breve di tutti gli script (staff e non-staff) con poco più di 1.000 caratteri. L'ho incluso negli script qui sotto. I punteggi totali dopo quattro sfide sono:
Prima di parlare di moltiplicazione di numeri grandi, parliamo di come decomprimere o vettorizzare una stringa di cifre, ovvero trasformare una stringa di cifre in un vettore di numeri. Come abbiamo visto il mese scorso, analizzare una stringa di cifre una alla volta usando Sottotipo in un ciclo è dolorosamente lento. Questo ci lascia due alternative generali: 1) decostruire la stringa in singole unità, quindi rimetterle insieme in una forma che può essere trasformata in un vettore (usando Analizzare , ad esempio) o, 2) usare il pattern matching. La mia inclinazione iniziale sarebbe quella di usare l'approccio 1. Per anni, ho resistito all'apprendimento delle funzioni di pattern matching JSL. Lo sforzo era troppo grande, le informazioni e gli esempi troppo scarsi, ed ero troppo pigro. Ho pensato di avere tutto ciò di cui avevo bisogno con la funzione Espressione regolare , qualcosa che conoscevo molto bene. Non più.
Queste sfide mi hanno aperto gli occhi sulla velocità e l'efficienza del pattern matching. Come mi ha spiegato @Craige_Hales , lo sviluppatore responsabile di queste funzioni e partecipante abituale alle sfide, le routine di pattern matching in JSL sono la base su cui è costruito Espressione regolare . Per dimostrare la loro efficienza, esegui il codice in Esempio di vettorizzazione.JSL , che confronta quattro diversi metodi di vettorizzazione. Ho anche incluso una breve funzione per generare una lunga stringa di numeri casuali nello script. Per una stringa di 10.000 numeri, analizzare le cifre una alla volta in un ciclo è, di gran lunga, il più lento, impiegando circa 11 secondi sulla mia macchina. Utilizzare Parole e Elenco di concatenazione per decostruire e ricostruire le cifre in una stringa che può essere analizzata in un vettore è di gran lunga meglio (0,0965 sec).
Fare la stessa cosa usando Espressione regolare e Analizzare è leggermente meglio (0,08543). Il pattern matching riduce questo tempo di ben 4X (0,02179)! Mentre le differenze di tempo sono minuscole per 50.000 cifre, se consideriamo 5.000.000 di cifre, entrambi gli approcci di parsing impiegano circa 10 minuti mentre il pattern matching impiega 2 secondi, scalando quasi linearmente, a differenza degli altri metodi! Se vuoi saperne di più sul pattern matching in JSL, dai un'occhiata agli script scritti da @Craige_Hales o @David_Burnham (che ha alcuni post di blog con maggiori informazioni ed esempi ).
Passiamo alle routine di moltiplicazione. Il pattern matching viene utilizzato per tutte le vettorizzazioni. Inoltre, nel primo esempio vengono utilizzati gli algoritmi di addizione più rapidi dell'ultima sfida. Il primo approccio ( moltiplicaBig Lento.JSL ) non utilizza nulla oltre a quanto abbiamo imparato finora nelle sfide. Moltiplica le cifre due alla volta, assicurandosi di aggiungere zeri a seconda della posizione del moltiplicando e del moltiplicatore (ad esempio, aggiungendo cinque zeri quando una cifra delle centinaia viene moltiplicata per una cifra delle decine). Nonostante la funzione ordini gli input in modo che il primo sia più grande, questo non è di alcun beneficio. Viene eseguito lo stesso numero di operazioni. Questo cambierà nell'esempio finale, tuttavia. La funzione è lenta, impiegando quasi 30 secondi per elaborare un set di 100 numeri da 100 cifre.
In moltiplicareGrande Più Veloce.JSL il numero di cifre in un registro è aumentato da uno a sette, circa la metà del numero di cifre che JSL può rappresentare senza overflow. Il motivo di questa scelta è evidente quando moltiplichiamo due grandi numeri di sette cifre, il cui risultato può essere grande quanto quattordici cifre. Poiché un registro di sette cifre può contenere 14 cifre, la routine di addizione utilizzata nell'ultimo esempio deve essere modificata in modo che tutto ciò che va oltre la settima cifra venga trasferito al registro successivo. Nonostante ciò, il codice risultante è notevolmente più breve poiché devono essere considerati solo numeri positivi. Inoltre, i risultati migliorano notevolmente per la moltiplicazione di 100 coppie di numeri di 100 cifre (0,04375 sec). Questa implementazione fa anche un lavoro ragionevole moltiplicando 100 coppie di numeri di 1000 cifre (1,54 sec).
Con una semplice modifica, puoi andare ancora più veloce. Invece di moltiplicare un registro alla volta, moltiplicareGrande Più veloce.JSL usa le operazioni di matrice JSL per moltiplicare ogni registro nel numero più corto con l'intero numero più grande. Questo approccio è più veloce del precedente, con un tempo di 0,3015 secondi per 100 coppie di 1.000 cifre, un miglioramento di 5 volte.
E puoi andare ancora più veloce. Il file moltiplicareBig – Brady.JSL , sebbene leggermente più lento per moltiplicare numeri di 1.000 cifre, era superiore quando la dimensione dei numeri raggiungeva circa 2.000 cifre e oltre. Ciò è stato ottenuto modificando l'ordine delle operazioni in modo che le moltiplicazioni e le addizioni potessero essere eseguite nello stesso ciclo. I dettagli dietro a questo vanno oltre ciò che desidero trattare, ma @brady_brady mi dice che sarebbe felice di scrivere un breve articolo che posso aggiungere a questo post se c'è interesse. Più veloce? Forse. Ci sono due notevoli algoritmi di moltiplicazione tipicamente usati in crittologia che riducono il numero di operazioni di moltiplicazione da O(n 2 ) a O(n 1.58 ) o inferiore . Poiché richiedono più operazioni di addizione con numeri grandi, è difficile dire se sarebbero più veloci in JSL. Al momento di questo post, ho provato ma non sono riuscito a implementare una versione JSL veloce di nessuno di questi algoritmi.
1 agosto 2020: Grazie a @Craige_Hales per aver trovato un bug in moltiplicareGrande Più veloce.JSL . Ho corretto il problema. Ho anche aggiunto lo script multiplyBig di Craige, che intendevo fare ma ho dimenticato. Utilizza le tabelle di ricerca come un modo per velocizzare l'algoritmo (con qualche avvertenza). Il suo script è completamente commentato, come al solito.
