Spero che ti sia divertito Sfida 4 . In futuro, se hai un'idea per qualcosa che potrebbe costituire una bella sfida, faccelo sapere. Sono sempre alla ricerca di buon materiale!
Congratulazioni, @atterrare su !Hai avuto gli inserimenti più veloci (non personali) sia per le sfide con 100 coppie di 1.000 cifre (9,88 secondi) che per quelle con cifre più lunghe (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 successivo più vicino poteva gestirne solo 10), ma poteva anche moltiplicare due numeri 3,5 volte più grandi della successiva voce più vicina! Inoltre, era la più breve di tutte le sceneggiature (personali e non personali) con poco più di 1.000 caratteri. L'ho incluso negli script seguenti. I punti totali dopo quattro sfide sono:
Prima di parlare di moltiplicazione di grandi numeri, parliamo di scompattare o vettorizzare una stringa di cifre, trasformando una stringa di cifre in un vettore di numeri. Come abbiamo visto il mese scorso, analizzare una stringa di cifre una alla volta utilizzando Sottostr in un ciclo è dolorosamente lento. Questo ci lascia due alternative generali: 1) scomporre la stringa in singole unità, quindi rimetterle insieme in una forma che può essere trasformata in un vettore (usando Analizzare , ad esempio) o 2) utilizzando la corrispondenza dei modelli. La mia inclinazione iniziale sarebbe quella di utilizzare l'approccio 1. Per anni ho resistito all'apprendimento delle funzioni di corrispondenza dei modelli 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 il Regex funzione, cosa che conoscevo molto bene. Non più.
Queste sfide mi hanno aperto gli occhi sulla velocità e sull’efficienza del pattern match. Come mi ha spiegato @Craige_Hales , lo sviluppatore responsabile di queste funzioni e partecipante regolare alle sfide, le routine di corrispondenza dei modelli in JSL sono la base su cui Regex è costruito. Per dimostrare la loro efficienza, esegui il codice Esempio di vettorizzazione.JSL , che mette a confronto quattro diversi metodi di vettorizzazione. Ho incluso anche una breve funzione per generare una lunga stringa di numeri casuali nello script. Per una stringa di 10.000 numeri, l'analisi delle cifre una alla volta in un ciclo è di gran lunga la più lenta, impiegando circa 11 secondi sulla mia macchina. Utilizzando Parole E Elenco Concat decostruire e ricostruire le cifre in una stringa che può essere analizzata in un vettore è molto meglio (0,0965 sec).
Fare la stessa cosa usando Regex E Analizzare è leggermente migliore di quello (0,08543). La corrispondenza dei modelli riduce questa volta di un sorprendente 4X (0,02179)! Mentre le differenze orarie sono minuscole per 50.000 cifre, se consideriamo 5.000.000 di cifre, entrambi gli approcci di analisi richiedono circa 10 minuti mentre la corrispondenza dei modelli richiede 2 secondi, scalando quasi linearmente, a differenza degli altri metodi! Se vuoi saperne di più sulla corrispondenza dei modelli in JSL, dai un'occhiata agli script scritti da @Craige_Hales O @David_Burnham (che ha alcuni post del suo blog con ulteriori informazioni ed esempi .)
Avanti con le routine di moltiplicazione. La corrispondenza dei modelli viene utilizzata per tutta la vettorizzazione. Inoltre, nel primo esempio viene utilizzato l'algoritmo di addizione più veloce dell'ultima sfida. Il primo approccio ( moltiplicareBig Slow.JSL ) non utilizza altro che ciò che 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 ingressi in modo che il primo sia più grande, ciò non apporta alcun vantaggio. Viene eseguito lo stesso numero di operazioni. Tuttavia, ciò cambierà nell'esempio finale. La funzione è lenta e impiega quasi 30 secondi per completare una serie di 100 numeri da 100 cifre.
In moltiplicareBig Faster.JSL il numero di cifre in un registro viene aumentato da uno a sette, circa la metà del numero di cifre che JSL può rappresentare senza overflow. Il motivo di questa scelta risulta evidente quando moltiplichiamo due grandi numeri a sette cifre, il cui risultato può arrivare fino a quattordici cifre. Poiché un registro a 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 portato al registro successivo. Nonostante ciò, il codice risultante è notevolmente più breve poiché devono essere considerati solo i numeri positivi. Inoltre, i risultati migliorano sostanzialmente moltiplicando 100 coppie di numeri da 100 cifre (0,04375 sec). Questa implementazione svolge anche un lavoro ragionevole moltiplicando 100 coppie di 1000 cifre (1,54 secondi).
Con una semplice modifica puoi andare ancora più veloce. Invece di moltiplicare un registro alla volta, moltiplicareBig Fastest.JSL utilizza le operazioni di matrice JSL per moltiplicare ciascun registro nel numero più breve per l'intero numero più grande. Questo approccio è più veloce del precedente, con un tempo di 0,3015 secondi per 100 coppie da 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 questo vanno oltre ciò che mi interessa coprire, 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. Esistono due notevoli algoritmi di moltiplicazione tipicamente utilizzati in crittologia che riducono il numero di operazioni di moltiplicazione da O(n 2 ) A SU 1,58 ) O inferiore . Poiché richiedono più operazioni di addizione con numeri grandi, è difficile dire se sarebbero più veloci in JSL. A partire da 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 catturato un insetto moltiplicareBig Fastest.JSL . Ho corretto il problema Ho anche aggiunto lo script multiplyBig di Craige, cosa che intendevo fare ma che ho dimenticato. Utilizza le tabelle di ricerca come un modo per velocizzare l'algoritmo (con alcuni avvertimenti). La sua sceneggiatura è completamente commentata, come al solito.
