Sinh test và stress test

Mức độ: Nâng cao

Chương trình chạy đúng với ví dụ của đề chưa chắc đã đúng: ví dụ thường nhỏ và “đẹp”. Stress test là cách tự tìm lỗi bằng máy: cho chương trình cần kiểm tra và một chương trình vét cạn chắc chắn đúng cùng chạy trên hàng trăm bộ dữ liệu ngẫu nhiên, rồi so kết quả. Gặp bộ nào lệch là đã có một test để sửa lỗi.

Toàn bộ bài luyện tập trên mục này đều được kiểm tra theo đúng cách đó.

Ba chương trình

1. Lời giải cần kiểm tra (loi_giai.py hoặc loi_giai.cpp).
2. Vét cạn (vet_can.py): cách đơn giản nhất, chậm cũng được, miễn là chắc chắn đúng. Thường là thử mọi khả năng, hoặc làm đúng theo lời đề.
3. Sinh test (sinh.py): in ra một bộ dữ liệu ngẫu nhiên nhỏ theo đúng định dạng đề, nhận số hạt giống (seed) để có thể sinh lại đúng bộ đó.

Ví dụ với bài đếm cặp có tổng bằng S:

sinh.py

import random
import sys

R = random.Random(int(sys.argv[1]))      # cùng seed thì sinh cùng bộ dữ liệu
n = R.randint(1, 8)                      # nhỏ để vét cạn chạy nhanh và dễ đọc khi sai
print(n, R.randint(0, 15))
print(*[R.randint(0, 9) for _ in range(n)])

vet_can.py

n, s = map(int, input().split())
a = list(map(int, input().split()))
print(sum(1 for i in range(n) for j in range(i + 1, n) if a[i] + a[j] == s))

Vòng lặp so sánh

Chương trình sau chạy cả ba chương trình trên nhiều seed, dừng ở bộ dữ liệu đầu tiên cho kết quả khác nhau:

import subprocess
import sys

def chay(lenh, du_lieu=""):
    return subprocess.run(lenh, input=du_lieu, capture_output=True, text=True).stdout.strip()

for seed in range(1000):
    du_lieu = chay(["python3", "sinh.py", str(seed)])
    ket_qua = chay(["python3", "loi_giai.py"], du_lieu)     # hoặc ["./loi_giai"] với C++ đã biên dịch
    dung = chay(["python3", "vet_can.py"], du_lieu)
    if ket_qua != dung:
        print("Sai ở seed", seed)
        print(du_lieu)
        print("Lời giải in:", ket_qua)
        print("Vét cạn in: ", dung)
        sys.exit()
print("Không tìm thấy lỗi sau 1000 bộ dữ liệu")

Khi thấy bộ sai, chạy tay lời giải trên bộ đó (in thêm các biến trung gian) để tìm chỗ sai.

Mẹo để stress test hiệu quả

• Dữ liệu nhỏ, giá trị nhỏ: n từ 1 đến 8, giá trị từ 0 đến 9. Lỗi thường lộ ra ngay ở test nhỏ, và test nhỏ thì đọc được bằng mắt. Giá trị nhỏ còn làm xuất hiện nhiều số trùng, chỗ hay có lỗi.
• Cho cả trường hợp biên: để n = 1 có thể xảy ra, cho phép số âm, số 0, các phần tử bằng nhau nếu đề cho phép.
• Vét cạn phải thật sự đơn giản: nếu vét cạn dùng cùng ý tưởng với lời giải thì hai chương trình có thể cùng sai.
• Kiểm tra cả trường hợp lớn: chạy lời giải với n lớn nhất (sinh bằng một chương trình khác) để xem thời gian và bộ nhớ, không cần so kết quả.

Bài có nhiều đáp án đúng

Nếu đề cho phép in bất kỳ đáp án nào đúng (ví dụ in một đường đi ngắn nhất), không so được trực tiếp với vét cạn. Thay vào đó viết chương trình kiểm tra: đọc dữ liệu và đáp án của lời giải, kiểm tra đáp án có hợp lệ không (ví dụ đường đi có thật sự nối hai đỉnh, có đúng độ dài ngắn nhất mà vét cạn tính ra không), in OK hoặc lý do sai.

Test đặc biệt nên tự thử trước khi nộp

Loại test	Ví dụ
nhỏ nhất	n = 1, xâu dài 1, đồ thị một đỉnh không có cạnh
mọi phần tử bằng nhau	dãy toàn số 5
đã sắp xếp hoặc sắp xếp ngược	1 2 3 … n và n … 3 2 1
giá trị lớn nhất	mọi ai = 109, để thử tràn số
không có đáp án	đồ thị không liên thông, mẫu không xuất hiện
cấu trúc xấu nhất cho thời gian	cây là một đường dài (DFS đệ quy sâu), dãy làm vòng while chạy nhiều nhất