私は趣味の開発者であり、今も JavaScript の深さを探求しており、これまでパッケージを書いたり公開したりしたことはありません。そのため、誰かに何かを教える立場にはありません。しかし、私にできることは、本質的にはまだ不完全なパッケージですが、思いつくのがとても楽しかったものを書いた経験を共有することです。

すべては、オンラインであまり取り組まれていなかったことに驚いた問題から始まりました。そして、少し予想外の方法、つまり再帰を使用することできれいに解決できることがわかったのです。

リーグテーブルの問題

サッカー (またはスポーツ全般、またはランキングが必要な競争環境) が好きな人は、リーグ テーブル: の概念に精通しているでしょう。一定数のチームが互いに競い合います。一連の試合の後、各チームは勝ち、引き分け、または負けに応じて一定のポイントを獲得します。 リーグ表では、すべてのチームがポイントの降順に収集され、どのチームが勝者として栄冠するかが明確になります。

プログラミングの観点から見ると、これは何の問題も引き起こさない状況です。どちらのチームが試合に勝ったかを確認することは簡単であり (サッカーでは、2 つのチームのどちらがより多くのゴ​​ールを獲得したかを確認するのと同じくらい簡単です)、合計数を計算することもできます。すべての試合のポイントは単純な加算に帰着します。 JavaScript には配列のデフォルトの並べ替えメソッドも用意されているため、並べ替えの手順も複雑ではありません。

2 つ以上のチームが勝ち点で同点になった場合、事態は少し難しくなることが想像されるでしょう。その場合、タイブレーカーが必要になります。もう一度サッカーに目を向けると、一般的なタイブレーカーには通常、得失点差 (得点数から失点数を引いたもの)、得点数自体、勝利数などが含まれます。そして、これは、この問題を解決するのがそれほど難しいことではないことをもう一度示唆します。勝ち点が同点の場合は、問題のチームを別の基準で並べ替えるだけで済みます。 どのタイブレーカーを適用するか、またはどの順序で適用するかをユーザーが選択できるようにすることも、選択肢のプールが有限でハードコーディングされている限り、実装は難しくありません。

これは、ほとんどのオンライン ソリューションが問題に対処する程度です。しかし、問題は少し微妙で、当初の予想よりも奥が深いです。

直接対決と全体のスタイル

真実は、あらゆる種類の基準 (得失点差、得点など、ただし勝ち点自体も) は 2 つの 異なる方法でチェックできます。いわゆる 全体 チェック)。これは、すべての一致から表示される 完全 テーブルを調べる標準タイプのチェックです。すべてのチームがプレーしたデータと、それに基づいてチームを比較する。または、制限された意味 (いわゆる直接対決 チェック) では、2 つ以上のチームが勝ち点で並んだ場合、その後のタイブレーカーはチーム間で行われる試合内でのみチェックされます。問題のチーム。

例を見ると、この違いが明確になります。 UEFA EURO 2016 のグループ E を例に挙げます。最終順位はこのようになりました

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

イタリアとベルギーは勝ち点で並んでおり、ユーロでの最初のタイブレークは得失点差(イタリアとベルギーはまだ2点で並んでいる)、次に得点数が続く。この時点でベルギーが予想されるだろう3 ゴールに対して 4 ゴールを挙げてイタリアに勝利しました。

しかし、ユーロは、勝ち点が互角のチームを分類するために直接対決のスタイルが使用される大会です。 これは、イタリアとベルギーが次のことを行う必要があることを認識し次第、直ちに決定することを意味します。同点が崩れた場合、同点に関係するチームのみから作成された新しいサブテーブルをすぐに計算します。そして、最初の試合でイタリアが 0-2 で終わった単一の試合を行ったので、このサブテーブルは次のようになります (サッカーは勝利に 3 ポイント、引き分けに 1 ポイント、負けには 0 ポイントを割り当てます)

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

つまり、直接の勝ち点 (3 対 0) により、イタリアがベルギーの上に並べられることを意味します。

通常、異なる競技会では異なるスタイルが採用されますが (ユーロでは先ほど見たように直接対決のスタイルが使用されますが、たとえば FIFA ワールドカップは代わりに全体的なチェックを採用することで有名です)、両方とも他のスタイルに切り替わります。スタイルは、条件の最初の実行で特定の同点を破る決定的なものでなければなりません。

これは、潜在的には遅かれ早かれ直接対決が必ず起こることを意味します（ユーロのような大会で即座に、または FIFA ワールドカップでの 2 回目のタイブレークの可能性として）。ここでの私の結論は、私たちが見ているテーブルはソートプロセス中に変更される可能性があるということです。これは直接対決のスタイル (すぐに来るかどうか) に依存するためです。事実。

しかし、次の例が示すように、これが私の唯一の教訓ではありませんでした。

