Da ich ein Hobbyentwickler bin, der immer noch die Tiefen von JavaScript erforscht und noch nie zuvor ein Paket geschrieben oder veröffentlicht hat, bin ich sicherlich nicht in der Lage, irgendjemandem etwas beizubringen. Was ich jedoch kann tun kann, ist, meine Erfahrungen beim Schreiben eines im Wesentlichen immer noch unvollkommenen Pakets zu teilen, das mir aber viel Spaß gemacht hat.

Alles begann mit einem Problem, von dem ich überrascht war, dass es nicht so oft online angegangen wurde und das, wie ich herausfand, auf etwas unerwartete Weise gelöst werden konnte: nämlich durch die Verwendung von Rekursion.

Das Problem mit Ranglisten

Diejenigen unter Ihnen, die Fußball (oder Sport im Allgemeinen oder jedes Wettbewerbsumfeld, in dem Ranglisten benötigt werden) mögen, sind sicherlich mit dem Konzept einer Ligatabelle vertraut: Eine bestimmte Anzahl von Teams tritt gegeneinander an in einer Reihe von Spielen, nach denen jedes Team eine bestimmte Anzahl von Punkten erhält, je nachdem, ob es gewonnen, unentschieden oder verloren hat; Eine Ligatabelle sammelt alle Mannschaften in absteigender Punktereihenfolge und macht so deutlich, welches Team als Sieger gekürt wird.

In Bezug auf die Programmierung ist dies eine Situation, die keinerlei Probleme darstellt: Es ist trivial zu überprüfen, welche Mannschaft ein Spiel gewonnen hat (beim Fußball ist es so einfach, zu sehen, welche der beiden Mannschaften mehr Tore geschossen hat) und die Gesamtzahl zu berechnen Die Anzahl der Punkte über alle Spiele hinweg läuft auf eine einfache Addition hinaus. Auch der Sortierschritt ist nicht kompliziert, da JavaScript sogar Standard-Sortiermethoden für Arrays mitbringt.

Man könnte sich vorstellen, dass die Dinge etwas weniger trivial werden, wenn zwei oder mehr Teams punktgleich abschließen. In diesem Fall ist ein Tiebreaker erforderlich. Wenden wir uns noch einmal dem Fußball zu: Zu den gängigen Tiebreakern gehören in der Regel die Tordifferenz (die Anzahl der erzielten Tore minus der Anzahl der kassierten Tore), die Anzahl der erzielten Tore selbst, die Anzahl der Siege usw. Und das würde einmal mehr darauf hindeuten, dass das Problem gar nicht so schwer zu lösen ist: Im Falle eines Punktegleichstands reicht es aus, die betreffenden Teams nach einem anderen Kriterium zu sortieren. Sogar dem Benutzer die Möglichkeit zu geben, welche Tiebreaker oder in welcher Reihenfolge anzuwenden sind, ist die Implementierung nicht schwer, solange der Pool an Auswahlmöglichkeiten endlich und fest codiert ist.

Und in diesem Ausmaß lösen die meisten Online-Lösungen das Problem. Allerdings ist die Sache etwas subtiler und geht tiefer, als man zunächst vermuten würde.

Kopf-an-Kopf vs. Gesamtstil

Die Wahrheit ist, dass jede Art von Kriterium (Tordifferenz, erzielte Tore usw. – aber sogar die Anzahl der Punkte selbst) auf zwei verschiedene Arten überprüft werden kann: im globalen Sinne (die sogenannte Gesamtkontrolle), bei der es sich um die Standardart der Kontrolle handelt, bei der man sich die vollständige Tabelle ansieht, wie sie aus allen gespielten Spielen hervorgeht von allen Teams und vergleicht die Teams auf dieser Grundlage; oder in einem eingeschränkten Sinne (der sogenannte Kopf-an-Kopf-Check), bei dem, wenn zwei oder mehr Teams punktgleich sind, jeder nachfolgende Tiebreaker nur innerhalb der Spiele zwischen den beiden Teams überprüft wird Teams in Frage.

Ein Beispiel soll diesen Unterschied verdeutlichen. Nehmen wir die Gruppe E bei der UEFA Euro 2016, wo die Abschlusstabelle am Ende so aussah

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

Italien und Belgien sind punktgleich, und der erste Entscheidungspunkt bei der EM ist die Tordifferenz (wobei Italien und Belgien mit jeweils 2 immer noch unentschieden sind), gefolgt von der Anzahl der erzielten Tore – zu diesem Zeitpunkt würde man Belgien erwarten um über Italien zu triumphieren, mit 4 erzielten Toren gegen 3.

