如何用JMH验证TreeSet增删O(log n)复杂度及基准测试相关疑问

测试流程怎么选？ #

按原始消息顺序处理请求绝对是更贴近真实场景的做法——预加载所有订单再删完全不符合实际订单簿的运行逻辑，真实场景里订单都是逐步插、随时可能被删的。

如果要对比删除的开销，你可以做两组测试：

• 一组按原始顺序执行所有请求（插+删）
• 另一组只执行所有插入请求
  然后用两组的总耗时差来估算删除操作的总开销。但要是想精准测单次删除的耗时，更靠谱的是在每条删除请求执行时，单独埋点统计TreeSet.remove()的执行时间，别让插入的耗时干扰结果。

N到底指啥？ #

得看你的测试目标：

• 要是想验证单次删除操作的时间复杂度，那N必须是执行删除时TreeSet的当前元素数量——毕竟TreeSet的O(log n)复杂度里，n就是集合当时的大小。你可以把删除操作按当时集合的大小分组（比如集合大小在1k-2k、2k-3k区间的删除），统计每组的平均耗时，看是不是符合log n的增长趋势。
• 要是只关注批量删除的整体耗时和删除数量的关系，那N可以取删除操作的总数量，但这种方式只能看整体趋势，没法精准对应单次删除的O(log n)特性。

额外测试细节 #

• 控制变量很重要：插入的订单对象要保证一致（别因为对象的比较逻辑不一样影响耗时），JMH的预热要拉满（默认会做，但可以确认@Warmup参数），多跑几次取平均，结果才靠谱。
• 插入操作的验证可以单独做：生成不同大小的数据集，统计插N个元素的总耗时和单次平均耗时，总耗时应该接近O(n log n)，这就能验证插入的O(log n)特性。

内容的提问来源于stack exchange，提问作者CollinsPED