より複雑: 直接の再適用

UEFA EURO 2024 ではベルギーが再び有名なグループ E の主役となり、全チームが勝ち点 4 でグループを終えました

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

すべてのチームが勝ち点で並んでいるため、対戦結果のサブテーブルはいずれにせよフルテーブルのままです。スロバキアとウクライナは得失点差で最下位に並び、ルーマニアは得点数で上回っているためベルギーの上に位置する（ルーマニア4、ベルギー2）。実際、最終的なテーブルはこのようになりました。

しかし、これは奇妙に思われるかもしれません。ベルギーとルーマニアの間でちょうど 1 試合が行われ、第 2 節でベルギーが 2-0 で勝利しました。では、なぜベルギーはルーマニアより上位にランクされなかったのでしょうか?これは関係ありませんか？以前のように、スロバキアとウクライナが残りから分離された後、サブテーブルが再計算されなかったのはなぜですか?

実際のところ、UEFA ユーロ規則 (§20.01-d.) によれば、直接対決の結果の再計算はすべての段階で行われるわけではありません。ただし、タイブレーカーの完全なリストが使い果たされたのは 1 回のみです。 勝ち点と得失点差が同点になった後も、得点数を確認する必要があるため、それを確認します。これがルーマニアが最終的に勝利する理由です。 そのも同点だった場合、その時点でのみ、まだ同点のチーム (ベルギーとルーマニア) の間で行われた単一の試合に基づいてサブテーブルを実際に検討し始めることになります。ここでベルギーは勝利により実際に首位に立つことになります。

ここで 2 番目のポイントを紹介します。並べ替えプロセスには深さの概念があり、 は どの程度に取り組んでいるかによって異なります。サブテーブルの再計算を続行するかどうかなど、さまざまな決定を下す必要があります。この場合、基準のリストはまだ進行中であるため、まだ先に進むことはできません。

これらは、並べ替え機能の形式を決定するに至った主なポイントです。

再帰的アプローチ

パッケージが実装するクラスの .stands() メソッドを介してアクセスする並べ替えアルゴリズムは、再帰関数に依存します

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

任意のステップ テーブルが現在ソートされるチームのデータを保持するテーブルである場合、反復は反復番号とその他の関連情報を追跡します (たとえば、これが直接対決または全体的なタイプであるかどうか)チェックの)、criteria は適用される基準 (得点、得失点差、得点数など) の順序付きリストを表す配列です。

再帰は、すべてのチームによってプレイされたすべての試合から計算され、まだ順序付けされていない可能性があるテーブルから始まります。 定義上、最初のチェックは常に全体にわたって取得されたポイントの数であるため、アルゴリズムの最初の反復は常に全体的な型である(したがって、再帰の開始時にそのように初期化される)ことに注意してください。 matches; も定義上、条件配列の最初の要素は常に "points" です。

この開始テーブルも安全に保管されます。どのステップでも、そのエントリは変更されませんが、その行は少しずつソートされます。参考までに、今後はこれを「オリジナル順位」と呼ぶことにします。

UEFA チャンピオンズ リーグの実例

これを念頭に置いて、2013-14 年の UEFA チャンピオンズ リーグのグループ D によって提供された例を使用してアルゴリズムを理解することができます。最終的には次のようになります。

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

前述したように、アルゴリズムの最初のステップでの並べ替え基準は「ポイント」です。 sortAndDivideTable の最初の仕事は、それに応じてテーブルを分割することであり、これを行うために標準の .reduce() JavaScript 配列メソッドを使用します。

この場合、同点チームの 2 つのグループ (バイエルン ミュンヘン/マンチェスター シティとヴィクトリア プルゼン/CSKA モスクワ、それぞれ勝ち点 15 と 3) があるため、それぞれ 2 チームの 2 つのサブテーブルを作成します。その後、元の順位が部分的に並べ替えられます。これらのチームのいくつかは間違いなく他のチームよりも上位になります (例: マンチェスター シティは確実にヴィクトリア プルゼンより上にいます)。ただし、勝ち点で並んでいるチームはまだ未定のままです。

この最初の再帰ステップが終わりに近づくと、次にどこに行くかを決定します。UEFA チャンピオンズ リーグが直接対決のスタイルを採用していることはわかっているので、それを次の反復のタイプとして書きます。そして、細分化されたグループの長さは 1 より大きいため (それぞれのグループに 2 つの チームがあります)、つまり並べ替えに関してはまだやるべき作業が残っていることを意味します。それぞれを新しいテーブルとして sortAndDivideTable にフィードバックします。

