Memandangkan saya seorang pembangun hobi yang masih meneroka kedalaman JavaScript, dan yang tidak pernah menulis atau menerbitkan pakej sebelum ini, saya pastinya tidak mempunyai kedudukan untuk mengajar apa-apa kepada sesiapa pun. Walau bagaimanapun, apa yang saya boleh lakukan ialah berkongsi pengalaman saya dalam menulis perkara yang pada asasnya masih merupakan pakej yang tidak sempurna, tetapi saya berasa sangat seronok untuk menghasilkannya.

Semuanya bermula dengan masalah yang saya terkejut melihat tidak banyak ditangani dalam talian, dan saya dapati boleh diselesaikan dengan kemas dengan cara yang tidak dijangka: iaitu, menggunakan rekursi.

Masalah dengan jadual liga

Anda yang suka bola sepak (atau sukan secara amnya, atau mana-mana persekitaran kompetitif yang memerlukan ranking) sudah tentu biasa dengan konsep jadual liga: beberapa pasukan bersaing antara satu sama lain dalam urutan perlawanan, selepas itu setiap pasukan memperoleh sejumlah mata tertentu bergantung pada sama ada mereka menang, seri atau kalah; jadual liga mengumpul semua pasukan dalam susunan mata yang menurun, sekali gus menjelaskan pasukan mana yang dinobatkan sebagai pemenang.

Dari segi pengaturcaraan, ini adalah situasi yang tidak menimbulkan sebarang isu: menyemak pasukan mana yang memenangi perlawanan adalah remeh (dalam bola sepak, ia semudah melihat mana antara dua pasukan yang menjaringkan lebih banyak gol), dan mengira jumlah mata merentas semua perlawanan bermuara kepada penambahan mudah. Langkah pengisihan juga tidak rumit, kerana JavaScript juga disertakan dengan kaedah pengisihan lalai untuk tatasusunan.

Orang akan membayangkan bahawa perkara menjadi kurang remeh apabila dua atau lebih pasukan menamatkan tahap dengan mata, dalam hal ini pemecah seri diperlukan. Beralih kepada bola sepak sekali lagi, pemecah seri biasa biasanya termasuk perbezaan gol (jumlah gol yang dijaringkan tolak jumlah gol yang dibolosi), jumlah gol yang dijaringkan sendiri, jumlah kemenangan dan sebagainya. Dan ini akan, sekali lagi, mencadangkan bahawa masalahnya tidak begitu sukar untuk diselesaikan: sekiranya berlaku seri dalam mata, hanya beralih kepada menyusun pasukan yang dipersoalkan di bawah kriteria yang berbeza. Malah membenarkan pengguna memilih yang pemecah seri untuk digunakan, atau dalam susunan yang mana, tidak sukar untuk dilaksanakan selagi kumpulan pilihan adalah terhad dan berkod keras.

Dan ini adalah sejauh mana kebanyakan penyelesaian dalam talian menangani masalah tersebut. Walau bagaimanapun, perkara ini lebih halus sedikit dan lebih mendalam daripada yang dijangkakan pada mulanya.

Head-to-head v. gaya keseluruhan

Sebenarnya, apa-apa jenis kriteria (perbezaan gol, gol yang dijaringkan dan sebagainya—tetapi bilangan mata itu sendiri) boleh disemak dalam dua cara yang berbeza: dalam erti kata global ( dipanggil cek keseluruhan), iaitu jenis cek standard di mana seseorang melihat jadual penuh, sebagai ia muncul daripada semua perlawanan yang telah dimainkan oleh semua pasukan, dan membandingkan pasukan berdasarkan itu; atau dalam erti kata terhad (yang dipanggil head-to-head check), di mana jika dua atau lebih pasukan terikat dalam mata maka mana-mana pemecah seri berikutnya diperiksa hanya dalam perlawanan yang dimainkan antara pasukan berkenaan.

Contoh akan menjelaskan perbezaan ini. Ambil Kumpulan E di UEFA Euro 2016, di mana jadual akhir berakhir seperti ini

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

Itali dan Belgium terikat dengan mata, dan pemecah seri pertama di Euro ialah perbezaan gol (di mana Itali dan Belgium masih terikat, dengan 2 setiap satu), diikuti dengan jumlah gol yang dijaringkan—pada ketika itu seseorang akan menjangkakan Belgium untuk menang ke atas Itali, dengan 4 gol dijaringkan menentang 3.

