diff options
| -rw-r--r-- | README.md | 10 |
1 files changed, 10 insertions, 0 deletions
@@ -13,3 +13,13 @@ If you're wondering where the name came from, this is the C port of [SD](https:/ ## Performance CD is designed to be extremely efficient in order to support a very large number of flash cards and should be able to handle millions of cards with ease. If `N` is the number of cards, initializing the program requires `O(N)` time and `O(N)` memory. Selecting a random card and adjusting its weight requires `O(log N)` time. Internally CD uses [segment trees](https://en.wikipedia.org/wiki/Segment_tree) to achieve this time complexity. + +Some benchmark results using 10 card updates: +``` +Benchmark 1: ./cd < test + Time (mean ± σ): 57.4 ms ± 4.5 ms [User: 6.9 ms, System: 2.4 ms] + Range (min … max): 51.9 ms … 70.9 ms 41 runs +Benchmark 2: ./sd < test + Time (mean ± σ): 92.7 ms ± 6.8 ms [User: 8.4 ms, System: 4.5 ms] + Range (min … max): 79.4 ms … 108.9 ms 33 runs +``` |