Differential Testing

Algoritma cepat sulit diverifikasi: kompleksitas O(n log n) atau O(n) sering punya banyak cabang dan optimisasi. Differential testing menyelesaikan masalah ini dengan strategi sederhana — bandingkan output algoritma cepat dengan output brute force yang dipercaya benar pada ribuan input acak kecil. Bila hasil selalu sama, kepercayaan kita pada algoritma cepat meningkat drastis. Pada Chapter ini kita akan menerapkan differential testing untuk dua masalah klasik: maksimum subarray sum (Kadane O(n) vs brute O(n²)) dan hitung pasangan two-sum (hash map O(n) vs brute O(n²)). Tujuan akhirnya: menemukan bug pada solusi cepat sebelum kode dikirim ke judge produksi.

Aturan: Brute Force sebagai Oracle #

Differential testing bergantung pada dua implementasi:

Solusi cepat (fast): algoritma optimal yang sedang kita validasi.
Solusi brute force (brute): implementasi naif yang jelas benar — biasanya O(n²) atau O(n³).

Karena brute force sederhana, kita percaya implementasinya benar. Untuk input kecil (n ≤ 30), brute force masih cepat. Kita bandingkan fast(a) == brute(a) untuk ribuan input acak. Bila ada mismatch, kita temukan bug pada fast.

Mekanisme: Input Acak Kecil #

Differential test efektif bila:

Input kecil — brute force masih cepat. Untuk n ≤ 30, O(n²) = 900 operasi, O(n³) = 27000 operasi — semua sub-detik.
Rentang nilai sempit — misal [-10, 10]. Peluang memunculkan kasus batas (overflow, off-by-one) lebih tinggi bila nilai kecil dan mudah diverifikasi manual.
Trial banyak — ribuan trial memberi keyakinan probabilistik. 5000 trial pada input acak n=30 mencakup sebagian besar cabang.
Cetak input saat mismatch — bila ada bug, kita butuh counter-example untuk debugging.

Kode: Differential Testing Kadane vs Brute #

cpp
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <string>
#include <unordered_map>

// ---------- Brute force: max subarray sum — O(n^2) ----------
long long max_subarray_brute(const std::vector<int>& a) {
    int n = (int)a.size();
    long long best = 0;  // subarray kosong diizinkan: best = 0
    for (int i = 0; i < n; ++i) {
        long long cur = 0;
        for (int j = i; j < n; ++j) {
            cur += a[j];
            best = std::max(best, cur);
        }
    }
    return best;
}

// ---------- Fast: Kadane's algorithm — O(n) ----------
long long max_subarray_kadane(const std::vector<int>& a) {
    long long best = 0, cur = 0;
    for (int x : a) {
        cur += x;
        if (cur < 0) cur = 0;
        best = std::max(best, cur);
    }
    return best;
}

// ---------- Brute force: count distinct pairs (i<j) with a[i]+a[j]=T ----------
long long two_sum_pairs_brute(const std::vector<int>& a, int T) {
    long long cnt = 0;
    int n = (int)a.size();
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] + a[j] == T) cnt++;
    return cnt;
}

// ---------- Fast: hash map O(n) average ----------
long long two_sum_pairs_fast(const std::vector<int>& a, int T) {
    std::unordered_map<int,int> freq;
    long long cnt = 0;
    for (int x : a) {
        int need = T - x;
        auto it = freq.find(need);
        if (it != freq.end()) cnt += it->second;
        freq[x]++;
    }
    return cnt;
}