Allerdings die EM ist ein Wettbewerb, bei dem ein Kopf-an-Kopf-Rennen eingesetzt wird, um Teams zu ermitteln, die punktgleich sind. Das heißt, sobald wir erkennen, dass Italien und Belgien dies tun müssen Wenn ihr Unentschieden gebrochen ist, berechnen wir sofort eine neue Untertabelle, die nur aus den am Unentschieden beteiligten Teams besteht. Und da sie am ersten Spieltag ein einziges Spiel bestritten haben, das 0:2 für Italien endete, sieht diese Untertabelle so aus (der Fußball vergibt drei Punkte für einen Sieg, einen für ein Unentschieden und keinen für eine Niederlage)

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

was bedeutet, dass Italien aufgrund der direkten Punkteverteilung (drei zu null) sofort vor Belgien liegt.

Verschiedene Wettbewerbe verwenden in der Regel unterschiedliche Stile (die EM verwendet den Kopf-an-Kopf-Stil, wie wir gerade gesehen haben, während beispielsweise die FIFA-Weltmeisterschaft dafür bekannt ist, stattdessen Gesamtkontrollen zu verwenden), obwohl beide zum anderen wechseln Stil, falls die erste Reihe von Kriterien nicht schlüssig ist, um ein bestimmtes Unentschieden zu lösen.

Das bedeutet, dass es möglicherweise früher oder später zu direkten Duellen kommen wird (entweder sofort in einem Wettbewerb wie der EM oder als potenzieller zweiter Tiebreak-Lauf bei der FIFA-Weltmeisterschaft). Meine Erkenntnis hier war also, dass die Tabelle, die wir betrachten, sich möglicherweise während des Sortiervorgangs ändern kann, da der Kopf-an-Kopf-Stil (ob er sofort kommt oder nicht) davon abhängt Tatsache.

Aber das war nicht meine einzige Erkenntnis, wie das folgende Beispiel zeigt.

Weitere Feinheiten: direkte erneute Anwendung

Belgien ist erneut der Protagonist der berühmten Gruppe E bei der UEFA Euro 2024, wo jedes einzelne Team seine Gruppe mit 4 Punkten abschloss

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

Da alle Teams punktgleich sind, ist die Untertabelle der direkten Ergebnisse ohnehin immer noch die vollständige Tabelle. Die Slowakei und die Ukraine sind nach der Tordifferenz zu den Schlusslichtern der Tabelle sortiert, und Rumänien wird aufgrund seiner überlegenen Anzahl an erzielten Toren vor Belgien platziert (Rumänien 4, Belgien 2). Tatsächlich sah der Finaltisch am Ende so aus.

Aber man könnte es seltsam finden: Es gab genau ein Spiel zwischen Belgien und Rumänien, das Belgien am zweiten Spieltag mit 2:0 gewann. Warum rangierte Belgien nicht vor Rumänien? Spielt das keine Rolle? Warum wurde für sie keine Untertabelle neu berechnet, nachdem die Slowakei und die Ukraine vom Rest getrennt wurden, wie wir es zuvor getan haben?

Die Wahrheit ist, dass gemäß den UEFA-Euro-Bestimmungen (§20.01-d.) eine Neuberechnung der direkten Ergebnisse nicht bei jedem Schritt erfolgt, aber erst, wenn die vollständige Liste der Tiebreaker abgelaufen ist. Da nach dem Punktegleichstand und der Tordifferenz noch die Anzahl der erzielten Tore überprüft werden muss, schauen wir uns das an und das ist Warum Rumänien am Ende triumphiert. Wäre das ebenfalls unentschieden gewesen, erst zu diesem Zeitpunkt würden wir tatsächlich anfangen, über eine Untertabelle nachzudenken, die auf dem einzigen Spiel zwischen den immer noch unentschiedenen Mannschaften (Belgien und Rumänien) basiert. wo Belgien aufgrund seines Sieges tatsächlich als Sieger hervorgehen würde.

Hier ist also die zweite Erkenntnis: Der Sortierprozess beinhaltet ein Konzept der Tiefeabhängig davon, wie weit Sie darin sind müssen unterschiedliche Entscheidungen treffen – etwa, ob mit einer Neuberechnung der Untertabelle fortgefahren werden soll oder nicht. In diesem Fall würden Sie noch nicht damit fortfahren, da die Liste der Kriterien noch nicht abgeschlossen ist.

Das sind die Hauptpunkte, die zu meiner Entscheidung für die Form meiner Sortierfunktion geführt haben.

Ein rekursiver Ansatz

Der Sortieralgorithmus, auf den über die .standings()-Methode der von meinem Paket implementierten Klasse zugegriffen wird, basiert auf einer rekursiven Funktion

const sortAndDivideTable = (table, iteration, criteria) => {
    // ...
}