Walau bagaimanapun, Euro ialah pertandingan di mana gaya head-to-head digunakan untuk menyusun pasukan yang mempunyai mata yang sekata. Ini bermakna, sebaik sahaja kami menyedari bahawa Itali dan Belgium perlu apabila seri mereka putus, kami segera mengira sub-jadual baharu yang dibuat hanya daripada pasukan yang berkenaan dalam perlawanan itu. Dan ketika mereka bermain satu perlawanan yang berakhir 0-2 untuk Itali pada hari perlawanan pertama, jadual kecil ini kelihatan seperti ini (bola sepak memberikan tiga mata untuk menang, satu untuk seri dan tiada untuk kalah)

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

bermaksud Itali diisih di atas Belgium serta-merta, berdasarkan mata bersemuka (tiga hingga sifar).

Pertandingan yang berbeza biasanya akan menggunakan gaya yang berbeza (Euro menggunakan gaya head-to-head seperti yang baru kita lihat, manakala contohnya Piala Dunia FIFA terkenal dengan menggunakan semakan keseluruhan sebaliknya), walaupun kedua-duanya akan bertukar kepada yang lain gaya sekiranya larian pertama kriteria tidak meyakinkan dalam memecahkan seri yang diberikan.

Ini bermakna, kemungkinan, semakan head-to-head pasti akan berlaku lambat laun (sama ada serta-merta dalam pertandingan seperti Euro, atau sebagai larian pecah seri kedua yang berpotensi di Piala Dunia FIFA). Jadi yang saya ambil perhatian di sini ialah jadual yang kita lihat mungkin berpotensi berubah semasa proses pengisihan, kerana gaya kepala ke kepala (sama ada ia datang serta-merta atau tidak) bergantung pada perkara ini fakta.

Tetapi ini bukan satu-satunya yang boleh saya ambil, seperti yang ditunjukkan oleh contoh berikut.

Lebih selok-belok: permohonan semula secara bersemuka

Belgium sekali lagi menjadi protagonis dalam Kumpulan E yang terkenal di UEFA Euro 2024, di mana setiap pasukan menamatkan kumpulan mereka dengan 4 mata

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

Memandangkan semua pasukan terikat dalam mata, jadual kecil keputusan head-to-head masih lagi jadual penuh. Slovakia dan Ukraine disusun berdasarkan perbezaan gol ke bahagian bawah jadual, dan kemudian Romania diletakkan di atas Belgium kerana jumlah gol mereka yang unggul (Romania 4, Belgium 2). Memang, inilah rupa jadual akhir.

Tetapi orang mungkin menganggap ini ganjil: terdapat satu perlawanan yang dimainkan antara Belgium dan Romania, yang dimenangi Belgium 2-0 pada hari perlawanan kedua. Jadi mengapa Belgium tidak berada di atas Romania? Adakah ini tidak penting? Mengapakah sub-jadual tidak dikira semula untuk mereka selepas Slovakia dan Ukraine dipisahkan daripada yang lain, seperti yang kita lakukan sebelum ini?

Kebenaran perkara ini ialah, mengikut peraturan UEFA Euro (§20.01-d.), pengiraan semula keputusan head-to-head tidak berlaku pada setiap langkah, tetapi hanya apabila senarai penuh pemecah seri telah habis. Memandangkan selepas seri mata dan perbezaan gol masih terdapat jumlah gol yang perlu disemak, kami lihat itu dan inilah sebabnya Romania akhirnya menang. Sekiranya itu terikat juga, hanya pada ketika itu kami akan mula mempertimbangkan sub-jadual berdasarkan perlawanan tunggal yang dimainkan antara pasukan yang masih terikat (Belgium dan Romania), di mana Belgium sebenarnya akan muncul di atas kerana kemenangan mereka.

Jadi, berikut ialah pengambilan kedua: terdapat konsep kedalaman yang terlibat dalam proses penyisihan, kerana bergantung pada sejauh mana anda terlibat dengannya perlu mengambil keputusan yang berbeza-seperti sama ada untuk meneruskan pengiraan semula sub-jadual atau tidak. Dalam kes ini, anda tidak akan meneruskannya kerana senarai kriteria masih diteruskan.

Ini adalah perkara utama yang membawa kepada keputusan saya untuk bentuk fungsi pengisihan saya.

Pendekatan rekursif

Algoritma pengisihan, mengakses melalui kaedah .standings() kelas yang pakej saya laksanakan, bergantung pada fungsi rekursif

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

