나는 아직 JavaScript의 깊이를 탐구하고 있는 취미 개발자이고 이전에 패키지를 작성하거나 게시한 적이 없기 때문에 누구에게도 아무것도 가르칠 수 있는 입장이 아닙니다. 하지만 제가 할 수 있는 일은 본질적으로 아직 불완전하지만 생각해낸 내용이 매우 즐거웠던 글을 작성하면서 겪은 경험을 공유하는 것입니다.

모든 것은 온라인에서 그다지 많이 다루어지지 않은 것을 보고 놀랐던 문제와 약간 예상치 못한 방법, 즉 재귀를 사용하여 깔끔하게 해결할 수 있다는 것을 알게 된 문제에서 시작되었습니다.

리그 테이블의 문제

축구(또는 일반적인 스포츠 또는 순위가 필요한 모든 경쟁 환경)를 좋아하는 분들은 확실히 리그 테이블: 특정 수의 팀이 서로 경쟁하는 개념에 익숙할 것입니다. 일련의 경기에서 각 팀은 승리, 무승부, 패배 여부에 따라 특정 포인트를 획득합니다. 리그 테이블은 모든 팀을 점수가 높은 순서대로 수집하여 어느 팀이 승자로 결정되는지 명확하게 보여줍니다.

프로그래밍 측면에서 이는 전혀 문제가 되지 않는 상황입니다. 어느 팀이 경기에서 승리했는지 확인하는 것은 사소한 일입니다(축구에서는 두 팀 중 어느 팀이 더 많은 골을 넣었는지 확인하는 것만 큼 쉽습니다). 모든 경기에서 얻은 포인트는 간단한 추가로 귀결됩니다. JavaScript에는 배열에 대한 기본 정렬 방법도 함께 제공되므로 정렬 단계도 복잡하지 않습니다.

둘 이상의 팀이 승점 동점을 이루면 상황이 조금 덜 단순해진다고 생각할 수 있으며, 이 경우 타이브레이커가 필요합니다. 다시 한 번 축구로 돌아가면, 일반적인 승부차기에는 일반적으로 골득실차(득점수 - 실점득점), 득점자체 득점, 승수 등이 포함됩니다. 그리고 이는 다시 한 번 문제를 해결하는 것이 그다지 어렵지 않다는 것을 시사합니다. 승점이 동점인 경우 문제의 팀을 다른 기준에 따라 정렬하는 것으로 전환하면 됩니다. 사용자가 어느 적용할 순위 결정이나 순서를 선택하도록 허용하는 것조차도 선택 항목이 유한하고 하드 코딩되어 있는 한 구현하기 어렵지 않습니다.

이는 대부분의 온라인 솔루션이 문제를 해결하는 정도입니다. 그러나 문제는 처음에 예상했던 것보다 조금 더 미묘하고 더 깊게 진행됩니다.

일대일 대 전반적인 스타일

사실 모든 종류의 기준(골 차이, 득점 등, 심지어 승점 자체도)은 두 가지 다른 방식으로 확인할 수 있습니다. 소위 전체 검사)는 모든 테이블에서 나타나는 전체 테이블을 보는 표준 유형의 검사입니다. 모든 팀이 치른 경기를 보고 이를 바탕으로 팀을 비교합니다. 또는 제한된 의미에서(소위 일대일 확인) 두 개 이상의 팀이 승점에서 동점일 경우 이후의 승점 결정은 두 팀 사이에 진행된 경기 내에서만 확인됩니다. 해당 팀.

예를 들어 보면 이러한 차이가 더욱 분명해집니다. UEFA Euro 2016에서 E조의 최종 테이블은 다음과 같았습니다

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

이탈리아와 벨기에는 승점에서 동점이며, 유로의 첫 번째 승점은 골득실차(이탈리아와 벨기에가 여전히 동점이며 각각 2골)이며 그 다음에는 득점한 골 수입니다. 이 시점에서 벨기에는 예상할 수 있습니다 3대 4골로 이탈리아를 꺾고 승리.

