J'espère que vous vous êtes amusé avec Défi 4 . À l’avenir, si vous avez une idée de quelque chose qui pourrait constituer un bon défi, n’hésitez pas à me le faire savoir. Je suis toujours à la recherche de bon matériel !
Toutes nos félicitations, @se poser sur !Vous avez eu les entrées (non-personnel) les plus rapides pour les 100 paires de 1 000 chiffres (9,88 secondes) et les défis avec les chiffres les plus longs (7 150). Non seulement c'était le seul script capable de lire les 100 paires de nombres à 1 000 chiffres en moins de 10 secondes (le prochain plus proche ne pouvait en gérer que 10), mais il pouvait également multiplier deux nombres 3,5 fois plus grands que l'entrée suivante la plus proche ! De plus, c'était le plus court de tous les scripts (personnel et non-personnel) avec un peu plus de 1 000 caractères. Je l'ai inclus dans les scripts ci-dessous. Le total de points après quatre défis est :
Avant de parler de multiplication de grands nombres, parlons de décompresser ou de vectoriser une chaîne de chiffres – transformer une chaîne de chiffres en un vecteur de nombres. Comme nous l'avons vu le mois dernier, analyser une chaîne de chiffres un par un en utilisant Sous-titre dans une boucle est terriblement lent. Cela nous laisse deux alternatives générales : 1) déconstruire la chaîne en unités individuelles, puis les reconstituer sous une forme qui peut être transformée en vecteur (en utilisant Analyser , par exemple) ou, 2) en utilisant la correspondance de modèles. Mon inclination initiale serait d’utiliser l’approche 1. Pendant des années, j'ai résisté à l'apprentissage des fonctions de correspondance de modèles JSL. L’effort était trop important, les informations et les exemples trop rares et j’étais trop paresseux. Je pensais que j'avais tout ce dont j'avais besoin avec le Expression régulière fonction, quelque chose que je connaissais très bien. Pas plus.
Ces défis m’ont ouvert les yeux sur la rapidité et l’efficacité de la correspondance de modèles. Comme me l'a expliqué @Craige_Hales , développeur responsable de ces fonctions et participant régulier aux défis, les routines de correspondance de modèles en JSL constituent la base sur laquelle Expression régulière est construit. Pour démontrer leur efficacité, exécutez le code dans Exemple de vectorisation.JSL , qui compare quatre méthodes différentes de vectorisation. J'ai également inclus une courte fonction pour générer une longue chaîne de nombres aléatoires dans le script. Pour une chaîne de 10 000 nombres, l’analyse des chiffres un par un dans une boucle est de loin la plus lente, prenant environ 11 secondes sur ma machine. En utilisant Mots et Liste de concaténation déconstruire et reconstruire les chiffres en une chaîne qui peut être analysée en un vecteur est un monde meilleur (0,0965 sec).
Faire la même chose en utilisant Expression régulière et Analyser est légèrement meilleur que cela (0,08543). La correspondance de motifs réduit ce temps d'un incroyable 4X (0,02179) ! Alors que les différences de temps sont minuscules pour 50 000 chiffres, si l'on considère 5 000 000 de chiffres, les deux approches d'analyse prennent environ 10 minutes alors que la correspondance de modèles prend 2 secondes, avec une mise à l'échelle presque linéaire, contrairement aux autres méthodes ! Si vous souhaitez en savoir plus sur la correspondance de modèles en JSL, jetez un œil aux scripts écrits par @Craige_Hales ou @David_Burnham (qui a quelques articles de blog avec plus d'informations et d'exemples .)
Passons aux routines de multiplication. La correspondance de motifs est utilisée pour toutes les vectorisations. De plus, les algorithmes d’addition les plus rapides du dernier défi sont utilisés dans le premier exemple. La première approche ( multiplierBig Slow.JSL ) n'utilise rien au-delà de ce que nous avons appris dans les défis jusqu'à présent. Il multiplie les chiffres deux à la fois, en veillant à ajouter des zéros en fonction de la position du multiplicande et du multiplicateur (par exemple, en ajoutant cinq zéros lorsqu'un chiffre des centaines est multiplié par un chiffre des dizaines). Malgré la fonction ordonnant les entrées pour que la première soit plus grande, cela ne présente aucun avantage. Le même nombre d'opérations est effectué. Cependant, cela changera dans le dernier exemple. La fonction est lente, prenant près de 30 secondes pour parcourir une série de 100 nombres à 100 chiffres.
Dans multiplierBig Faster.JSL le nombre de chiffres dans un registre passe de un à sept, soit environ la moitié du nombre de chiffres que JSL peut représenter sans débordement. La raison de ce choix apparaît clairement lorsque l’on multiplie deux grands nombres à sept chiffres, dont le résultat peut atteindre quatorze chiffres. Puisqu'un registre à sept chiffres peut contenir 14 chiffres, la routine d'addition utilisée dans le dernier exemple doit être modifiée afin que tout ce qui dépasse le 7ème chiffre soit transféré au registre suivant. Malgré cela, le code résultant est considérablement plus court puisque seuls les nombres positifs doivent être pris en compte. De plus, les résultats s'améliorent considérablement en multipliant 100 paires de nombres à 100 chiffres (0,04375 s). Cette implémentation fait également un travail raisonnable en multipliant 100 paires de 1 000 chiffres (1,54 s).
Avec un simple changement, vous pouvez aller encore plus vite. Plutôt que de multiplier un registre à la fois, multiplierBig Fastest.JSL utilise les opérations matricielles JSL pour multiplier chaque registre du nombre le plus court par le nombre entier le plus grand. Cette approche est plus rapide que la précédente, avec un temps de 0,3015 seconde pour 100 paires de 1 000 chiffres, soit une amélioration de 5 fois.
Et vous pouvez aller encore plus vite. Le fichier multiplierBig – Brady.JSL , bien que légèrement plus lent pour multiplier des nombres à 1 000 chiffres, était supérieur lorsque la taille des nombres atteignait environ 2 000 chiffres et au-delà. Ceci a été réalisé en modifiant l'ordre des opérations afin que les multiplications et les additions puissent être effectuées dans la même boucle. Les détails derrière cela dépassent ce que je souhaite aborder, mais @brady_brady me dit qu'il serait heureux de rédiger un court article que je pourrai ajouter à ce message s'il y a de l'intérêt. Plus rapide? Peut être. Il existe deux algorithmes de multiplication notables généralement utilisés en cryptologie qui réduisent le nombre d'opérations de multiplication de O(n 2 ) à Sur 1,58 ) ou inférieur . Parce qu'ils nécessitent plus d'opérations d'addition avec de grands nombres, il est difficile de dire s'ils seraient plus rapides en JSL. À partir de cet article, j'ai essayé mais je n'ai pas pu implémenter une version JSL rapide de l'un ou l'autre de ces algorithmes.
1er août 2020 : Grâce à @Craige_Hales pour avoir attrapé un bug multiplierBig Fastest.JSL . J'ai corrigé le problème. J'ai également ajouté le script multiplieBig de Craige, que j'avais l'intention de faire mais que j'ai oublié. Il utilise des tables de recherche pour accélérer l'algorithme (avec quelques mises en garde). Son scénario est minutieusement commenté, comme à son habitude.