di mana pada mana-mana jadual langkah tertentu terdapat jadual yang menyimpan data pasukan yang sedang diisih, lelaran menjejaki nombor lelaran dan maklumat lain yang berkaitan (cth. jika ini adalah jenis head-to-head atau keseluruhan semakan), dan kriteria ialah tatasusunan yang mewakili senarai tersusun kriteria untuk digunakan (cth. mata, perbezaan gol, bilangan gol yang dijaringkan).

Rekursi bermula dengan jadual yang dikira daripada semua perlawanan yang dimainkan oleh semua pasukan, dan yang masih berpotensi tidak teratur. Perhatikan bahawa lelaran pertama algoritma sentiasa jenis keseluruhan (dan oleh itu dimulakan sedemikian apabila rekursi bermula), kerana mengikut takrifan semakan pertama sentiasa bilangan mata yang diperoleh merentas semua sepadan; sekali lagi mengikut definisi, elemen pertama dalam tatasusunan kriteria sentiasa "mata".

Jadual permulaan ini juga disimpan dengan selamat: pada mana-mana langkah entrinya tidak diubah suai, tetapi barisnya akan diisih sedikit demi sedikit. Untuk tujuan rujukan, kita boleh memanggilnya ‘kedudukan asal’ mulai sekarang.

Contoh dunia sebenar daripada Liga Juara-Juara UEFA

Memandangkan perkara ini, adalah mungkin untuk memahami algoritma dengan contoh yang disediakan oleh Kumpulan D pada Liga Juara-Juara UEFA 2013-14, yang akhirnya kelihatan seperti ini

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

Seperti yang kami nyatakan, pada langkah pertama algoritma kami, kriteria pengisihan ialah "mata". Tugas pertama sortAndDivideTable ialah memotong jadual mengikutnya dan kami menggunakan kaedah tatasusunan JavaScript .reduce() standard untuk melakukannya.

Dalam kes ini, kami menghasilkan dua jadual kecil dua pasukan setiap satu, kerana terdapat dua kumpulan pasukan seri (Bayern Munich/Manchester City dan Viktoria Plzeň/CSKA Moscow, masing-masing pada 15 dan 3 mata). Kedudukan asal kemudian sebahagian disusun: sesetengah pasukan ini pasti akan berada di atas yang lain (cth. Manchester City pastinya tinggal di atas Viktoria Plzeň), tetapi pasukan yang mempunyai mata yang sama masih belum membuat keputusan.

Memandangkan langkah rekursif pertama ini menghampiri penghujungnya, kami memutuskan ke mana hendak pergi seterusnya: kami tahu Liga Juara-Juara UEFA menggunakan gaya head-to-head, dan dengan itu kami menulisnya sebagai jenis untuk lelaran seterusnya; dan memandangkan kumpulan yang dicincang panjangnya lebih besar daripada satu (terdapat dua pasukan dalam setiap satu daripada mereka), bermakna kami masih mempunyai beberapa kerja yang perlu dilakukan dari segi pengasingan, kami menyuap setiap daripada mereka kembali ke sortAndDivideTable sebagai jadual baharu.

Mari kita ikuti sejarah set pertama pasukan seri. Kami telah memasuki satu pusingan kriteria, jadi perkara pertama yang pertama kita hitung sub-jadual perlawanan mereka: kita melihat bahawa Bayern Munich tewas di tempat sendiri (Bayern Munich 2-3 Manchester City) tetapi kemudian menang di tempat sendiri dengan margin yang lebih besar (Manchester City 1-3 Bayern Munich), sekali gus menimbulkan sub-jadual

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

Sekarang, mereka terikat dalam mata (head-to-head): oleh itu langkah pengumpulan membiarkan jadual ini tidak berubah, langkah pengisihan tiada kaitan dan kami mencapai penghujung lelaran rekursif tanpa banyak pencapaian; oleh itu kami beralih ke kriteria seterusnya (perbezaan matlamat), mengekalkan jenis head-to-head, dan kami menyuap meja itu kembali ke dalam fungsi.

Memandangkan kami berada di tengah-tengah larian head-to-head, kami melangkau langkah pengiraan semula jadual (seperti yang dinyatakan dalam bahagian takeaway kedua, itu adalah sesuatu yang kami hanya lakukan apabila proses head-to-head bermula, atau apabila berakhir selepas semua kriteria telah memohon tanpa mencapai keputusan); tetapi kali ini kriterianya ialah perbezaan gol, jadi langkah kumpulan berjaya memotong jadual menjadi dua sub-jadual (panjang satu setiap satu) kerana satu pasukan mempunyai perbezaan gol 1, manakala satu lagi mempunyai perbezaan gol -1 . Ini membolehkan langkah penyisihan untuk melihat kedudukan asal sekali lagi, dan kini pasti mengatakan bahawa Bayern Munich berada di atas Manchester City.

