import numpy as np import pandas as pd import matplotlib.pyplot as plt import os from sklearn.linear_model import LinearRegression from sklearn.metrics import r2_score from scipy.optimize import curve_fit # Heap: Binary # # Runtime = Add + Extract-min + Relax-attempts + Relax-success # = VlogV * k1 + VlogV * k2 + E * k3 + \alpha * logV * k4 # (\alpha = relax_success) # # V increases -> Add, Extract-min, Relax-attempts, Relax-success all increases. # Therfore, critical multicollinearlity occurs. # # To solve this problem, run regression per each V. # Then V becomes constant. # # Runtime_V = (V) * (logV(k1 + k2)) + (E) * k3 + (\alpha) * (logV * k4) # # left part: call number, right part: cost per call # call number is not concern in operation cost analysis. # Important thing is that logV in right sides become constant. # # Final equation # Runtime of specific V = V * l + E * k3 + \alpha * m # # Using this equation, we can get l, k3, and m from each regression. # l, m are defined like this. # l = logV * (k1 + k2) # m = logV * k4 # # # Final result # l: cost per each add and extract-min (should scale with log2N) # k3: cost per relax_attempt (should be equal across heaps) # m: cost per decrease-key (should scale with log2N) # # (All base of log in this context is 2 due to binary heap.) # contribution diagram def contribution(): contribution_records = [] for n in nodes: g = df[df['nodes'] == n] g = g[g['relax_success'] > 0] if len(g) < 3: continue # 해당 N의 l, k3, m 가져오기 row = results[results['N'] == n].iloc[0] l_val = row['l'] k3_val = row['k3'] # k3_fixed m_val = row['m'] # 각 항의 평균값 계산 E_mean = g['relax_attempts'].mean() alpha_mean = g['relax_success'].mean() Vl = n * l_val # V·l Ek3 = E_mean * k3_val # E·k3 am = alpha_mean * m_val # α·m total = Vl + Ek3 + am contribution_records.append({ 'N' : n, 'V·l' : Vl, 'E·k3' : Ek3, 'α·m' : am, 'total' : total, 'V·l %' : Vl / total * 100, 'E·k3 %' : Ek3 / total * 100, 'α·m %' : am / total * 100, }) contrib = pd.DataFrame(contribution_records) print("\n=== Contribution of each operations ===") print(contrib[['N','V·l %','E·k3 %','α·m %']].to_string(index=False)) # 시각화 fig, ax = plt.subplots(figsize=(9, 5)) x = np.arange(len(contrib)) w = 0.25 ax.bar(x - w, contrib['V·l %'], width=w, label='V·l (add+extract)') ax.bar(x, contrib['E·k3 %'], width=w, label='E·k3 (relax-attempt)') ax.bar(x + w, contrib['α·m %'], width=w, label='α·m (decrease-key)') ax.set_xticks(x) ax.set_xticklabels(contrib['N'].astype(int)) ax.set_xlabel('N (nodes)') ax.set_ylabel('Contribution (%)') ax.set_title('Runtime contribution by operation') ax.legend() ax.grid(True, alpha=0.4) fig.tight_layout() fig.savefig(f"{save_folder}/contribution_vs_N.png", dpi=300) plt.close(fig) print(f"Saved: contribution_vs_N.png") # l def mean_l(): return results["l"].mean() def plot_l(): fig, ax = plt.subplots(figsize=(7, 5)) ax.plot(nodes, l_bin, marker="o", color="steelblue", label="l") ax.set_xlabel("N (nodes)") ax.set_ylabel("l — add + extract-min unit cost [s]") ax.set_title("l (add + extract-min unit cost) vs N") ax.legend(fontsize=8) ax.grid(True, alpha=0.4) fig.tight_layout() fig.savefig(f"{save_folder}/l_vs_N.png", dpi=300) plt.close(fig) print(f"Saved: {save_folder}/l_vs_N.png") # k3 def regression_k3(): n_arr = np.array(nodes, dtype=float) def exp_conv(n, a, b, c): return a * np.exp(-b * n) + c k3_arr = np.array(k3_bin, dtype=float) popt_ec, _ = curve_fit(exp_conv, n_arr, k3_arr, p0=[float(k3_arr.max() - k3_arr.min()), 1/float(n_arr.mean()), float(k3_arr.min())], maxfev=20000) return popt_ec def plot_k3(): n_arr = np.array(nodes, dtype=float) n_line = np.linspace(min(nodes), max(nodes), 300) def exp_conv(n, a, b, c): return a * np.exp(-b * n) + c k3_arr = np.array(k3_bin, dtype=float) popt_ec, _ = curve_fit(exp_conv, n_arr, k3_arr, p0=[float(k3_arr.max() - k3_arr.min()), 1/float(n_arr.mean()), float(k3_arr.min())], maxfev=20000) pred_ec = exp_conv(n_line, *popt_ec) r2_ec = r2_score(k3_bin, exp_conv(n_arr, *popt_ec)) print("\n=== k3 exp_conv regression ===") print("a * exp(-b*N) + c") print(popt_ec) fig, ax = plt.subplots(figsize=(9, 5)) ax.plot(nodes, k3_bin, marker="o", color="black", zorder=5, label="k3 (data)") ax.plot(n_line, pred_ec, linestyle="--", linewidth=1.5, label=f"exp conv R²={r2_ec:.4f}") ax.set_xlabel("N (nodes)") ax.set_ylabel("k3 — iteration cost per call [s]") ax.set_title("k3 (iteration unit cost) vs N — model comparison") ax.legend(fontsize=8) ax.grid(True, alpha=0.4) fig.tight_layout() fig.savefig(f"{save_folder}/k3_vs_N.png", dpi=300) plt.close(fig) print(f"Saved: {save_folder}/k3_vs_N.png") # m def regression_m(): log_n = np.log2(np.array(nodes)).reshape(-1, 1) reg = LinearRegression().fit(log_n, m_bin) return (reg.coef_[0], reg.intercept_) def plot_m(): log_n = np.log2(np.array(nodes)).reshape(-1, 1) reg = LinearRegression().fit(log_n, m_bin) r2_bin = r2_score(m_bin, reg.predict(log_n)) n_line = np.linspace(min(nodes), max(nodes), 300) log_n_line = np.log2(n_line).reshape(-1, 1) print("\n=== m log regression ===") print("m = a * log_2(N) + b") print(reg.coef_[0], reg.intercept_) fig, ax = plt.subplots(figsize=(7, 5)) ax.plot(nodes, m_bin, marker="o", color="steelblue", label="binary k4") ax.plot(n_line, reg.predict(log_n_line), color="steelblue", linestyle="--", linewidth=1.5, label=f"fit (∝ log₂N) R²={r2_bin:.3f}") ax.set_xlabel("N (nodes)") ax.set_ylabel("m — decrease-key cost per call [s]") ax.set_title("m (decrease-key unit cost) vs N") ax.legend(fontsize=8) ax.grid(True, alpha=0.4) fig.tight_layout() fig.savefig(f"{save_folder}/m_vs_N.png", dpi=300) plt.close(fig) print(f"Saved: {save_folder}/m_vs_N.png") # Initial process csv_file = "results/synthetic_data/raw/20260421_031740.csv" save_folder = f"results/synthetic_data/derived/{os.path.splitext(os.path.basename(csv_file))[0]}/processing_time_analysis" os.makedirs(save_folder, exist_ok=True) df = pd.read_csv(csv_file) nodes = sorted(df["nodes"].unique()) df = df[df["algorithm"] == "binary"] records = [] for n in nodes: g = df[df["nodes"] == n] X = g[["relax_attempts", "relax_success"]].to_numpy() y = g["time"].to_numpy() model = LinearRegression().fit(X, y) r2 = r2_score(y, model.predict(X)) l = model.intercept_ / n k3 = model.coef_[0] m = model.coef_[1] records.append({ "N": n, "log2N": round(np.log2(n), 4), "l": l, "k3": k3, "m": m, "r2": r2, "data": len(g), }) results = pd.DataFrame(records) grouped = results.set_index(["N"]) l_bin = grouped.loc[nodes, "l"].values k3_bin = grouped.loc[nodes, "k3"].values m_bin = grouped.loc[nodes, "m"].values # Directly run if __name__ == "__main__": r = results[["N","log2N","l","k3","m","r2","data"]] print("=== Regression Result ===") print(r.to_string(index=False)) print("\n=== l representative value ===\n", results["l"].describe(), sep="") contribution() plot_l() plot_k3() plot_m()