그러나 유로는 승점차가 있는 팀을 대결 방식으로 정렬하는 대회입니다. 이는 이탈리아와 벨기에가 동점이 깨지는 경우, 동점에 해당하는 팀만으로 구성된 새 하위 테이블을 즉시 계산합니다. 그리고 첫 번째 경기일에 이탈리아를 상대로 0-2로 끝난 단일 경기를 치렀기 때문에 이 하위 테이블은 다음과 같습니다(축구에서는 승리 시 3점, 무승부 시 1점, 패배 시 무득점)

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

이는 정면 승점(3 대 0)으로 인해 이탈리아가 벨기에보다 즉시 순위가 높다는 것을 의미합니다.

각 대회는 일반적으로 서로 다른 스타일을 사용하지만(유로 대회는 방금 본 것처럼 맞대결 스타일을 사용하지만, 예를 들어 FIFA 월드컵은 전체 점검을 사용하는 것으로 유명합니다) 둘 다 서로 다른 방식으로 전환합니다. 스타일은 첫 번째 기준 실행이 특정 동점을 깨는 데 결정적이지 않아야 합니다.

이는 잠재적으로 정면 대결이 조만간(유로와 같은 대회에서 즉시 또는 FIFA 월드컵에서 두 번째 동점 결정으로) 일어날 가능성이 있다는 것을 의미합니다. 그래서 제가 여기서 깨달은 점은 우리가 보는 테이블은 정렬 과정 중에 잠재적으로 변경될 수 있다는 것입니다 즉각적으로 나오든 안 나오든 일대일 스타일이 여기에 달려 있기 때문입니다. 사실입니다.

하지만 다음 예에서 볼 수 있듯이 이것이 제가 유일하게 시사하는 바는 아니었습니다.

더 복잡한 사항: 정면 재적용

벨기에는 모든 팀이 승점 4점으로 조를 마친 UEFA 유로 ​​2024에서 다시 한 번 유명한 E조의 주인공이 되었습니다

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

모든 팀이 승점 동률을 이루고 있기 때문에, 어쨌든 맞대결 결과의 하위 테이블은 여전히 ​​전체 테이블입니다. 슬로바키아와 우크라이나는 골득실차를 기준으로 최하위로 분류되었으며, 루마니아는 득점 득점 수가 우세하여 벨기에보다 높습니다(루마니아 4, 벨기에 2). 실제로 최종 테이블의 모습은 이러했습니다.

하지만 이상하게 생각할 수도 있습니다. 벨기에와 루마니아가 정확히 한 경기를 치렀고, 두 번째 경기에서 벨기에가 2-0으로 승리했습니다. 그렇다면 벨기에가 루마니아보다 높은 순위를 차지하지 못한 이유는 무엇입니까? 이것은 중요하지 않습니까? 이전처럼 슬로바키아와 우크라이나가 나머지 국가로부터 분리된 후 하위 테이블이 다시 계산되지 않은 이유는 무엇입니까?

문제의 진실은 UEFA 유로 ​​규정(§20.01-d.)에 따라 모든 단계에서 맞대결 결과의 재계산이 발생하지 않는다는 것입니다. 그러나 전체 동점자 목록이 소진된 경우에만 해당됩니다. 승점 및 골득실 동점 이후에도 아직 득점한 골 수를 확인해야 하므로 이를 살펴봅니다. 이것이 루마니아가 승리하는 이유입니다. 그도 동점이라면 그 시점에서만 여전히 동점인 팀(벨기에와 루마니아)이 치른 단일 경기를 기반으로 하위 테이블을 실제로 고려하기 시작할 것입니다. 실제로 벨기에가 승리로 인해 1위를 차지하게 되었습니다.

두 번째 요점은 다음과 같습니다. 정렬 과정에는 깊이 개념이 있습니다.얼마나 해당 분야에 관심이 있는지에 따라 다릅니다. 하위 테이블 재계산을 진행할지 여부와 같은 다양한 결정을 내려야 합니다. 이 경우 기준 목록이 계속 진행 중이므로 아직 진행하지 마십시오.

정렬 기능의 형태를 결정하게 된 주요 포인트입니다.

재귀적 접근 방식

내 패키지가 구현하는 클래스의 .standings() 메서드를 통해 액세스하는 정렬 알고리즘은 재귀 함수에 의존합니다

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