Während sich in jeder Schritttabelle die Tabelle befindet, die die Daten der Teams enthält, die aktuell sortiert werden sollen, verfolgt die Iteration die Iterationsnummer und andere zugehörige Informationen (z. B. ob es sich um einen Kopf-an-Kopf- oder einen Gesamttyp handelt). der Prüfung) und Kriterien ist ein Array, das die geordnete Liste der anzuwendenden Kriterien darstellt (z. B. Punkte, Tordifferenz, Anzahl der erzielten Tore).

Die Rekursion beginnt mit einer Tabelle, die aus allen Spielen aller Teams berechnet wird und möglicherweise noch ungeordnet ist. Beachten Sie, dass die erste Iteration des Algorithmus immer vom Typ „Gesamt“ ist (und daher als solcher initialisiert wird, wenn die Rekursion beginnt), da per Definition die erste Prüfung immer die Anzahl der über alle erhaltenen Punkte ist stimmt überein;wiederum ist per Definition das erste Element im Kriterienarray immer „Punkte“.

Diese Starttabelle ist ebenfalls sicher verstaut: Bei jedem Schritt werden ihre Einträge nicht geändert, aber ihre Zeilen werden nach und nach sortiert. Zu Referenzzwecken können wir es von nun an als „ursprünglicher Stand“ bezeichnen.

Ein reales Beispiel aus der UEFA Champions League

Vor diesem Hintergrund ist es möglich, den Algorithmus anhand eines Beispiels zu verstehen, das von der Gruppe D bei der UEFA Champions League 2013–14 bereitgestellt wurde und am Ende so aussah

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

Wie wir festgestellt haben, lautet das Sortierkriterium im ersten Schritt unseres Algorithmus „Punkte“. Die erste Aufgabe von sortAndDivideTable besteht darin, die Tabelle entsprechend aufzuteilen, und wir verwenden dazu die Standard-JavaScript-Array-Methode .reduce().

In diesem Fall erstellen wir zwei Untertabellen mit jeweils zwei Mannschaften, da es zwei Gruppen mit punktgleichen Mannschaften gibt (Bayern München/Manchester City und Viktoria Plzeň/ZSKA Moskau, mit 15 bzw. 3 Punkten). Die ursprüngliche Rangliste wird dann teilweise sortiert: Einige dieser Teams werden definitiv über anderen liegen (z. B. Manchester City liegt sicherlich über Viktoria Plzeň), aber die Teams, die punktgleich sind, bleiben noch unentschieden.

Da sich dieser erste rekursive Schritt seinem Ende nähert, entscheiden wir, wohin wir als nächstes gehen: Wir wissen, dass die UEFA Champions League einen Kopf-an-Kopf-Stil verwendet, und schreiben diesen daher als Typ für die nächste Iteration; und da die zerstückelten Gruppen eine Länge von mehr als eins haben (es gibt zwei Teams in jeder von ihnen), bedeutet das, dass wir noch einiges an Sortierarbeit vor uns haben, Wir speisen jeden von ihnen als neue Tabelle in sortAndDivideTable zurück.

Lassen Sie uns die Geschichte der ersten Gruppe unentschiedener Teams verfolgen. Wir haben einen Vergleich der Kriterien gestartet, also berechnen wir zunächst die Untertabelle ihrer Spiele: Wir sehen, dass Bayern München zu Hause verloren hat (Bayern München 2:3 Manchester City), aber dann auswärts gewonnen hat mit größerem Vorsprung (Manchester City – Bayern München 1:3), wodurch die Untertabelle entsteht

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

Jetzt sind sie in (Kopf-an-Kopf-)Punkten gleichauf: Der Gruppierungsschritt lässt diese Tabelle daher unverändert, der Sortierschritt hat nichts zu tun und wir erreichen das Ende der rekursiven Iteration, ohne viel erreicht zu haben; Deshalb gehen wir zum nächsten Kriterium (Tordifferenz) über, behalten den Head-to-Head-Typ bei und geben die Tabelle wieder in die Funktion ein.

Da wir uns mitten in einem Kopf-an-Kopf-Rennen befinden, überspringen wir den Schritt der Neuberechnung der Tabelle (wie im zweiten Abschnitt zum Mitnehmen erwähnt, tun wir das nur, wenn der Kopf-an-Kopf-Prozess läuft ). beginnt, oder wenn es ende, nachdem alle Kriterien angewendet wurden, ohne sie zu erreichen eine Entscheidung); Aber dieses Mal ist das Kriterium die Tordifferenz, daher gelingt es dem Gruppierungsschritt, die Tabelle in zwei Untertabellen (jeweils mit der Länge eins) aufzuteilen, da eine Mannschaft eine Tordifferenz von 1 hat, während die andere eine Tordifferenz von -1 hat . Dies ermöglicht es dem Sortierschritt, sich noch einmal die ursprüngliche Rangliste anzusehen und nun definitiv zu sagen, dass Bayern München über Manchester City rangiert.

