Merci encore à ceux qui ont participé, et merci pour votre patience avec ce post tardif. Tout le monde a pu relever les défis. Les défis liés aux plus grands nombres ajoutés (~ 2 millions de chiffres) et aux plus grandes listes de 1 000 chiffres (~ 2 000 éléments) pour le personnel non-JMP ont été surmontés par @David_Burnham . Pour les entrées du personnel, les deux plus grands nombres ajoutés en moins de 5 secondes étaient d'environ 22 millions ( @brady_brady et @Craige_Hales ) et la plus grande liste comptait environ 61 500 éléments ( Défi 3 Exemple 3.JSL ). Ces scripts ont été publiés ci-dessous.
Voici les totaux de points à travers trois défis :
Commençons par les opérations impliquant deux nombres. Défi 3 Exemple 1 – slow.JSL fournit une implémentation similaire à la plupart des entrées :
- Déterminez si les nombres sont des signes identiques (addition) ou opposés (soustraction).
- Analysez la chaîne numérique.
- Effectuez les opérations d’addition/soustraction.
- Concaténez les résultats pour construire la réponse.
Que les opérations d'addition et de soustraction soient effectuées dans une seule fonction ou dans plusieurs fonctions est une question de style et ne devrait affecter que la clarté et la lisibilité du programme, mais pas le temps d'exécution. Ce qui fera une énorme différence, cependant, c'est la façon dont les nombres d'entrée sont analysés et reconstitués. Analyser les chaînes d'entrée avant de parcourir les chiffres individuels ( Défi 3 Exemple 1 – plus rapide.JSL ) plutôt qu'à l'intérieur de la boucle, l'opération est multipliée par environ 5 (2,28 secondes contre 0,464 secondes pour l'ajout de 2 nombres de 16 000 chiffres). Supprimer les concaténations de chaînes individuelles de l'intérieur des boucles en collectant les résultats dans une liste puis en concaténant les éléments à la fin accélère les choses de plus de 10 fois (0,04054 sec) - voir (Défi 3, exemple 1 - le plus rapide.JSL).
Avant de parler de la façon de rendre cela encore plus rapide, nous devrions parler de l'ajout de nombres dans une liste. Presque tout le monde a résolu ce problème en parcourant la liste un élément à la fois, en ajoutant chacun à un total cumulé. Bien que ce ne soit pas finalement l’approche la plus rapide, elle pourrait être réalisée exceptionnellement rapidement ( Défi 3 - Hales.JSL ajouté 51 000 numéros à 1 000 chiffres en moins de 5 secondes). Comme pour la plupart des opérations, la clé de l’amélioration de la rapidité est de minimiser le nombre d’opérations, toutes choses égales par ailleurs. Dans l'exemple fourni, Défi 3 Exemple 2.JSL , la solution consistait à réduire les opérations de report/emprunt d'une seule série pour chaque paire de nombres à trois séries au total. Ceci a été accompli par :
- Chargement des nombres d'entrée dans deux matrices, une pour les nombres positifs et une pour les nombres négatifs.
- Ajoutez chaque matrice séparément en utilisant V Somme , effectuez un ensemble d'opérations de report pour les deux matrices de résultats.
- Soustrayez le plus petit nombre du plus grand nombre. Effectuez un ensemble d’opérations d’emprunt une fois pour les résultats. La soustraction finale est effectuée à l’aide de l’algorithme à deux nombres évoqué ci-dessus.
Les opérations à deux chiffres et de liste peuvent être effectuées encore plus rapidement en considérant plus d'un chiffre à la fois pendant les opérations de report/emprunt. Cela a été fait dans les deux Défi 3 - Hales.JSL et Défi 3 - Brady.JSL . Alors que la tendance naturelle est d'ajouter/soustraire/reporter/emprunter avec un seul nombre, la procédure peut, avec un peu d'ingéniosité, être généralisée à autant de nombres que possible, à condition qu'il n'y ait pas de débordement. Dans JMP , ce serait 14 chiffres pour le cas à deux chiffres et 14 – Étage (Journal10( listeTaille - 1)) chiffres , où listeTaille est le nombre d'éléments dans la liste d'entrée, dans le cas de la liste. Pour comprendre pourquoi il en est ainsi, rappelons que le débordement se produit vers 9e16. L'ajout des deux plus grands nombres à 15 chiffres (quinze 9) provoque une erreur de débordement. L’addition des deux plus grands nombres à 14 chiffres ne fonctionne pas. De même, l'ajout de 9 999 999 999 999 à lui-même provoquera un débordement lorsqu'il est effectué entre 11 et 100 fois (91 fois, pour être exact).
À titre d'exemple de la façon dont cela pourrait fonctionner, envisagez d'ajouter trois nombres, chaque nombre étant disposé en registres de 14 :
11 999999999999999
22 999999999999999
33 99999999999999
La somme des valeurs du premier registre (les 14 9) vous donne
2 999999999999997
Porter le 2 et additionner le deuxième registre vous donne
68
Le numéro final est
68 999999999999997
L'application de cette approche est donnée dans Défi 3 Exemple 3.JSL . Le temps de traitement moyen pour l'ajout de deux nombres de 2 millions de chiffres passe de 4,7 à 0,82 seconde, soit une amélioration de vitesse de plus de 5 fois. Des ajustements supplémentaires peuvent améliorer la vitesse de 2 fois supplémentaires, comme en témoigne Défi 3 - Hales.JSL et Défi 3 - Brady.JSL Le temps nécessaire pour ajouter 10 000 numéros à 1 000 chiffres est réduit de 4,5 à 0,88 seconde (5X). Il en résulte l’approche d’ajout de liste la plus rapide.
20 juillet 2020 : Encore une correction de bug, cette fois pour Défi 3 Exemple 3.JSL . Ajout de messages d'avertissement lors de l'utilisation d'un argument matriciel pour les trois fichiers de l'exemple 1 (non implémenté avant l'exemple 2).
17 juillet 2020 : J'ai trouvé un autre bug dans les scripts du Challenge 3 Exemple 1 et les trois ont été corrigés et remplacés.
16 juillet 2020 : j'ai remplacé les scripts Défi 3 Exemple 1 - slow.JSL et Défi 3 Exemple 1 - plus rapide.JSL car ils contenaient une ligne à la fin qui pose problème (ils font référence à une table que j'utilisais pour tester le code). Si vous avez téléchargé ces fichiers et n'avez pas résolu le problème vous-même, veuillez remplacer vos anciennes copies.
