Skip to content

Instantly share code, notes, and snippets.

@z0z0r4

z0z0r4/draw_pic.py

Created April 21, 2026 04:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save z0z0r4/a2c24a9cbd06cd97a9e3534a61021713 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save z0z0r4/a2c24a9cbd06cd97a9e3534a61021713 to your computer and use it in GitHub Desktop.
Download ZIP
Disjoint-Set Performance Test
Raw
draw_pic.py
import matplotlib.pyplot as plt
import numpy as np
from mpl_toolkits.mplot3d import Axes3D
# 准备数据
data = [
# N, M, Speedup
[25, 10, 3.45], [25, 100, 1.38], [25, 1000, 0.98], [25, 100000, 2.11], [25, 1000000, 2.09], [25, 10000000, 2.14],
[50, 10, 4.71], [50, 100, 1.36], [50, 1000, 2.25], [50, 100000, 2.30], [50, 1000000, 2.30], [50, 10000000, 1.97],
[100, 10, 4.62], [100, 100, 1.22], [100, 1000, 2.05], [100, 100000, 2.59], [100, 1000000, 2.96], [100, 10000000, 2.72],
[1000, 10, 4.64], [1000, 100, 1.34], [1000, 1000, 0.86], [1000, 100000, 19.55], [1000, 1000000, 22.13], [1000, 10000000, 16.66],
[10000, 10, 4.11], [10000, 100, 0.75], [10000, 1000, 0.56], [10000, 100000, 175.19], [10000, 1000000, 215.01], [10000, 10000000, 191.96],
[100000, 10, 5.60], [100000, 100, 1.28], [100000, 1000, 0.82], [100000, 100000, 1.00], [100000, 1000000, 1482.66]
]
data = np.array(data)
n_size = data[:, 0]
m_ops = data[:, 1]
speedup = data[:, 2]
# 创建画布
fig = plt.figure(figsize=(12, 8))
ax = fig.add_subplot(111, projection='3d')
# 使用对数坐标处理 X 和 Y 轴，因为跨度太大
# 如果想看原始间距，可以直接使用 n_size 和 m_ops
x = np.log10(n_size)
y = np.log10(m_ops)
z = speedup
# 绘制三维散点图
# c 代表颜色深浅（根据加速比变化），cmap 是颜色映射表
scatter = ax.scatter(x, y, z, c=z, cmap='viridis', s=60, edgecolors='w', alpha=0.8)
# 绘制三角网格曲面（有助于观察趋势）
ax.plot_trisurf(x, y, z, cmap='viridis', alpha=0.3)
# 设置轴标签
ax.set_xlabel('Log10(N Size)')
ax.set_ylabel('Log10(M Ops)')
ax.set_zlabel('Speedup (N/O)')
ax.set_title('Performance Benchmark: Speedup Analysis')
# 添加颜色条
cbar = fig.colorbar(scatter, ax=ax, shrink=0.5, aspect=10)
cbar.set_label('Speedup Magnitude')
# 自定义坐标轴刻度显示，让它看起来还是原始数值的量级
ax.set_xticks(np.unique(x))
ax.set_xticklabels([f'$10^{{{int(i)}}}$' if i.is_integer() else f'{10**i:.0f}' for i in np.unique(x)])
ax.set_yticks(np.unique(y))
ax.set_yticklabels([f'$10^{{{int(i)}}}$' if i.is_integer() else f'{10**i:.0f}' for i in np.unique(y)])
plt.show()
Raw
main.cpp
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <iomanip>
#include <string>
using namespace std;
class NaiveDisjointSet
{
vector<int> data;
public:
NaiveDisjointSet(int n) : data(n, -1) {}
void make_set(int i) { data[i] = i; }
int find_set(int i)
{
while (i != data[i])
i = data[i];
return i;
}
void connect(int a, int b)
{
int rootA = find_set(a);
int rootB = find_set(b);
if (rootA != rootB)
data[rootB] = rootA;
}
bool isconnected(int a, int b)
{
return find_set(a) == find_set(b);
}
};
class OptimizedDisjointSet
{
vector<int> data;
vector<int> rank;
public:
OptimizedDisjointSet(int n) : data(n, -1), rank(n, 0) {}
void make_set(int i)
{
if (i >= 0 && i < data.size())
data[i] = i;
}
int find_set(int i)
{
if (i < 0 || i >= data.size() || data[i] == -1)
throw "Error";
int root = i;
while (root != data[root])
{
root = data[root];
}
while (i != root)
{
int next_node = data[i];
data[i] = root;
i = next_node;
}
return root;
}
bool isconnected(int a, int b)
{
return find_set(a) == find_set(b);
}
void connect(int a, int b)
{
int rootA = find_set(a);
int rootB = find_set(b);
if (rootA != rootB)
{
if (rank[rootA] > rank[rootB])
{
data[rootB] = rootA;
}
else if (rank[rootA] < rank[rootB])
{
data[rootA] = rootB;
}
else
{
data[rootB] = rootA;
rank[rootA]++;
}
}
}
};
struct Result
{
double naive_ms;
double optimized_ms;
string winner;
};
Result run_single_benchmark(int N, int M)
{
mt19937 rng(42);
uniform_int_distribution<int> dist(0, N - 1);
double naive_time;
{
NaiveDisjointSet ndjs(N);
for (int i = 0; i < N; i++)
ndjs.make_set(i);
auto start = chrono::high_resolution_clock::now();
for (int i = 0; i < M; i++)
{
int a = dist(rng), b = dist(rng);
if (i % 2 == 0)
ndjs.connect(a, b);
else
ndjs.isconnected(a, b);
}
auto end = chrono::high_resolution_clock::now();
naive_time = chrono::duration<double, milli>(end - start).count();
}
double opt_time;
{
OptimizedDisjointSet odjs(N);
for (int i = 0; i < N; i++)
odjs.make_set(i);
auto start = chrono::high_resolution_clock::now();
for (int i = 0; i < M; i++)
{
int a = dist(rng), b = dist(rng);
if (i % 2 == 0)
odjs.connect(a, b);
else
odjs.isconnected(a, b);
}
auto end = chrono::high_resolution_clock::now();
opt_time = chrono::duration<double, milli>(end - start).count();
}
return {naive_time, opt_time, (naive_time < opt_time ? "Naive" : "Optimized")};
}
void print_matrix()
{
// 定义测试矩阵：节点规模 x 操作次数
vector<int> n_sizes = {25, 50, 100, 1000, 10000, 100000, 1000000};
vector<int> m_ops = {10, 100, 1000, 100000, 1000000, 10000000};
cout << fixed << setprecision(2);
cout << "==========================================================================" << endl;
cout << " N Size | M Ops | Naive (ms) | Optimized (ms) | Speedup (N/O) | Winner " << endl;
cout << "==========================================================================" << endl;
for (int n : n_sizes)
{
for (int m : m_ops)
{
Result res = run_single_benchmark(n, m);
double speedup = res.naive_ms / res.optimized_ms;
cout << setw(9) << n << " | "
<< setw(8) << m << " | "
<< setw(10) << res.naive_ms << " | "
<< setw(14) << res.optimized_ms << " | "
<< setw(13) << speedup << "x | "
<< res.winner << endl;
}
cout << "--------------------------------------------------------------------------" << endl;
}
}
int main()
{
print_matrix();
return 0;
}
@z0z0r4
Copy link
Copy Markdown
Author

z0z0r4 commented Apr 21, 2026

毫无疑问测试和绘图脚本都是 AI 生成的

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment