ベンチマーク
実行環境
- ホストOS: Windows 11 Home 24H2
- WSLバージョン: WSL2
- Linuxディストリビューション: Ubuntu 22.04
- CPU: AMD Ryzen 5 7520U
- メモリ: 8GB (WSLが使えるのはもっと少ないはず)
を 10 回ずつ実行しています。
実行結果
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| read all |
2.657/1.713/3.926 |
92.55/91.34/93.78 |
| read 16 |
6.086/4.398/12.508 |
13.32/12.79/13.81 |
| read 256 |
2.277/1.926/2.938 |
13.02/11.72/13.51 |
| read 4096 |
1.802/1.732/2.141 |
15.44/14.98/15.69 |
| read 65536 |
1.861/1.759/1.998 |
15.43/14.90/15.73 |
| read 1048576 |
1.942/1.769/2.271 |
15.44/15.14/15.73 |
| Python |
0.998/0.933/1.128 |
10.11/10.06/10.19 |
| C++ |
0.396/0.336/0.539 |
3.51/3.45/3.56 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| IntervalHeap |
0.758/0.702/0.876 |
27.86/27.56/28.13 |
| BinaryTrie |
4.547/3.053/12.458 |
313.01/312.32/315.11 |
| SegTree + Compress |
1.230/1.091/1.683 |
64.45/63.99/64.95 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| SegTree |
2.142/1.928/2.847 |
40.08/39.42/42.08 |
| SegTree with Parameter |
2.126/1.904/2.548 |
40.08/39.62/42.08 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| DualSegTree |
2.694/2.571/2.956 |
39.61/38.76/39.85 |
| LazySegTree |
3.533/3.343/4.574 |
43.88/43.54/44.26 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| Cumulative Sum |
0.947/0.920/0.995 |
23.69/23.45/23.96 |
| FenwickTree |
0.976/0.952/1.024 |
23.88/23.38/25.70 |
| SegTree |
1.027/0.986/1.108 |
27.77/27.02/28.06 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| AVLTree |
13.637/12.796/15.604 |
618.69/585.49/624.92 |
| BinaryTrie |
13.292/12.075/14.181 |
585.55/584.56/586.16 |
| WordSizeTree |
2.020/1.958/2.182 |
42.24/41.53/44.04 |
| SegTree |
2.938/2.447/4.144 |
371.99/371.42/372.37 |
| 機能 |
実行時間 avg/min/max (sec) |
メモリ avg/min/max (MB) |
| AVLTree |
2.347/2.146/2.704 |
68.72/68.07/70.75 |
| BinaryTrie |
2.645/2.394/3.357 |
174.69/173.61/175.78 |
| SegTree + Compress |
1.581/1.213/3.133 |
66.14/65.13/66.56 |