第 1 セットの引き分けチームの歴史をたどってみましょう。基準の直接対決に入ったので、まず最初に、試合のサブテーブルを計算します。バイエルン・ミュンヘンがホームで負けましたが（バイエルン・ミュンヘン 2-3 マンチェスター・シティ）、その後アウェーで勝利したことがわかります。大差で (マンチェスター・シティ 1-3 バイエルン・ミュンヘン)、サブテーブルが誕生しました

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

今、それらは (直接の) 点で結び付けられています。したがって、グループ化ステップではこのテーブルは変更されず、並べ替えステップでは何もすることがなく、あまり達成されることなく再帰的反復の終わりに到達します。したがって、次の基準 (ゴール差) に進み、対戦タイプを維持し、それをテーブルに関数にフィードバックします。

私たちは直接対決の実行の途中であるため、テーブルの再計算ステップをスキップします (2 番目の要点セクションで説明したように、これは直接対決のプロセスの場合にのみ実行されることです 開始時、またはすべての条件が適用されずに終了したとき決定に達する）;しかし、今回の基準は得失点差なので、一方のチームの得失点差が 1 で、もう一方のチームの得失点差が -1 であるため、グループ化ステップはテーブルを 2 つのサブテーブル (それぞれ長さが 1 つ) に分割することに成功します。 。これにより、並べ替えステップで元の順位をもう一度確認して、バイエルン ミュンヘンがマンチェスター シティよりも上位にあると明確に言えるようになります。

グループ化ステップから得られる細分化されたセットの長さはちょうど 1 であるため (結合が残っていないことを意味します)、関数をもう呼び出さないことで、この分岐での再帰を終了します。

一方、第 2 セットの歴史を見ると、ヴィクトリア プルゼニも同様にホームで勝利しました (ヴィクトリア プルゼニ 2-1 CSKA モスクワ) が、アウェイでは同じ差で負けました (CSKA モスクワ 3) -2 ヴィクトリア プルゼン)、こうして得られる

GF = Goals For (得点したゴール)、GA = Goals Against (失点)、GD = 得失点差。

この場合、両チームは対戦ゴール差と対戦ゴール数で並んでおり、そのため、相手チームとは異なり、追加の基準 (したがって、追加の再帰ステップ) をソートする必要があります。 UEFA チャンピオンズ リーグの場合、次の基準はアウェイでのゴール数になります。ここでは、対戦成績でヴィクトリア プルゼニが 2 ゴール、CSKA モスクワが 1 ゴールです。

もう一度言いますが、再帰はこのステップで終了し、元の順位が完全にソートされます。

何が良いのか

この例は、再帰的アプローチのポジティブな側面のいくつかを示しています。2 つのブランチは互いに「対話」する必要はありません。実際、そのうちの 1 つはソートするために追加のタイブレーカーさえ必要ですが、これはブランチにとっては関係ありません。他の。 (上記の同じ名前のセクションで説明したように) 直接の再適用を行う必要があるかどうかなど、到達した再帰の深さに関する問題は、各ブランチで個別に分類できます。

さらに、2 つのブランチの交差部分は常に空であるため (これらのブランチは .reduce() によるグループ化ステップで作成され、常に交差しない同値クラスに配列を分割します)、各ブランチは独自のブランチを独立してソートできます。チームはお互いの足を踏むことなく、元の順位で戦うことができます。これは、非常に同点のチームの支部が直接対決の基準をすべて使い果たし、他のチームとの比較に影響を与えることなく、同点を破ることを望んで全体的なチェックに戻る可能性さえあることを意味します。他のものに影響を与えることはありません。

再帰がどのように終了するかにも注目してください。現在の基準に従って 2 つのチームがソートされるたびに、.reduce() は現在のテーブルの長さよりも厳密に小さい部分配列を生成します。そのため、再帰の次のステップは長さ 1 の配列に近づきます (この時点で関数は呼び出されなくなります)。そして、最後まで同点が続いた場合、最終基準は常にランダムな抽選かアルファベット順のソートのいずれかになります。どちらの方法でも結果が生成されるはずです (チーム ID は入力時に一意である必要があります)。

最終的な考慮事項

タイブレーク スタイル、このパッケージの機能、およびトーナメントのルールを定義する際にユーザーがアクセスできるすべてのカスタマイズ オプションに関して、語るべきことはまだたくさんあります。

これについては、特に .ti​​es() メソッドに関して詳しく書くかもしれません。このメソッドは、どのチームがどのように、どの段階でソートされたのか、最終ユーザーが印刷したいと考えているテキストの説明を提供します。明確にするためです。

しかし、それまでの間、必要に応じて GitHub のリポジトリをチェックしてください...

...そして当然のことながら、これは私にとっても学ぶ機会です。気になる点や改善の余地があれば、遠慮せずにコメント欄で教えてください!

以上が私の最初の JavaScript パッケージ (成功のための再帰を使用)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。