특정 단계 테이블에서 현재 정렬할 팀의 데이터가 포함된 테이블이 있는 경우 반복은 반복 횟수 및 기타 관련 정보를 추적합니다(예: 일대일 또는 전체 유형인 경우). of check), 기준은 적용할 기준(예: 점수, 골 차이, 득점 수)의 순서 목록을 나타내는 배열입니다.

재귀는 모든 팀이 플레이한 모든 경기에서 계산되고 여전히 순서가 지정되지 않은 테이블로 시작됩니다. 알고리즘의 첫 번째 반복은 항상 전체 유형입니다(따라서 재귀가 시작될 때 초기화됩니다). 정의에 따라 첫 번째 확인은 항상 모든 항목에서 얻은 포인트 수이기 때문입니다. match; 정의에 따르면 기준 배열의 첫 번째 요소는 항상 "포인트"입니다.

이 시작 테이블은 안전하게 보관되어 있습니다. 어떤 단계에서든 항목은 수정되지 않지만 해당 행은 조금씩 정렬됩니다. 참고로 지금부터는 '원래 순위표'라고 부르겠습니다.

UEFA 챔피언스 리그의 실제 사례

이를 염두에 두고 2013-14 UEFA Champions League에서 D조가 제공한 예를 통해 알고리즘을 이해하는 것이 가능합니다. 결과는 다음과 같습니다

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

앞서 언급했듯이 알고리즘의 첫 번째 단계에서 정렬 기준은 '포인트'입니다. sortAndDivideTable의 첫 번째 작업은 테이블을 그에 따라 분할하는 것이며 이를 위해 표준 .reduce() JavaScript 배열 메서드를 사용합니다.

이 경우 동점 팀으로 구성된 두 그룹(바이에른 뮌헨/맨체스터 시티 및 빅토리아 플젠/CSKA 모스크바, 각각 15점과 3점)이 있으므로 각각 두 팀으로 구성된 두 개의 하위 테이블을 생성합니다. 그런 다음 원래 순위는 부분적으로 정렬됩니다. 이들 팀 중 일부는 확실히 다른 팀보다 위에 있을 것입니다(예: 맨체스터 시티는 확실히 빅토리아 플젠보다 위에 있습니다). 하지만 승점 면에서 같은 팀은 아직 결정되지 않은 상태로 남아 있습니다.

이 첫 번째 재귀 단계가 거의 끝나가면서 우리는 다음에 어디로 갈지 결정합니다. UEFA 챔피언스 리그가 일대일 스타일을 사용한다는 것을 알고 있으므로 이를 다음 반복의 유형으로 작성합니다. 분할된 그룹의 길이가 1보다 길기 때문에(각 그룹에는 두 개개의 팀이 있음) 정렬 측면에서 아직 해야 할 일이 남아 있음을 의미합니다. 우리는 각각을 새로운 테이블로 sortAndDivideTable에 다시 공급합니다.

첫 번째 동점 팀의 역사를 따라가 보겠습니다. 우리는 일대일 기준을 입력했으므로 먼저 경기의 하위 테이블을 계산합니다. 바이에른 뮌헨이 홈에서 패했지만(바이에른 뮌헨 2-3 맨체스터 시티) 홈에서 승리했다는 것을 알 수 있습니다. 더 큰 차이로(맨체스터 시티 1-3 바이에른 뮌헨) 하위 테이블이 발생했습니다

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

이제 두 항목은 (일대일) 점으로 묶여 있습니다. 따라서 그룹화 단계는 이 테이블을 변경하지 않고 그대로 두고 정렬 단계는 아무 관련이 없으며 별다른 성과 없이 재귀 반복의 끝에 도달합니다. 따라서 다음 기준(골 차이)으로 이동하여 일대일 유형을 유지하고 테이블을 함수에 다시 공급합니다.

직전 진행 중이므로 테이블 재계산 단계를 건너뜁니다. (두 번째 테이크어웨이 섹션에서 언급했듯이 이는 정면 대결 과정에서만 수행하는 작업입니다. 시작 또는 모든 기준이 적용된 후 종료되는 경우 결정에 도달함) 그러나 이번에는 기준이 골득실차이므로 그룹화 단계에서는 한 팀의 골득실차가 1이고 다른 팀의 골득실차가 -1이므로 테이블을 두 개의 하위 테이블(각 길이는 하나씩)로 나누는 데 성공합니다. . 이를 통해 정렬 단계에서 원래 순위를 다시 한 번 살펴보고 바이에른 뮌헨이 맨체스터 시티보다 순위가 높다

