# -*- coding: utf-8 -*-


# -*- coding: utf-8 -*-
"""
Semi-Edgeworth large-volume experiments (2026-10-24)
====================================================
Two scale-parameter configurations, base X0 = centered Exp(1)
(Lyapunov ratio lambda = 2.4146, skewness gamma = 2.0), seed = 20261024,
Lyapunov threshold theta = 0.6.

  Experiment A (n = 3010): G1: 2500 x U(9,11),  G2: 10 x U(50,100),
                           G3: 300 x U(300,400), G4: 200 x U(400,600)
  Experiment B (n = 2020): G1: 1000 x U(9,11), G2: 1000 x U(20,40),
                           G3: 20 x U(200,400)

For each experiment and each K in {3, 4} the script compares:
  1. Semi-Edgeworth (k-means on c_i = sqrt(k_i), Lyapunov test per cluster;
     Good clusters -> Edgeworth-corrected Normal CF, Bad clusters -> Monte Carlo)
  2. Muller-inspired (simulate top 10% largest-k variables, Normal for the rest)
  3. FFT characteristic-function inversion (N = 2^14 and 2^17, truncation a = 4 sd)
  4. Overall Normal approximation

Reference ("true") distribution: full Monte Carlo of the whole sum with
M = 5000 * n replications.  Every Monte-Carlo-based method uses the budget
rule M = 5000 * (number of simulated variables).

Metrics: KS distance vs. the reference empirical CDF (on a dense quantile
grid) and relative error of the 95% / 99% / 99.9% quantiles.

Usage:
    python semi_edgeworth_experiments.py            # both experiments, K = 4 only
    python semi_edgeworth_experiments.py A 4        # experiment A only, K = 4
    python semi_edgeworth_experiments.py A 3        # experiment A only, K = 3

Requirements: numpy (matplotlib only for the PDF comparison figures).
Runtime note: the reference Monte Carlo (15.05M / 10.1M replications) is the
expensive part and is cached in true_A.npy / true_B.npy; delete those files
to regenerate. Density comparison figures (chunked KDE, ~120 MB peak memory)
are written to pdf_<tag>_k<K>.png.
"""
import json
import math
import os
import sys
import time

import numpy as np
from statistics import NormalDist

try:
    import matplotlib
    matplotlib.use("Agg")
    import matplotlib.pyplot as plt
    HAVE_MPL = True
except ImportError:
    HAVE_MPL = False

SEED = 20261024
THETA = 0.6
LAM = 2.4146          # Lyapunov ratio E|X0|^3 / (E X0^2)^{3/2}, centered Exp(1)
SKEW = 2.0            # skewness of Exp(1)
PROBS = [0.95, 0.99, 0.999]
M_PER_VAR = 5000      # Bad-group budget rule: M2 = 5000 * (#bad variables)
M_GOOD = 1_000_000    # Good-group sample size: M1 = 1e6; Semi uses M = max(M1, M2)
MAKE_FIGURES = False  # set True to also write pdf_<tag>_k<K>.png (chunked KDE)
chunk_size=500000     #when running simulation, chunk large M into smaller batch ,once used it clear the momery


CONFIGS = {
    "A": dict(groups=[(2500, 9, 11), (10, 50, 100), (300, 300, 400), (200, 400, 600)],
              true_file="true_A.npy"),
    "B": dict(groups=[(1000, 9, 11), (1000, 20, 40), (20, 200, 400)],
              true_file="true_B.npy"),
}


# ---------------------------------------------------------------- scale parameters
def make_k(tag):
    """Deterministic scale-parameter list (group order preserved)."""
    rng = np.random.default_rng(SEED)
    return np.concatenate([rng.uniform(lo, hi, m)
                           for m, lo, hi in CONFIGS[tag]["groups"]])


