스트레스 테스트 - 알고리즘카

스트레스 테스트는 무작위 테스트를 생성하고 두 풀이의 실행 결과를 비교하는 방식으로 풀이의 오류를 찾는 방법입니다:

정확하지만 느린 해법.
빠르지만 틀린 풀이.

이 방법은 IOI 형식의 대회에서 특히 유용합니다. 시간이 많거나, 작은 부분 문제에 대한 풀이를 이미 작성해 둔 경우에 그렇습니다.

더 자세히 설명하면 다음과 같습니다.

빠르지만 우리가 찾고자 하는 버그가 있는 smart 풀이가 있습니다.
느리지만 확실히 올바른 풀이 stupid를 작성합니다.
생성기 gen을 작성합니다. 이 생성기는 무작위로 생성한 올바른 테스트 하나를 출력합니다.
이 모든 것을 checker 스크립트에 넣습니다. 이 스크립트는 테스트를 $n$번 생성하여 stupid와 smart에 입력으로 주고, 출력을 비교하여 둘이 다르면 멈춥니다.

경우에 따라서는 문제 유형에 따라 전체적인 방식이 조금 달라질 수 있습니다. 이에 대해서는 글의 마지막에서 다루겠습니다.

#구체적인 예시

문제. 수 배열 $1 \le a_1 … a_n \le 10^9$이 있습니다. 최솟값 원소의 값을 구하십시오.

기준으로 사용할 stupid 풀이의 코드를 제시합니다:

int a[maxn];

void stupid() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, a[i]);
    cout << ans;
}

반복문의 경계에 오류가 있는 해법 smart가 있다고 합시다:

int a[maxn];

void smart() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 1e9;
    for (int i = 1; i < n; i++)
        ans = min(ans, a[i]);
    cout << ans;
}

이런 예시에서도 무작위 테스트를 손으로 골라 답이 올바른지 확인하다 보면 오류를 찾는 데 오랜 시간이 걸릴 수 있습니다. 그래서 우리는 두 풀이가 서로 다른 답을 내는 테스트를 찾아, 이를 바탕으로 smart의 오류를 찾고자 합니다.

#인라인 테스트

참고. 저자는 이렇게 하는 것을 권장하지 않지만, 많은 사람들에게는 이 방식이 더 이해하기 쉽게 느껴집니다.

가장 간단한 접근 방식은 스트레스 테스트의 모든 로직을 하나의 소스 파일에 구현하는 것입니다. 테스트 생성기와 두 풀이를 각각 별도의 함수로 만들고, main의 반복문에서 이 함수들을 여러 번 호출합니다.

생성기는 무작위 테스트 하나를 어딘가에 기록해야 합니다. 가장 간단한 방법으로는 다음과 같은 것들이 있습니다.

자신의 반환값에;
참조로 전달된 변수에;
전역 변수에.

그다음 이 테스트를 해법 함수들에 차례로 전달하고, 각 함수는 마찬가지 방식으로 작업 결과를 어떻게든 넘겨줍니다. 이 결과들을 비교하여 답이 일치하지 않으면 테스트를 출력하고 종료할 수 있습니다.

int a[maxn];
int n;

int stupid() {
    int n;
    cin >> n;
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        ans = min(ans, a[i]);
    return ans;
}

int smart() {
    int n;
    cin >> n;
    int ans = 1e9;
    for (int i = 1; i < n; i++)
        ans = min(ans, a[i]);
    return ans;
}

void gen() {
    n = rand() % 10 + 1;
    for (int i = 0; i < n; i++)
        a[i] = rand();
}

int main() {
    for (int i = 0; i < 100; i++) {
        gen();
        if (smart() != stupid()) {
            cout << "WA" << endl;
            cout << n << endl;
            for (int j = 0; j < n; j++)
                cout << a[j] << ' ';
            break;
        }
        cout << "OK" << endl;
    }
    return 0;
}

이 접근 방식은 범용적이지만, 단점이 많습니다:

여러 문제를 테스트하려면 많은 코드를 중복해서 작성해야 합니다.
생성기나 기준 해답을 다른 언어로 작성할 수 없습니다(Python 같은 스크립트 언어로 작성하는 편이 더 간단하고 빠른 경우가 많습니다).
소스 코드가 더 비대해지고, 코드를 파악하기가 더 어려워집니다.
전역 변수를 사용할 때는 주의해야 합니다.
어떻게든 «스트레스 테스트» 모드와 일반적인 «콘솔 입력» 모드 사이를 전환할 수 있어야 합니다.

이 모든 로직을 별도의 프로그램으로 분리하고, 풀이 자체는 건드리지 않을 수도 있습니다.

#외부 스크립트를 이용한 테스트

요지는 다음과 같습니다:

모든 솔루션과 생성기는 별도의 파일에 둡니다. 이제 이 파일들이 반드시 같은 환경에서 실행될 필요는 없습니다.
테스트는 입출력 스트림 리다이렉션을 통해 전달됩니다. 프로그램은 테스트 시스템에서 자연스럽게 입력을 읽는 방식 그대로 입력을 읽습니다.
외부 스크립트를 실행하면, 이 스크립트는 생성기를 $n$번 실행하여 그 출력을 파일에 기록한 다음, 이 파일을 두 풀이에 입력으로 넣고 출력을 한 줄씩 비교합니다.

stupid.cpp, smart.cpp, gen.py 파일에는 이미 우리가 이해하고 있는 코드가 들어 있습니다. 다음은 checker.py 스크립트의 대략적인 코드입니다:

import os, sys

_, f1, f2, gen, iters = sys.argv
# первый аргумент это название программы, "checker.py",
# поэтому "забудем" его с помощью "_"

for i in range(int(iters)):
    print('Test', i + 1)
    os.system(f'python3 {gen} > test.txt')
    v1 = os.popen(f'./{f1} < test.txt').read()
    v2 = os.popen(f'./{f2} < test.txt').read()
    if v1 != v2:
        print("Failed test:")
        print(open("test.txt").read())
        print(f'Output of {f1}:')
        print(v1)
        print(f'Output of {f2}:')
        print(v2)
        break

필자는 보통 stupid와 smart를 checker.py와 같은 디렉터리에 미리 컴파일해 둔 뒤, python3 checker.py stupid smart gen.py 100 명령으로 이 스크립트를 실행합니다. 원한다면 컴파일 과정을 스크립트 안에 직접 작성할 수도 있습니다.

이 스크립트는 Linux / Mac용으로 작성되었습니다. Windows에서는 외부 명령에서 ./를 제거하고 python3 대신 python을 써야 합니다.

프로그램 중 하나라도 파일 끝에 줄 바꿈을 출력하지 않으면 체커가 출력이 다르다고 판단한다는 점을 잊지 마십시오.

#변형

때로는 stupid조차 작성할 수 없는 경우도 있습니다(예를 들어 기하 문제에서). 하지만 여러 가지 다른 풀이를 작성하여 서로 비교하며 테스트할 수는 있습니다. 이때 각 풀이의 버그가 크게 겹치지 않기를 기대하는 것입니다. 출력이 서로 다르다면, 적어도 그중 하나는 틀렸다는 것이 보장됩니다. 또한 마찬가지로 WA를 받는 다른 사람의 풀이를 stupid로 삼을 수도 있으며, 그러면 적어도 둘 중 하나에서는 버그를 찾게 될 것입니다.

문제의 출력이 하나로 정해지지 않는 경우(예를 들어 최솟값의 인덱스를 출력하는 문제라면 그러한 인덱스가 여러 개일 수 있습니다)에는 stupid 풀이와 v1 != v2 대신, 테스트와 풀이의 출력을 읽어 검사한 뒤 yes / no를 출력하는 별도의 체커 스크립트를 사용해야 합니다.

인터랙티브 문제는 인터랙터를 작성하여 그 출력이 풀이로, 풀이의 출력이 인터랙터로 전달되도록 리디렉션하는 방식으로 테스트할 수 있습니다. Linux에서는 다음과 같이 합니다.

mkfifo fifo
./solution < fifo | ./interactor > fifo

하지만 이 방법으로는 상호작용 기록을 바로 얻을 수 없습니다. 이를 위해서는 인터랙터가 유용한 정보를 모두 별도의 파일에 기록해야 합니다.

이 밖에도 유용할 수 있는 것이 많이 있습니다:

인터랙티브 문제에 대한 완전한 지원,
멀티스레드 테스트,
메모리 및 시간 제한 지원,
수동 테스트 자동 실행,
소스 코드 변경 감지 및 자동 재테스트,
채점 시스템에서 테스트 파싱,
출력의 컬러 diff 및 체커를 위한 기타 사용자 정의 출력.

저자는 얼마 전에 이 모든 기능을 갖춘 더 발전된 프로그램을 솔루션 테스트용으로 작성했지만, 개발을 중단했습니다. 누군가 이 프로그램의 개발을 이어 가거나 직접 새로 작성하고 싶다면 알려 주십시오.