int main() {
    std::mt19937 rng(2024);

    int trials = 5000;
    int mismatch_count = 0;

    for (int t = 0; t < trials; ++t) {
        int n = std::uniform_int_distribution<int>(0, 30)(rng);
        std::vector<int> a(n);
        std::uniform_int_distribution<int> dist(-10, 10);
        for (int& x : a) x = dist(rng);

        long long bf = max_subarray_brute(a);
        long long fast = max_subarray_kadane(a);

        if (bf != fast) {
            mismatch_count++;
            if (mismatch_count <= 3) {
                std::cout << "[MISMATCH] max_subarray trial=" << t
                          << " brute=" << bf << " fast=" << fast << " input=[";
                for (int x : a) std::cout << x << ' ';
                std::cout << "]\n";
            }
        }
    }
    std::cout << "max_subarray: " << trials << " trials, " << mismatch_count
              << " mismatches\n\n";

    // --- Differential testing untuk two_sum_pairs ---
    int sum_trials = 3000;
    int sum_mismatch = 0;
    for (int t = 0; t < sum_trials; ++t) {
        int n = std::uniform_int_distribution<int>(0, 50)(rng);
        std::vector<int> a(n);
        std::uniform_int_distribution<int> dist(-15, 15);
        for (int& x : a) x = dist(rng);
        int T = dist(rng) * 2;

        long long bf = two_sum_pairs_brute(a, T);
        long long fast = two_sum_pairs_fast(a, T);
        if (bf != fast) {
            sum_mismatch++;
            if (sum_mismatch <= 3) {
                std::cout << "[MISMATCH] two_sum_pairs trial=" << t
                          << " T=" << T
                          << " brute=" << bf << " fast=" << fast << " input=[";
                for (int x : a) std::cout << x << ' ';
                std::cout << "]\n";
            }
        }
    }
    std::cout << "two_sum_pairs: " << sum_trials << " trials, "
              << sum_mismatch << " mismatches\n";
    return 0;
}

Output yang Dihasilkan:

text
max_subarray: 5000 trials, 0 mismatches

two_sum_pairs: 3000 trials, 0 mismatches

Bedah Kode Baris-per-Baris #

long long best = 0; for (int i ...) for (int j ...) cur += a[j];: brute force O(n²). Subarray dari i ke j, sum akumulatif. Bandingkan setiap kombinasi. Untuk n = 30, total ~465 iterasi — sangat cepat.
long long best = 0, cur = 0; for (int x : a) { cur += x; if (cur < 0) cur = 0; ... }: Kadane algorithm O(n). Bila cur menjadi negatif, reset ke 0 (mulai subarray baru lebih baik). Pakai long long agar tidak overflow bila nilai besar.
two_sum_pairs_brute: dua loop bersarang. Untuk setiap pasangan (i, j) dengan i < j, cek a[i] + a[j] == T. Jumlah pasangan terhitung dengan benar termasuk duplikat nilai (tetapi indeks berbeda).
two_sum_pairs_fast: hash map freq mencatat berapa kali tiap nilai muncul. Untuk setiap x, cari need = T - x di map — semua nilai need yang sudah muncul membentuk pasangan dengan x. Penting: insert x ke map setelah pencarian, agar tidak menggunakan elemen yang sama dua kali.
int n = std::uniform_int_distribution<int>(0, 30)(rng);: n acak dalam [0, 30]. Termasuk 0 (array kosong) — edge case wajib.
if (bf != fast): bila output berbeda, cetak input lengkap. Inilah counter-example yang kita cari. Bila 0 mismatch setelah 5000 trial, keyakinan kita pada fast sangat tinggi (meskipun bukan bukti matematis).

Strategi Pemilihan Brute Force #

Solusi Cepat	Brute Force yang Cocok
`O(n log n)` sort	`O(n²)` selection/insertion sort, kemudian bandingkan elemen-elemen
`O(n)` Kadane	`O(n²)` enumerasi subarray
`O(n)` hash two-sum	`O(n²)` enumerasi pasangan
`O(log n)` binary search	`O(n)` linear search
`O(E log V)` Dijkstra	`O(V²)` Dijkstra naif atau Floyd-Warshall
`O(2^n)` DP bitmask	`O(n!)` brute permutation

Keterbatasan Differential Testing #

Tiga keterbatasan utama:

Hanya untuk input kecil — brute force lambat. Untuk n = 10^5, differential test tidak praktis.
Brute force harus benar — bila brute force punya bug, test tidak berguna. Audit brute force seperti audit solusi produksi.
Tidak menemukan bug di cabang yang tidak terjangkau — bila bug hanya muncul untuk input dengan struktur khusus (misalnya semua elemen sama), random test mungkin tidak menemukannya. Kombinasikan dengan edge case test eksplisit.

Ringkasan #

Differential testing membandingkan output solusi cepat vs brute force pada ribuan input acak kecil.
Brute force wajib sederhana dan jelas benar — biasanya O(n²) atau O(n³).
Input acak kecil (n ≤ 30, nilai dalam rentang sempit) memaksimalkan peluang menemukan bug.
Cetak input saat mismatch untuk mendapatkan counter-example yang dapat direproduksi.
Differential test memberi keyakinan probabilistik, bukan bukti formal — kombinasikan dengan analisis invarian dan edge case test.