Und da die resultierenden zerstückelten Mengen aus dem Gruppierungsschritt genau die Länge eins haben (was bedeutet, dass es keine verbleibenden Bindungen mehr gibt), beenden wir die Rekursion auf diesem Zweig, indem wir die Funktion nicht mehr aufrufen.

Auf der anderen Seite haben wir für die Geschichte des zweiten Satzes festgestellt, dass Viktoria Plzeň ebenfalls zu Hause gewann (Viktoria Plzeň 2:1 ZSKA Moskau), dann aber auswärts mit dem gleichen Vorsprung verlor (ZSKA Moskau 3). -2 Viktoria Plzeň), also nachgeben

GF = Tore für (erzielte Tore), GA = Tore gegen (zugegebene Tore), GD = Tordifferenz.

wobei beide Teams hinsichtlich der direkten Tordifferenz und der erzielten direkten Tore gleichauf sind und daher im Gegensatz zu ihren Gegenspielern ein zusätzliches Kriterium (und damit einen zusätzlichen Rekursionsschritt) zur Sortierung erforderlich ist. Im Falle der UEFA Champions League wäre dieses nächste Kriterium die Anzahl der auswärts erzielten Tore – hier 2 für Viktoria Plzeň und 1 für ZSKA Moskau in ihrer direkten Bilanz.

Wieder einmal endet die Rekursion an diesem Schritt und die ursprüngliche Rangliste ist nun vollständig sortiert.

Was ist daran gut?

Dieses Beispiel zeigt einige der positiven Aspekte des rekursiven Ansatzes: Die beiden Zweige müssen nicht miteinander „sprechen“ – tatsächlich benötigt einer von ihnen sogar einen zusätzlichen Tiebreaker zum Sortieren, aber das ist für den nicht von Belang andere. Alle Fragen bezüglich der Rekursionstiefe, die wir erreicht haben, z. B. ob wir uns für eine direkte erneute Anwendung entscheiden müssen (wie im gleichnamigen Abschnitt oben erläutert), können von jedem Zweig unabhängig geklärt werden.

Da außerdem die Schnittmenge von zwei beliebigen Zweigen immer leer ist (da sie im Gruppierungsschritt über .reduce() erstellt werden, wodurch ein Array immer in sich nicht überschneidende Äquivalenzklassen aufgeteilt wird), kann jeder Zweig seine eigene unabhängig sortieren Teams in der ursprünglichen Rangliste, ohne sich gegenseitig auf die Füße zu treten. Dies bedeutet, dass ein Zweig mit extrem unentschiedenen Teams sogar die gesamten Kriterien für ein direktes Duell erfüllen könnte und somit zu den Gesamtprüfungen zurückkehren könnte, in der Hoffnung, das Unentschieden zu brechen, ohne dass dies Auswirkungen auf die Vergleiche anderer Teams hat – da es keinen Zweig gibt beeinflusst jemals andere.

Beachten Sie auch, wie die Rekursion enden muss: Immer wenn zwei Teams nach dem aktuellen Kriterium sortiert werden, erzeugt .reduce() Unterarrays, deren Länge strikt kleiner ist als die der aktuellen Tabelle. so dass der nächste Schritt in der Rekursion näher am Erreichen eines Arrays der Länge eins liegt (an diesem Punkt wird die Funktion nicht mehr aufgerufen); und wenn das Unentschieden bis zum Ende bestehen bleibt, ist das Endkriterium immer entweder eine Auslosung nach dem Zufallsprinzip oder eine alphabetische Sortierung, die in beiden Fällen zwangsläufig zu einem Ergebnis führt (die Teamkennungen müssen zum Zeitpunkt der Eingabe eindeutig sein).

Abschließende Überlegungen

Über Tiebreaking-Stile gibt es noch viel mehr zu sagen, ebenso über die Funktionalitäten dieses Pakets und alle Anpassungsoptionen, auf die der Benutzer beim Definieren der Turnierregeln Zugriff hat.

Möglicherweise schreibe ich in Zukunft mehr darüber, insbesondere was die Methode .ties() betrifft, die eine Textbeschreibung darüber bereitstellt, welche Teams sortiert wurden, einschließlich wie und in welchem ​​Schritt, für die der Endbenutzer möglicherweise drucken möchte Der Klarheit halber.

Aber in der Zwischenzeit können Sie gerne das Repository auf GitHub überprüfen, wenn Sie möchten...

...und natürlich ist dies auch für mich eine Gelegenheit zu lernen. Wenn Sie Bedenken oder Verbesserungspotenzial sehen, zögern Sie nicht und sagen Sie es mir in den Kommentaren!

Das obige ist der detaillierte Inhalt vonMein erstes JavaScript-Paket (mit Rekursion für den Sieg). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!