Comme je suis un développeur amateur qui explore encore les profondeurs de JavaScript et qui n'a jamais écrit ou publié de package auparavant, je ne suis certainement pas en mesure d'enseigner quoi que ce soit à qui que ce soit. Ce que je pouvez faire, cependant, c'est de partager mon expérience dans l'écriture de ce qui est essentiellement encore un package imparfait, mais que j'ai eu beaucoup de plaisir à créer.
Tout a commencé avec un problème dont j'ai été surpris de constater qu'il n'avait pas été beaucoup abordé en ligne, et que j'ai découvert qu'il pouvait être parfaitement résolu d'une manière un peu inattendue : c'est-à-dire en utilisant la récursivité.
Ceux d'entre vous qui aiment le football (ou le sport en général, ou tout environnement compétitif où des classements sont nécessaires) connaissent certainement le concept de tableau de classement : un certain nombre d'équipes s'affrontent dans une séquence de matchs, à l'issue desquels chaque équipe gagne un certain nombre de points selon qu'elle a gagné, fait match nul ou perdu ; un tableau de classement rassemble toutes les équipes par ordre décroissant de points, indiquant ainsi clairement quelle équipe est couronnée vainqueur.
En termes de programmation, c'est une situation qui ne pose aucun problème : vérifier quelle équipe a gagné un match est trivial (en football, c'est aussi simple que de voir laquelle des deux équipes a marqué le plus de buts), et calculer le nombre total de points sur tous les matchs se résume à une simple addition. L'étape de tri n'est pas compliquée non plus, car JavaScript est même livré avec des méthodes de tri par défaut pour les tableaux.
On pourrait imaginer que les choses deviennent un peu moins triviales lorsque deux équipes ou plus terminent à égalité de points, auquel cas un tiebreak est nécessaire. En ce qui concerne le football, les bris d'égalité courants incluent généralement la différence de buts (le nombre de buts marqués moins le nombre de buts encaissés), le nombre de buts marqués, le nombre de victoires, etc. Et cela laisserait, une fois de plus, penser que le problème n'est pas si difficile à résoudre : en cas d'égalité de points, il suffit de passer à un tri des équipes en question selon un critère différent. Même permettre à l'utilisateur de choisir quels critères de départage appliquer, ou dans quel ordre, n'est pas difficile à mettre en œuvre tant que l'ensemble des choix est limité et codé en dur.
Et c’est dans quelle mesure la plupart des solutions en ligne résolvent le problème. Cependant, l’affaire est un peu plus subtile et va plus loin que ce à quoi on pourrait s’attendre au départ.
En vérité, tout type de critère (différence de buts, buts marqués, etc., mais même le nombre de points lui-même) peut être vérifié de deux manières différentes : au sens global (le dite vérification globale), qui est le type de vérification standard où l'on regarde le tableau complet, tel qu'il ressort de tous les matchs qui ont été joué par toutes les équipes et compare les équipes sur cette base ; ou dans un sens restreint (le soi-disant contrôle face-à-face), où si deux équipes ou plus sont à égalité de points, tout bris d'égalité ultérieur est vérifié uniquement dans les matchs joués entre les équipes en question.
Un exemple rendra cette différence claire. Prenez le groupe E de l'UEFA Euro 2016, où la table finale ressemblait à ceci
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Italy | 2 | 0 | 1 | 3 | 1 | 2 | 6 |
| 2 | Belgium | 2 | 0 | 1 | 4 | 2 | 2 | 6 |
| 3 | Republic of Ireland | 1 | 1 | 1 | 2 | 4 | -2 | 4 |
| 4 | Sweden | 0 | 1 | 2 | 1 | 3 | -2 | 1 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
L'Italie et la Belgique sont à égalité de points, et le premier bris d'égalité à l'Euro est la différence de buts (où l'Italie et la Belgique sont toujours à égalité, avec 2 chacune), suivi du nombre de buts marqués, auquel cas on pourrait s'attendre à ce que la Belgique pour triompher de l'Italie, avec 4 buts marqués contre 3.
Cependant, l'Euro est une compétition où un style de face-à-face est utilisé pour trier les équipes qui sont à égalité de points. Cela signifie que, dès que l'on reconnaît que l'Italie et la Belgique doivent Si leur égalité est brisée, on calcule immédiatement un nouveau sous-tableau composé uniquement des équipes concernées par l'égalité. Et comme ils ont joué un seul match qui s'est terminé 0-2 pour l'Italie lors de la toute première journée, ce sous-tableau ressemble à ceci (le football attribue trois points pour une victoire, un pour un match nul et aucun pour une défaite)
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Italy | 1 | 0 | 0 | 2 | 0 | 2 | 3 |
| 2 | Belgium | 0 | 0 | 1 | 0 | 2 | -2 | 0 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
ce qui signifie que l'Italie est immédiatement classée au-dessus de la Belgique, en raison des points en face-à-face (trois à zéro).
Différentes compétitions emploieront généralement des styles différents (les Euros utilisent le style face-à-face comme nous venons de le voir, tandis que par exemple la Coupe du Monde de la FIFA est célèbre pour utiliser des contrôles globaux à la place), bien qu'elles passent toutes les deux à l'autre. style si la première série de critères ne permet pas de briser une égalité donnée.
Cela signifie que, potentiellement, des confrontations sont susceptibles de se produire tôt ou tard (soit immédiatement dans une compétition comme l'Euro, soit dans le cadre d'un deuxième bris d'égalité potentiel lors de la Coupe du Monde de la FIFA). Ce que je retiens ici, c'est que le tableau que nous examinons peut potentiellement changer au cours du processus de tri, car le style du face-à-face (qu'il vienne immédiatement ou non) dépend de cela fait.
Mais ce n'était pas mon seul point à retenir, comme le montre l'exemple suivant.
La Belgique est une fois de plus protagoniste du célèbre Groupe E de l'UEFA Euro 2024, où chaque équipe a terminé son groupe avec 4 points
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Romania | 1 | 1 | 1 | 4 | 3 | 1 | 4 |
| 2 | Belgium | 1 | 1 | 1 | 2 | 1 | 1 | 4 |
| 3 | Slovakia | 1 | 1 | 1 | 3 | 3 | 0 | 4 |
| 4 | Ukraine | 1 | 1 | 1 | 2 | 4 | -2 | 4 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
Comme toutes les équipes sont à égalité de points, le sous-tableau des résultats face-à-face reste de toute façon le tableau complet. La Slovaquie et l'Ukraine sont classées en bas du tableau à la différence de buts, puis la Roumanie est placée devant la Belgique en raison de son nombre supérieur de buts marqués (Roumanie 4, Belgique 2). En effet, voilà à quoi a finalement ressemblé la table finale.
Mais on pourrait trouver cela étrange : il y a eu exactement un match joué entre la Belgique et la Roumanie, que la Belgique a remporté 2-0 lors de la deuxième journée. Alors pourquoi la Belgique n’est-elle pas classée devant la Roumanie ? Cela n'a-t-il pas d'importance ? Pourquoi un sous-tableau n'a-t-il pas été recalculé pour eux après que la Slovaquie et l'Ukraine aient été séparées du reste, comme nous l'avions fait auparavant ?
La vérité est que, selon le règlement de l'UEFA Euro (§20.01-d.), un recalcul des résultats face-à-face n'a pas lieu à chaque étape, mais seulement une fois que la liste complète des bris d'égalité est épuisée. Puisqu'après l'égalité aux points et à la différence de buts, il reste encore à vérifier le nombre de buts marqués, nous regardons cela et cela c'est pourquoi la Roumanie finit par triompher. Si ce avait également été à égalité, seulement à ce stade pourrions-nous effectivement commencer à envisager un sous-tableau basé sur le match unique joué entre les équipes encore à égalité (Belgique et Roumanie), où la Belgique s'imposerait en fait grâce à sa victoire.
Voici donc le deuxième point à retenir : il y a une notion de profondeur impliquée dans le processus de tri, car selon jusqu'où vous en êtes, vous doivent prendre différentes décisions, par exemple s'il faut procéder ou non à un recalcul de sous-table. Dans ce cas, vous ne procéderiez pas tout de suite car la liste des critères est toujours en cours.
Ce sont les principaux points qui ont conduit à ma décision quant à la forme de ma fonction de tri.
L'algorithme de tri, accessible via la méthode .standings() de la classe que mon package implémente, repose sur une fonction récursive
const sortAndDivideTable = (table, iteration, criteria) => {
// ...
}
où, à une table d'étape donnée, se trouve la table contenant les données des équipes qui doivent actuellement être triées, l'itération garde une trace du numéro d'itération et d'autres informations associées (par exemple, s'il s'agit d'un type face-à-face ou global de contrôle), et les critères sont un tableau représentant la liste ordonnée des critères à appliquer (par exemple points, différence de buts, nombre de buts marqués).
La récursivité commence par un tableau qui est calculé à partir de tous les matchs joués par toutes équipes, et qui est encore potentiellement non ordonné. A noter que la première itération de l'algorithme est toujours de type global (et est donc initialisée comme telle lorsque la récursion démarre), car par définition la première vérification est toujours le nombre de points obtenus sur l'ensemble matches; encore une fois par définition, le premier élément du tableau de critères est toujours "points".
Cette table de départ est également bien rangée : à chaque étape, ses entrées ne sont pas modifiées, mais ses lignes seront triées petit à petit. À titre de référence, nous pouvons désormais l’appeler « classement original ».
En gardant cela à l'esprit, il est possible de donner un sens à l'algorithme avec un exemple fourni par le groupe D de l'UEFA Champions League 2013-14, qui a fini par ressembler à ceci
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Bayern Munich | 5 | 0 | 1 | 17 | 5 | 12 | 15 |
| 2 | Manchester City | 5 | 0 | 1 | 18 | 10 | 8 | 15 |
| 3 | Viktoria Plzeň | 1 | 0 | 5 | 6 | 17 | -11 | 3 |
| 4 | CSKA Moscow | 1 | 0 | 5 | 8 | 17 | -9 | 3 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
Comme nous l'avons noté, à la première étape de notre algorithme le critère de tri est "points". La première tâche de sortAndDivideTable consiste à découper la table en fonction de celle-ci, et nous utilisons la méthode de tableau JavaScript standard .reduce() pour ce faire.
Dans ce cas, nous produisons deux sous-tableaux de deux équipes chacun, car il y a deux groupes d'équipes à égalité (Bayern Munich/Manchester City et Viktoria Plzeň/CSKA Moscou, respectivement à 15 et 3 points). Le classement d'origine est ensuite partiellement trié : certaines de ces équipes seront certainement au-dessus des autres (par exemple, Manchester City vit certainement au-dessus du Viktoria Plzeň), mais les équipes à égalité de points restent encore indécises.
Alors que cette première étape récursive touche à sa fin, nous décidons où aller ensuite : nous savons que l'UEFA Champions League emploie un style de face-à-face, et nous écrivons donc cela comme le type pour la prochaine itération ; et comme les groupes découpés sont de longueur supérieure à un (il y a deux équipes dans chacun d'eux), ce qui signifie qu'il nous reste encore du travail en termes de tri, nous renvoyons chacun d'eux dans sortAndDivideTable en tant que nouvelle table.
Suivons l'historique de la première série d'équipes à égalité. Nous avons entré une série de critères en face-à-face, donc tout d'abord nous calculons le sous-tableau de leurs matchs : nous voyons que le Bayern Munich a perdu à domicile (Bayern Munich 2-3 Manchester City) mais a ensuite gagné à l'extérieur. avec une plus grande marge (Manchester City 1-3 Bayern Munich), donnant ainsi naissance au sous-tableau
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Bayern Munich | 1 | 0 | 1 | 5 | 4 | 1 | 3 |
| 2 | Manchester City | 1 | 0 | 1 | 4 | 5 | -1 | 3 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
Maintenant, ils sont liés en points (tête-à-tête) : l'étape de regroupement laisse donc ce tableau inchangé, l'étape de tri n'a plus rien à voir, et on arrive à la fin de l'itération récursive sans grand chose de fait ; on passe donc au critère suivant (différence de buts), on garde le type face-à-face, et on le réinjecte dans la fonction.
Comme nous sommes au milieu d'un face-à-face, nous sautons l'étape de recalcul de la table (comme indiqué dans la deuxième section à retenir, c'est quelque chose que nous ne faisons que lors du processus face-à-face commence, ou quand il se termine après tous critères ont été appliqués sans atteindre une décision); mais cette fois, le critère est la différence de buts, donc l'étape de regroupement réussit à découper le tableau en deux sous-tableaux (de longueur un chacun) car une équipe a une différence de buts de 1, tandis que l'autre a une différence de buts de -1. . Cela permet à l'étape de tri de revoir le classement d'origine et de dire maintenant avec certitude que Le Bayern Munich se classe au-dessus de Manchester City.
Et comme les ensembles découpés résultant de l'étape de regroupement ont exactement une longueur (ce qui signifie qu'il n'y a plus de liens restants), nous quittons la récursion sur cette branche en n'appelant plus la fonction.
D'un autre côté, pour l'histoire du deuxième set, nous savons que le Viktoria Plzeň a également gagné à domicile (Viktoria Plzeň 2-1 CSKA Moscou) mais a ensuite perdu à l'extérieur avec la même marge (CSKA Moscou 3 -2 Viktoria Plzeň), cédant ainsi
| Position | Team | Won | Drawn | Lost | GF | GA | GD | Points |
|---|---|---|---|---|---|---|---|---|
| 1 | Viktoria Plzeň | 1 | 0 | 4 | 4 | 4 | 0 | 3 |
| 2 | CSKA Moscow | 1 | 0 | 1 | 4 | 4 | 0 | 3 |
GF = Buts pour (buts marqués), GA = Buts contre (buts encaissés), GD = Différence de buts.
où les deux équipes sont à égalité sur la différence de buts en face-à-face et les buts en face-à-face marqués, et elles nécessitent donc un critère supplémentaire (et donc une étape de récursion supplémentaire) pour être triées contrairement à leurs homologues. Dans le cas de l'UEFA Champions League, ce prochain critère serait le nombre de buts marqués à l'extérieur, ici 2 pour le Viktoria Plzeň et 1 pour le CSKA Moscou dans leur bilan en face-à-face.
Encore une fois, la récursivité se termine à cette étape et les classements d'origine sont désormais entièrement triés.
Cet exemple met en valeur certains des aspects positifs de l'approche récursive : les deux branches n'ont pas besoin de « parler » entre elles ; en fait, l'une d'entre elles a même besoin d'un bris d'égalité supplémentaire pour être triée, mais cela ne concerne pas le autre. Toute question concernant la profondeur de récursion que nous avons atteinte, comme par exemple si nous devons ou non procéder à une réapplication en tête-à-tête (comme expliqué dans la section du même nom ci-dessus), peut être réglée par chaque branche indépendamment.
De plus, comme l'intersection de deux branches est toujours vide (puisqu'elles sont créées lors de l'étape de regroupement via .reduce(), qui divise toujours un tableau en classes d'équivalence qui ne se croisent pas), chaque branche peut trier indépendamment la sienne. équipes au classement initial sans se marcher sur les pieds. Cela signifie qu'une branche d'équipes extrêmement ex aequo pourrait même remplir tous les critères des confrontations face-à-face, et ainsi revenir aux contrôles globaux dans l'espoir de briser l'égalité, sans que cela n'affecte les comparaisons des autres équipes, car aucune branche jamais influence les autres.
Remarquez aussi comment la récursivité doit se terminer : chaque fois que deux équipes sont triées selon le critère courant, .reduce() produira des sous-tableaux dont la longueur est strictement inférieure à celle du tableau actuel, afin que la prochaine étape de la récursion soit plus proche d'atteindre un tableau de longueur un (à ce stade, la fonction n'est plus appelée) ; et si l'égalité persiste jusqu'à la fin, le critère final est toujours soit un tirage au sort, soit un tri alphabétique, qui ne manquera pas de produire un résultat dans les deux cas (les identifiants des équipes doivent être uniques au moment de la saisie). 🎜>
Considérations finalesJ'écrirai peut-être davantage à ce sujet à l'avenir, en particulier en ce qui concerne la méthode .ties() qui fournit une description textuelle des équipes qui ont été triées, y compris comment et à quelle étape, pour laquelle l'utilisateur final peut vouloir imprimer par souci de clarté.
Mais en attendant, n'hésitez pas à consulter le dépôt sur GitHub si vous le souhaitez...
SuzuSuzu-HaruHaru
/
classement de la ligue
En tant que grand fan de football (soccer), je peux affirmer avec confiance qu'il n'y a rien de plus facile—etrien de plus difficile—que de mettre des équipes dans un tableau. C'est facile, dans la mesure où la logique est apparemment assez simple : suivre les résultats, calculer les points, trier par points ; s'il y a des égalités, appliquez des bris d'égalité. Petites nuances mises à part, ce serait la fin de l’histoire. Mais comme on dit, le diable est dans les détails.
La règle des buts à l'extérieur est une règle célèbre qui a fait l'actualité en 2021, lorsque l'UEFA l'a supprimée ; mais est-il vraiment disparu de la liste des départages ? ou encore, le groupe F de l'UEFA Europa League 2022-23 a vu toutes les équipes terminer leur groupe avec huit points chacune : comment ces égalités ont-elles été résolues ? et qui peut dire ce qui se passe à l'Euro si deux équipes sont à égalité de points, de différence de buts et de buts…
...et bien sûr, c'est pour moi aussi l'occasion d'apprendre. Si vous voyez des points de préoccupation ou des marges d'amélioration, ne soyez pas timide et dites-le-moi dans les commentaires !
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
