ベンチマーク
実行環境
- ホストOS: Windows 11 Home 24H2
- WSLバージョン: WSL2
- Linuxディストリビューション: Ubuntu 22.04
- CPU: AMD Ryzen 5 7520U
- メモリ: 8GB (WSLが使えるのはもっと少ないはず)
oj-verify run {path}
を 10 回ずつ実行しています。
実行結果
Many A + B
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| read all | 2.214/1.725/3.513 | 149.77/149.02/150.48 |
| read 16 | 4.241/4.027/4.892 | 21.35/21.01/21.49 |
| read 256 | 1.822/1.755/2.112 | 21.21/20.52/21.66 |
| read 4096 | 1.641/1.569/1.770 | 23.16/22.37/23.68 |
| read 65536 | 1.600/1.545/1.707 | 23.64/23.20/25.03 |
| read 1048576 | 1.647/1.527/2.001 | 23.25/22.72/23.64 |
| Mojo with Python input | 13.956/12.745/15.648 | 27.97/27.14/28.34 |
| Python with input | 2.815/2.499/4.165 | 10.10/10.06/10.14 |
| Python with sys.stdin.readline | 1.017/0.822/1.371 | 10.22/10.18/10.28 |
| C++ | 0.350/0.335/0.418 | 3.59/3.54/3.62 |
Double-Ended Priority Queue
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| IntervalHeap | 0.712/0.687/0.740 | 35.27/34.42/36.02 |
| BinaryTrie | 3.216/2.958/3.792 | 320.89/320.19/322.35 |
| SegTree + Compress | 1.280/1.164/1.513 | 70.99/70.18/71.69 |
Point Add Range Sum
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| FenwickTree | 1.146/0.955/1.797 | 31.68/31.32/32.80 |
| SegTree | 1.096/1.013/1.257 | 35.76/35.38/37.10 |
| SegTree with Parameter | 1.073/0.972/1.472 | 35.57/35.05/35.89 |
| LazySegTree | 2.785/2.383/4.210 | 43.93/43.47/45.34 |
Point Set Range Composite
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| SegTree | 1.972/1.758/2.387 | 47.70/47.45/47.90 |
| SegTree with Parameter | 2.237/1.787/3.576 | 47.12/45.97/47.64 |
Range Affine Point Get
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| DualSegTree | 3.478/2.936/5.358 | 47.10/46.08/47.71 |
| LazySegTree | 4.649/3.556/6.838 | 51.07/46.93/53.25 |
Static Range Sum
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| Cumulative Sum | 1.584/0.955/3.026 | 30.80/30.32/31.69 |
| FenwickTree | 1.007/0.951/1.165 | 31.36/30.38/33.06 |
| SegTree | 1.048/0.946/1.215 | 34.93/34.40/35.64 |
Predecessor Problem
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| AVLTree | 9.649/8.757/11.131 | 662.65/661.90/663.60 |
| AVLTree with preallocate | 7.821/7.507/8.291 | 438.89/438.32/439.66 |
| BinaryTrie | 7.108/6.595/7.820 | 662.87/662.01/663.35 |
| BinaryTrie with preallocate | 6.070/5.687/6.717 | 518.36/517.49/518.90 |
| WordSizeTree | 1.663/1.466/2.349 | 50.02/49.86/50.35 |
| SegTree | 3.068/2.356/3.944 | 379.71/379.44/380.88 |
Ordered Set
| 機能 | 実行時間 avg/min/max (sec) | メモリ avg/min/max (MB) |
|---|---|---|
| AVLTree | 1.976/1.872/2.384 | 64.41/63.74/66.03 |
| AVLTree with preallocate | 1.729/1.599/1.927 | 55.72/55.08/56.54 |
| BinaryTrie | 2.404/2.191/2.616 | 273.63/272.33/274.62 |
| BinaryTrie with preallocate | 1.895/1.705/2.227 | 215.07/214.12/216.10 |
| SegTree + Compress | 1.409/1.258/1.685 | 72.02/71.43/72.92 |