均衡型选手 – TQPagedList 与 TList 和 RBTree 的性能PK

• C++ Builder、Delphi、QDAC、杂谈 • 评论关闭 • •浏览 3,471 次

QDAC 新实现了一个 TQPagedList 来代替 TList 来处理需要较大量的数据增删的情况。通过内存数据分页的方式，降低数据移动的数量，从而达到优化速度的目的。

下面是一些性能的实测结果（Release模式）：

  • 插入测试
    • 将10万条数据插入位置0（最糟情况）
      • TList: 2736.3 ms
      • TQPagedList:107.3 ms
      • 性能差距：2629 ms
      • 性能变化：提升约 25.5X
    • 将10万条记录采用追加到末尾的方式加入（最好情况）
      • TList: 15 ms
      • TQPagedList: 15 ms
      • 性能差距：0 ms
      • 性能变化：基本无变化
    • 插入时排序
      • TList: 1358 ms
      • TQPagedList: 207 ms
      • TQRBTree （红黑树）:  35 ms
      • 性能差距: 比 TList 快 1151 ms，比 TQRBTree 慢 172 ms
      • 性能变化: 比红黑树要慢约 5.91 倍，比 TList 要快了 6.56 倍
  • 随机访问性能
    • 10万次随机位置访问
      • TList: 0.4 ms
      • TQPagedList: 5.6 ms
      • 性能差距: 5.2 ms
      • 性能变化：明显降低，TQPagedList 要慢 14 倍

通过上面的例子，我们实际上可以得出结论，TQPagedList的综合性能要明显好于 TList ，数据量越大，其与 TList 的性能差距越明显。

本测试程序位于 Demos\Benchmark\RBTreevsList 目录下，可以实际运行测试。

由上面的测试结果，我们对TList、TQPageList、TQRBTree  的适用场合做一个简单的分解：

  • TList
    • 需要随机访问支持；
    • 对数据追加操作（ Add ）占绝大多数，删除和插入操作较少;
    • 增加元素时不需要自动排序
  • TQPagedList
    • 需要随机访问支持（随机迭代器）；
    • 对数据操作有频繁的删除和插入操作（性能弱于 TQRBTree 而强于 TList ）;
    • 增加元素时自动排序
  • TQRBTree
    • 只需要双向访问支持（双向迭代器，向前或向后）;
    • 对数据操作有频繁的删除和插入操作；
    • 增加的元素时自动排序

下面是重新测试的详细结果（可以明显看出性能变化，时间越短越好）：

测试结果为操作完成用时，每10000条统计一次用时，单位为毫秒

 插入初始位置测试
  TList 总计用时 2737.0 ms :
    26.4	78.8	131.0	183.8	237.7	288.8	347.8	419.1	479.1	544.5	
  TQPagedList 总计用时 107.3 ms :
    9.8	11.4	10.4	11.0	10.8	10.6	11.5	10.1	11.8	9.9	
 插入初始位置测试完成:
    TQPagedList 用时为 1，则 TList 用时为 25.51 倍

 追加数据测试
  TList 总计用时 1.6 ms :
    0.2	0.1	0.2	0.1	0.1	0.2	0.3	0.1	0.2	0.1	
  TQPagedList 总计用时 1.8 ms :
    0.2	0.2	0.2	0.1	0.2	0.2	0.2	0.1	0.2	0.2	
 追加测试完成:
    TQPagedList 用时为 1，则 TList 用时为 0.89 倍

 随机插入测试
  TList 总计用时 1341.6 ms :
    13.6	40.3	66.9	92.5	117.2	144.4	172.0	200.5	233.5	260.7	
  TQPagedList 总计用时 73.7 ms :
    0.8	2.0	2.9	4.2	5.8	8.3	10.4	12.1	13.4	13.8	
 随机插入测试完成:
    TQPagedList 用时为 1，则 TList 用时为 18.20 倍

 即时排序插入测试
  TList 总计用时 1360.9 ms :
    16.4	42.5	70.1	96.0	121.9	148.7	174.2	200.9	228.5	261.7	
  TQPagedList 总计用时 260.5 ms :
    14.6	21.2	24.7	27.2	25.8	26.1	29.1	29.4	30.6	31.8	
  TQRBTree 总计用时 45.1 ms :
    3.2	3.8	4.1	4.5	4.7	4.7	4.9	5.0	4.9	5.3	
  即时排序插入测试完成:
    TQRBTree 用时计为 1，则 TList 用时为 30.18 倍，TQPagedList 用时为 5.78 倍

 删除首个元素测试
  TList 总计用时 2725.1 ms :
    537.9	477.2	417.8	342.9	286.7	238.3	185.9	133.3	78.6	26.5	
  TQPagedList 总计用时 110.2 ms :
    12.1	10.5	11.6	10.9	11.1	11.4	10.5	11.9	10.2	10.0	
 删除首个元素测试完成:
    TQPagedList 用时为 1，则 TList 用时为 24.73 倍

 删除随机元素测试
  TList 总计用时 1334.6 ms :
    261.9	228.2	198.5	169.8	143.6	118.5	92.9	66.1	39.9	15.2	
  TQPagedList 总计用时 110.5 ms :
    12.2	10.5	11.7	10.9	11.1	11.4	10.6	11.9	10.2	10.0	
 删除随机元素测试完成:
    TQPagedList 用时为 1，则 TList 用时为 12.08 倍

 

分享到：