指针/数组实现线段树性能比较

自上次用指针写网络流之后,就很好奇指针写线段树性能怎么样。

以POJ – 3468为例。

数组版

指针版

性能比较

 指针数组
时间(ms)34382485
空间(MB)10.75.2

小结

惊喜不惊喜?意外不意外?其实仔细想想好想也没什么毛病。

首先空间性能上是很好解释的,因为数组是堆式存储的,所以每个节点不需要记录左儿子和右儿子在哪里,但是指针就需要记录这两个值——要维护的值从两个(value, lazy-tag)变成了四个(value, lazy-tag, left-son, right-son),那么空间自然翻倍。

时间性能上来说以我现在的知识还不能给出合理的解释,我有两个猜想:

  • 计算机在连续的内存空间寻址速度比非连续空间快
  • 用数组只申请了一次空间,但是用指针需要申请$n \log n$次空间,拖慢了速度

先留个坑吧。有读者知道的话可以发邮件给我😊,非常感谢。

说点什么

avatar
50
  Subscribe  
提醒