그리고 그룹화 단계에서 잘게 자른 결과 집합의 길이는 정확히 1이므로(남은 연결이 없음을 의미) 더 이상 함수를 호출하지 않고 이 분기에서 재귀를 종료합니다.

반면, 두 번째 세트의 역사에서는 빅토리아 플젠이 홈에서도 마찬가지로 승리했지만(빅토리아 플젠 2-1 CSKA 모스크바) 홈에서 같은 차이로 패했습니다(CSKA 모스크바 3). -2 Viktoria Plzeň),

GF = Goals For(득점), GA = Goals Against(실점), GD = 골득실차

두 팀 모두 일대일 골 차이와 일대일 골 득점이 동점이므로 상대 팀과 다르게 정렬하려면 추가 기준(따라서 추가 재귀 단계)이 필요합니다. UEFA 챔피언스 리그의 경우 다음 기준은 홈 원정 경기에서 득점한 골 수입니다. 여기서는 빅토리아 플젠이 2골, CSKA 모스크바가 1골을 기록했습니다.

다시 한번, 이 단계에서 재귀가 종료되고 이제 원래 순위가 완전히 정렬되었습니다.

뭐가 좋은데?

이 예는 재귀 접근 방식의 몇 가지 긍정적인 측면을 보여줍니다. 두 분기는 서로 '대화'할 필요가 없습니다. 실제로 그 중 하나는 정렬을 위해 추가 순위 결정이 필요하지만 이는 문제가 되지 않습니다. 다른. 우리가 도달한 재귀 깊이에 관한 모든 문제(예: 일대일 재적용(위의 동일한 이름 섹션에서 설명)을 해야 하는지 여부 등)은 각 분기별로 독립적으로 정렬할 수 있습니다.

또한 두 분기의 교차점은 항상 비어 있으므로(항상 교차하지 않는 등가 클래스에서 배열을 분할하는 .reduce()를 통해 그룹화 단계에서 생성되므로) 각 분기는 독립적으로 자체 정렬할 수 있습니다. 서로 발을 밟지 않고 원래 순위의 팀. 즉, 동점률이 매우 높은 팀의 분기는 전체 일대일 기준을 모두 소진하여 다른 팀의 비교에 영향을 주지 않고 동점을 깨기 위해 전체 점검으로 되돌아갈 수도 있습니다. 다른 어떤 것에도 영향을 미치지 않습니다.

재귀가 끝나는 방법에 주목하세요. 두 팀이 현재 기준에 따라 정렬될 때마다 .reduce()는 길이가 현재 테이블의 길이보다 훨씬 작은 하위 배열을 생성합니다. 재귀의 다음 단계는 길이가 1인 배열에 더 가까워집니다(이 시점에서 함수는 더 이상 호출되지 않습니다). 동률이 끝까지 지속되는 경우 최종 기준은 항상 무작위 추첨 또는 알파벳순 정렬이며, 이는 어느 쪽이든 결과를 생성해야 합니다(팀 식별자는 입력 시 고유해야 함).

최종 고려사항

동점 결정 스타일뿐만 아니라 이 패키지의 기능과 토너먼트 규칙을 정의할 때 사용자가 액세스할 수 있는 모든 사용자 정의 옵션 측면에서 할 말이 많습니다.

나중에 이에 대해 더 많이 쓸 수 있습니다. 특히 최종 사용자가 인쇄하려는 방법과 단계를 포함하여 어떤 팀이 정렬되었는지에 대한 텍스트 설명을 제공하는 .ties() 메서드와 관련된 내용에 대해 더 많이 쓸 수 있습니다. 명확성을 위해서입니다.

그동안 원하는 경우 GitHub의 저장소를 확인해보세요...

...그리고 자연스럽게 저에게도 배울 수 있는 기회가 되었습니다. 혹시 불편한 점이나 개선할 여지가 있다면 주저하지 말고 댓글로 알려주세요!

위 내용은 내 첫 번째 JavaScript 패키지(승리를 위한 재귀 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!