Dan memandangkan set cincang yang terhasil daripada langkah pengelompokan adalah panjang tepat satu (bermakna tiada ikatan yang tinggal), kami keluar dari rekursi pada cawangan ini dengan tidak memanggil fungsi itu lagi.

Di sisi lain, untuk sejarah set kedua, kami mempunyai Viktoria Plzeň yang juga menang di tempat sendiri (Viktoria Plzeň 2-1 CSKA Moscow) tetapi kemudian tewas di tempat sendiri dengan margin yang sama (CSKA Moscow 3 -2 Viktoria Plzeň), dengan itu menghasilkan

GF = Goals For (gol dijaringkan), GA = Goals Against (gol dibolosi), GD = Goal Difference.

di mana kedua-dua pasukan terikat pada perbezaan gol head-to-head dan gol head-to-head dijaringkan, maka mereka memerlukan kriteria tambahan (dan oleh itu langkah rekursi tambahan) untuk disusun tidak seperti rakan sejawatan mereka. Dalam kes Liga Juara-Juara UEFA, kriteria seterusnya ialah jumlah gol yang dijaringkan di tempat lawan—di sini 2 untuk Viktoria Plzeň dan 1 untuk CSKA Moscow dalam rekod head-to-head mereka.

Sekali lagi, rekursi berakhir pada langkah ini dan kedudukan asal kini disusun sepenuhnya.

Apa yang bagus tentangnya

Contoh ini mempamerkan beberapa aspek positif pendekatan rekursif: kedua-dua cabang tidak perlu 'bercakap' antara satu sama lain—malah, salah satu daripadanya memerlukan pemecah seri tambahan untuk diisih tetapi ini tidak membimbangkan lain. Sebarang perkara mengenai kedalaman rekursi yang telah kami capai, seperti sama ada kami perlu menggunakan semula secara bersemuka atau tidak (seperti yang dijelaskan dalam bahagian dengan nama yang sama di atas) boleh diselesaikan oleh setiap cawangan secara berasingan.

Selain itu, kerana persilangan mana-mana dua cawangan sentiasa kosong (kerana ia dicipta dalam langkah pengumpulan melalui .reduce(), yang sentiasa membahagikan tatasusunan dalam kelas kesetaraan tidak bersilang), setiap cawangan boleh mengisih sendiri secara bebas pasukan dalam kedudukan asal tanpa memijak kaki satu sama lain. Ini bermakna bahawa cawangan pasukan yang sangat seri boleh kehabisan keseluruhan kriteria head-to-head, dan dengan itu kembali kepada pemeriksaan keseluruhan dengan harapan untuk memecahkan seri, tanpa ini menjejaskan perbandingan mana-mana pasukan lain—kerana tiada cabang pernah mempengaruhi orang lain.

Perhatikan juga bagaimana rekursi telah berakhir: apabila dua pasukan diisih mengikut kriteria semasa, .reduce() akan menghasilkan sub-tatasusunan yang panjangnya lebih kecil daripada jadual sekarang, supaya langkah seterusnya dalam rekursi akan lebih dekat untuk mencapai tatasusunan panjang satu (pada ketika itu fungsi tidak dipanggil lagi); dan jika seri berterusan sehingga tamat, kriteria akhir sentiasa sama ada lukisan lot rawak atau isihan abjad, yang pasti menghasilkan keputusan sama ada cara (pengecam pasukan dikehendaki unik pada masa input).

Pertimbangan akhir

Terdapat banyak lagi yang perlu diperkatakan tentang gaya pecah seri, serta dari segi fungsi pakej ini dan semua pilihan penyesuaian yang boleh diakses oleh pengguna dalam menentukan peraturan kejohanan.

Saya mungkin menulis lebih lanjut tentang perkara ini pada masa hadapan, terutamanya untuk perkara yang berkaitan dengan kaedah .ties() yang menyediakan penerangan teks tentang pasukan mana yang diisih, termasuk bagaimana dan pada langkah apa, yang pengguna akhir mungkin ingin mencetaknya demi kejelasan.

Tetapi sementara itu, sila semak repositori di GitHub jika anda mahu...

...dan semestinya, ini peluang untuk saya belajar juga. Jika anda melihat sebarang perkara yang membimbangkan atau margin untuk penambahbaikan, jangan segan dan beritahu saya dalam komen!

Atas ialah kandungan terperinci Pakej JavaScript pertama saya (dengan rekursi untuk kemenangan). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!