# ------------------------------------------------------- reference distribution
def true_mc(tag, k):
    """Full Monte Carlo of S = sum k_i * (E_i - 1), E_i ~ Exp(1).
    Cached on disk; chunked to bound memory."""
    f = CONFIGS[tag]["true_file"]
    if os.path.exists(f):
        return np.fromfile(f, dtype=np.float64)
    n = len(k)
    M = 10000000
    rng = np.random.default_rng(SEED + 100)
    kf = k.astype(np.float32)
    out = open(f, "wb")
    chunk = 100000
    t0 = time.perf_counter()
    for s in range(0, M, chunk):
        m = min(chunk, M - s)
        X = rng.exponential(1.0, (m, n)).astype(np.float32) - np.float32(1.0)
        (X @ kf).astype(np.float64).tofile(out)
        if (s // chunk) % 200 == 0:
            print(f"  true MC {tag}: {s:,}/{M:,}  ({time.perf_counter() - t0:.0f}s)")
    out.close()
    return np.fromfile(f, dtype=np.float64)


# ------------------------------------------------------------------- clustering
def kmeans_sqrt(k, K, restarts=50, iters=200):
    """Plain 1-D k-means (k-means++ seeding) on c_i = sqrt(k_i)."""
    c = np.sqrt(np.abs(k))
    n = len(k)
    rng = np.random.default_rng(SEED)
    best = None
    for _ in range(restarts):
        cent = [c[rng.integers(n)]]
        for _ in range(K - 1):
            d2 = np.min((c[:, None] - np.array(cent)) ** 2, axis=1)
            cent.append(c[rng.choice(n, p=d2 / d2.sum())])
        cent = np.array(cent)
        for _ in range(iters):
            lab = np.argmin((c[:, None] - cent) ** 2, axis=1)
            new = np.array([c[lab == j].mean() if (lab == j).any() else cent[j]
                            for j in range(K)])
            if np.allclose(new, cent):
                break
            cent = new
        inertia = ((c - cent[lab]) ** 2).sum()
        if best is None or inertia < best[0]:
            best = (inertia, lab.copy())
    return best[1]


def lyapunov_split(k, labels, K):
    """Apply L = lambda * B with B = sum k^3 / (sum k^2)^{3/2} per cluster."""
    order = sorted(range(K), key=lambda j: k[labels == j].mean())
    good_idx, bad_idx, clusters = [], [], []
    for ci, j in enumerate(order, 1):
        idx = np.where(labels == j)[0]
        kg = k[idx]
        B = float((kg ** 3).sum() / (kg ** 2).sum() ** 1.5)
        L = LAM * B
        dec = "Good" if L < THETA else "Bad"
        clusters.append(dict(cluster=ci, count=len(idx), kmin=float(kg.min()),
                             kmax=float(kg.max()), L=L, decision=dec))
        (good_idx if L < THETA else bad_idx).extend(idx.tolist())
    good_idx = np.array(sorted(good_idx), dtype=int)
    bad_idx = np.array(sorted(bad_idx), dtype=int)
    return clusters, good_idx, bad_idx


# ---------------------------------------------------------------------- metrics
class Metric:
    """KS distance and quantile errors vs. the reference empirical CDF,
    evaluated on a dense grid of reference quantiles."""

    def __init__(self, true_sum):
        self.true = np.sort(true_sum)
        self.M = len(self.true)
        self.grid = np.quantile(self.true, np.linspace(1e-6, 1 - 1e-6, 400_001))
        self.F_true = np.searchsorted(self.true, self.grid, side="right") / self.M
        self.q_true = np.quantile(self.true, PROBS)

    def from_sample(self, sample):
        s = np.sort(sample)
        F = np.searchsorted(s, self.grid, side="right") / len(s)
        qs = np.quantile(s, PROBS)
        return self._eval(F, qs)

    def from_cdf(self, cdf_fn, quant_fn):
        F = cdf_fn(self.grid)
        qs = np.array([quant_fn(p) for p in PROBS])
        return self._eval(F, qs)

    def _eval(self, F, qs):
        ks = float(np.max(np.abs(self.F_true - F)))
        errs = (qs - self.q_true) / self.q_true * 100
        return ks, errs


# --------------------------------------------------------------------- methods
Z_CACHE = "z_cf_20m.npy"

def cf_normal_draws():
    """Fixed pool of 20M standard normals for the fully analytic CF-Normal
    branch. Generated once (seed SEED+2) and cached on disk; every later call
    reuses the SAME sample instead of drawing fresh normals. This saves the
    regeneration cost and makes repeated evaluations directly comparable
    (common random numbers)."""
    if os.path.exists(Z_CACHE):
        return np.load(Z_CACHE)
    Z = np.random.default_rng(SEED + 2).standard_normal(20_000_000)
    np.save(Z_CACHE, Z)
    return Z


def semi_edgeworth(k, good_idx, bad_idx, metric,chunk_size):
    """Good clusters: Edgeworth-corrected Normal (analytic CF).
    Bad clusters: direct Monte Carlo, M = 5000 * (#bad variables)."""
    t0 = time.perf_counter()
    kG, kb = k[good_idx], k[bad_idx]
    sig_G = math.sqrt((kG ** 2).sum())
    gam_G = SKEW * float((kG ** 3).sum() / (kG ** 2).sum() ** 1.5)
    rng = np.random.default_rng(SEED + 2)
   
    if len(kb):
        M = max(M_GOOD, M_PER_VAR * len(kb))   # new rule: M = max(M1, M2)
        sample = np.empty(M)
        for s in range(0, M, chunk_size):
            m = min(chunk_size, M - s)
            Z = rng.standard_normal(m)
            sample[s:s + m] = sig_G * (Z + gam_G / 6 * (Z ** 2 - 1)) + \
                (rng.exponential(1.0, (m, len(kb))) - 1.0) @ kb
        M_str = f"{M:,}"
    else:   # fully analytic: M = max(M1, 0) = 1e6 draws from the cached pool
        Z = cf_normal_draws()[:M_GOOD]
        sample = sig_G * (Z + gam_G / 6 * (Z ** 2 - 1))
        M_str = f"{M_GOOD:,} (fully analytic)"
    ks, errs = metric.from_sample(sample)
    wall = time.perf_counter() - t0
    return dict(vsim=len(kb), M=M_str, wall=wall, ks=ks, errs=errs,
                sig_G=sig_G, gam_G=gam_G, sample=sample)


def muller_inspired(k, metric,chunk_size):
    """Simulate the top-10% largest-k variables; plain Normal for the rest."""
    t0 = time.perf_counter()
    n = len(k)
    n_top = n // 10
    top = np.argsort(k)[-n_top:]
    kT = k[top]
    sig_R = math.sqrt((k[np.setdiff1d(np.arange(n), top)] ** 2).sum())
    M = M_PER_VAR * n_top
    rng = np.random.default_rng(SEED + 3)
    sample = np.empty(M)
    for s in range(0, M, chunk_size):
        m = min(chunk_size, M - s)
        sample[s:s + m] = sig_R * rng.standard_normal(m) + \
            (rng.exponential(1.0, (m, n_top)) - 1.0) @ kT
    ks, errs = metric.from_sample(sample)
    wall = time.perf_counter() - t0
    return dict(vsim=n_top, M=f"{M:,}", wall=wall, ks=ks, errs=errs)


def fft_cdf(k, N):
    """Invert the product characteristic function of S on [-a, a], a = 4 sd.
    log phi(w) = -i w sum(k) - sum log(1 - i k w)   (centered Exp(1) base)."""
    a = 4 * math.sqrt((k ** 2).sum())
    h = 2 * a / N
    m = np.arange(N)
    omega = 2 * np.pi * (m - N // 2) / (N * h)
    logphi = np.empty(N, dtype=np.complex128)
    B = 2048
    for s in range(0, N, B):
        om = omega[s:s + B]
        logphi[s:s + B] = -1j * om * k.sum() - np.log(
            1.0 - 1j * np.outer(om, k)).sum(axis=1)
    phi = np.exp(logphi) * np.where(m % 2 == 0, 1.0, -1.0)   # fftshift phase
    f = (1 / h) * np.fft.ifft(phi).real
    f = np.where(m % 2 == 0, f, -f)[::-1]   # undo phase; ifft mirrors the grid
    f = np.maximum(f, 0.0)
    x = -a + np.arange(N) * h
    F = np.concatenate([[0.0], np.cumsum(0.5 * (f[1:] + f[:-1])) * h])
    F /= F[-1]
    return x, F


def fft_method(k, N, metric):
    t0 = time.perf_counter()
    xg, Fg = fft_cdf(k, N)
    ks, errs = metric.from_cdf(lambda g: np.interp(g, xg, Fg),
                               lambda p: np.interp(p, Fg, xg))
    wall = time.perf_counter() - t0
    return dict(vsim=0, M=f"— ({N * len(k):.2e} CF evals)", wall=wall,
                ks=ks, errs=errs)


def overall_normal(k, metric):
    t0 = time.perf_counter()
    nd = NormalDist(0.0, math.sqrt((k ** 2).sum()))
    ks, errs = metric.from_cdf(lambda g: np.array([nd.cdf(v) for v in g]),
                               lambda p: nd.inv_cdf(p))
    return dict(vsim=0, M="—", wall=time.perf_counter() - t0, ks=ks, errs=errs)


# ------------------------------------------------------------------- figures
_fig_rng = np.random.default_rng(7)

def kde(sample, grid):
    """Gaussian KDE on a 300k subsample, evaluated in blocks of 50 grid points.
    Working matrix: 50 x 300k (~120 MB) instead of 900 x 300k (~2.2 GB,
    ~4-6 GB peak with temporaries) -- avoids swap on <= 8 GB machines.
    Numerically identical to the unblocked version."""
    sub = sample[_fig_rng.integers(0, len(sample), min(300_000, len(sample)))]
    h = 1.06 * sub.std() * len(sub) ** (-1 / 5)
    norm = len(sub) * h * np.sqrt(2 * np.pi)
    out = np.empty(len(grid))
    for s in range(0, len(grid), 50):
        d = (grid[s:s + 50, None] - sub[None, :]) / h
        out[s:s + 50] = np.exp(-0.5 * d ** 2).sum(axis=1) / norm
    return out

def make_figure(tag, K, k, true_sum, semi_sample, semi_M):
    """Two-panel density comparison: linear PDF + right tail on log scale.
    Curves: True (full MC), Semi-approx, Overall Normal."""
    if not HAVE_MPL:
        print("  (matplotlib not installed; skipping figure)")
        return
    nd = NormalDist(0.0, math.sqrt((k ** 2).sum()))   # Var(Exp(1)) = 1
    lo = np.quantile(true_sum, 1e-6)
    hi = np.quantile(true_sum, 1 - 1e-6)
    g1 = np.linspace(lo * 1.15, hi * 1.15, 900)
    g2 = np.linspace(max(0, lo), np.quantile(true_sum, 1 - 1e-5) * 1.2, 900)
    f_t1, f_s1 = kde(true_sum, g1), kde(semi_sample, g1)
    f_t2, f_s2 = kde(true_sum, g2), kde(semi_sample, g2)
    f_n1 = np.array([nd.pdf(x) for x in g1])
    f_n2 = np.array([nd.pdf(x) for x in g2])

    fig, ax = plt.subplots(1, 2, figsize=(10.6, 3.6), dpi=130)
    ax[0].plot(g1, f_t1, "k-", lw=1.6, label="True")
    ax[0].plot(g1, f_s1, color="0.25", ls="--", lw=1.6, label="Semi-approx")
    ax[0].plot(g1, f_n1, color="tab:red", ls=":", lw=1.8, label="Overall Normal")
    ax[0].set_title("PDF (linear scale)")
    ax[0].set_xlabel("x"); ax[0].set_ylabel("Density")
    ax[0].legend(framealpha=0.9); ax[0].grid(alpha=0.25)

    ax[1].semilogy(g2, f_t2, "k-", lw=1.6, label="True")
    ax[1].semilogy(g2, f_s2, color="0.25", ls="--", lw=1.6, label="Semi-approx")
    ax[1].semilogy(g2, f_n2, color="tab:red", ls=":", lw=1.8, label="Overall Normal")
    ax[1].set_title("Right tail (log scale)")
    ax[1].set_xlabel("x"); ax[1].set_ylabel("Density (log)")
    ax[1].legend(framealpha=0.9); ax[1].grid(alpha=0.25, which="both")

    fig.suptitle(f"Experiment {tag}, n={len(k)}, K={K}, centered Exp(1), "
                 f"$\\theta$=0.6 (True: M={len(true_sum):,}, Semi: {semi_M})",
                 fontsize=11)
    fig.tight_layout(rect=[0, 0, 1, 0.93])
    out = f"pdf_{tag}_k{K}.png"
    fig.savefig(out, bbox_inches="tight")
    plt.close(fig)
    print(f"  saved {out}")


# ------------------------------------------------------------------------ run
def run_experiment(tag, K_list=(4,)):
    k = make_k(tag)
    n = len(k)
    print(f"\n===== Experiment {tag}: n = {n} =====")
    true_sum = true_mc(tag, k)
    metric = Metric(true_sum)
    print(f"reference: M = {metric.M:,}, sd = {true_sum.std():.1f}, "
          f"q95/99/99.9 = {np.round(metric.q_true, 1)}")

    out = dict(tag=tag, n=n, M_true=metric.M)
    for K in K_list:
        print(f"\n-- K = {K} --")
        labels = kmeans_sqrt(k, K)
        clusters, good_idx, bad_idx = lyapunov_split(k, labels, K)
        for c in clusters:
            print(f"  C{c['cluster']}: n={c['count']:>5}  "
                  f"k in [{c['kmin']:.1f},{c['kmax']:.1f}]  "
                  f"L={c['L']:.4f}  {c['decision']}")

        res = {}
        r = semi_edgeworth(k, good_idx, bad_idx, metric,chunk_size)
        res["Semi-Edgeworth"] = r
        print(f"  Semi: {sum(1 for c in clusters if c['decision'] == 'Good')} Good / "
              f"{len(bad_idx)} Bad vars, M={r['M']}, KS={r['ks']:.4f}, "
              f"errs={np.round(r['errs'], 2)}, t={r['wall']:.1f}s")

        r = muller_inspired(k, metric,chunk_size)
        res["Muller-inspired (top 10%)"] = r
        print(f"  Muller: sim={r['vsim']}, M={r['M']}, KS={r['ks']:.4f}, "
              f"errs={np.round(r['errs'], 2)}, t={r['wall']:.1f}s")

        for N in (2 ** 14, 2 ** 17):
            r = fft_method(k, N, metric)
            res[f"FFT (N=2^{int(math.log2(N))}, a=4sd)"] = r
            print(f"  FFT N=2^{int(math.log2(N))}: KS={r['ks']:.4f}, "
                  f"errs={np.round(r['errs'], 2)}, t={r['wall']:.1f}s")

        r = overall_normal(k, metric)
        res["Overall Normal"] = r
        print(f"  Normal: KS={r['ks']:.4f}, errs={np.round(r['errs'], 2)}")

        if MAKE_FIGURES:
            make_figure(tag, K, k, true_sum,
                        res["Semi-Edgeworth"]["sample"], res["Semi-Edgeworth"]["M"])

        out[f"K{K}"] = dict(
            clusters=clusters,
            n_good_clusters=sum(1 for c in clusters if c["decision"] == "Good"),
            n_bad_clusters=sum(1 for c in clusters if c["decision"] == "Bad"),
            n_bad_vars=int(len(bad_idx)),
            results={m: dict(vsim=v["vsim"], M=v["M"], wall=f"{v['wall']:.1f} s",
                             ks=v["ks"], errs=[float(e) for e in v["errs"]])
                     for m, v in res.items()})

    json.dump(out, open(f"results_{tag}.json", "w"), indent=1)
    print(f"\nsaved results_{tag}.json")


if __name__ == "__main__":
    tags = [sys.argv[1].upper()] if len(sys.argv) > 1 else ["A", "B"]
    Ks = [int(sys.argv[2])] if len(sys.argv) > 2 else [4]
    for t in tags:
        run_experiment(t, Ks)
        
        
#import json
#code see results: d = json.load(open("results_A.json"))
#d["K4"]["results"]["Semi-Edgeworth"]   # 实验 A 中 Semi 那一行的全部数值        
