sequence_timing.py

"""Measured running time of the whole-sequence computation vs (m+n) and vs gamma."""
import time, json, sys, numpy as np
sys.setrecursionlimit(100000)
from cc_flow import sequence, rand_hg

def run(n,m,rng,reps=3):
    ts=[];fl=[];op=[];gm=[]
    for _ in range(reps):
        E,w=rand_hg(rng,n,m); st={"flows":0,"ops":0}
        t0=time.perf_counter(); seq=sequence(n,E,w,st); el=time.perf_counter()-t0
        ts.append(el); fl.append(st["flows"]); op.append(st["ops"]); gm.append(len(seq))
    return dict(n=n,m=m,mn=m+n,time=float(np.mean(ts)),flows=float(np.mean(fl)),
                ops=float(np.mean(op)),gamma=float(np.mean(gm)))

def fit(x,y): return float(np.polyfit(np.log(x),np.log(y),1)[0])

if __name__=="__main__":
    rng=np.random.default_rng(11); R={}
    # (A) scale (m+n) with m ~ n
    rows=[]
    for n in (20,40,80,160,320,640):
        rows.append(run(n,2*n,rng)); r=rows[-1]
        print("   n=%4d m=%4d  m+n=%5d  gamma=%5.1f  flows=%6.1f  time=%8.3fs  ops=%.3g"
              %(r["n"],r["m"],r["mn"],r["gamma"],r["flows"],r["time"],r["ops"]),flush=True)
    mn=[r["mn"] for r in rows]
    R["size_sweep"]={"rows":rows,
        "time_exponent_in_m_plus_n":round(fit(mn,[r["time"] for r in rows]),3),
        "ops_exponent_in_m_plus_n":round(fit(mn,[r["ops"] for r in rows]),3),
        "time_per_gamma_exponent":round(fit(mn,[r["time"]/r["gamma"] for r in rows]),3),
        "ops_per_gamma_exponent":round(fit(mn,[r["ops"]/r["gamma"] for r in rows]),3),
        "corollary1_exponent":2}
    print("  [A] time ~ (m+n)^%.3f | ops ~ (m+n)^%.3f | time/gamma ~ (m+n)^%.3f | ops/gamma ~ (m+n)^%.3f  (Corollary 1: 2)"
          %(R["size_sweep"]["time_exponent_in_m_plus_n"],R["size_sweep"]["ops_exponent_in_m_plus_n"],
            R["size_sweep"]["time_per_gamma_exponent"],R["size_sweep"]["ops_per_gamma_exponent"]),flush=True)
    # (B) linearity in gamma at fixed size: vary edge density to move gamma
    rows2=[]
    for m in (10,20,40,80,160,320):
        rows2.append(run(200,m,rng)); r=rows2[-1]
        print("   n=200 m=%4d  gamma=%5.1f  flows=%6.1f  time=%8.3fs"%(r["m"],r["gamma"],r["flows"],r["time"]),flush=True)
    R["gamma_sweep"]={"rows":rows2,
        "flows_per_gamma":[round(r["flows"]/max(r["gamma"],1),3) for r in rows2],
        "time_exponent_in_gamma":round(fit([r["gamma"] for r in rows2],[r["time"] for r in rows2]),3),
        "flows_exponent_in_gamma":round(fit([r["gamma"] for r in rows2],[r["flows"] for r in rows2]),3),
        "corollary1_exponent":1}
    print("  [B] time ~ gamma^%.3f | mincut calls ~ gamma^%.3f | calls/gamma %s  (Corollary 1: 1)"
          %(R["gamma_sweep"]["time_exponent_in_gamma"],R["gamma_sweep"]["flows_exponent_in_gamma"],
            R["gamma_sweep"]["flows_per_gamma"]),flush=True)
    # (C) reach beyond enumeration
    E,w=rand_hg(rng,1200,2400); st={"flows":0,"ops":0}
    t0=time.perf_counter(); seq=sequence(1200,E,w,st); el=time.perf_counter()-t0
    R["reach"]={"n":1200,"m":2400,"gamma":len(seq),"flows":st["flows"],"time_s":round(el,2),
                "brute_force_masks":"2^1200"}
    print("  [C] n=1200 m=2400 solved in %.2fs with %d min-cuts, gamma=%d (enumeration would need 2^1200 masks)"
          %(el,st["flows"],len(seq)),flush=True)
    json.dump(R,open("cc_scale.json","w"),indent=1); print("DONE")