Skip to content

Latest commit

 

History

History
79 lines (54 loc) · 2.51 KB

README.md

File metadata and controls

79 lines (54 loc) · 2.51 KB
Raw

单向链表的逆序输出

plan

任务目标

  1. 逆序输出
  2. 高效

任务分析

可以改变原有数据结构的情况：

  1. 修改指针，将所有指向反向处理(好处是简单，坏处是破坏了原有数据结构)

不可以改变原有数据结构的情况：

  1. 递归(最简单的设计，牺牲的是效率)
  2. 遍历，将节点的值单独存放(典型的空间换时间的用法)

课题

将上面几种方案都进行基准测试，记录数据进行对比分析

课题的解决方案

  • 实现上面的几种思路，并基于基准测试获取对比数据
  • 测试的数据的多少和类型作为一个测试点
  • 使用go和tdd来实现(正好在熟悉这块)
  • 可用图表的方式来展示最后的测试结果

Do

确定行动措施

  1. 以tdd的方式完成几种实现方式
  2. 将不同的数据类型和不同量级的作为测试条件,完善基准测试
  3. 使用go-echarts来进行数据可视化(现在可以直接生成可视化图，后续考虑go-echarts)
# 用下面命令来生成性能分析文件
go test -bench="." -benchmem -cpuprofile profile.out

# 用下面的命令来在web生成可视化图
go tool pprof -http=172.17.0.2:8000 profile.out

Check

  • 都是利用go原生的包去实现的，包括单链表都是用list代替的
  • 整个测试还可以更加简化:自己组装数据类型和接口
  • 测试的结果看 "空间换时间" > "修改链表方向" > "递归"
  • 分析：
    • 空间换时间：只遍历一次链表，值不是很大的情况下，最优;不然需要考虑空间
    • 修改链表方向：遍历两次，修改了原始数据结构，适用场景有限
    • 递归：主要是调用栈深度不确定，实际结果也是最差的
  • 本次分析重构的非常少，印象因子非常多

Adjust

  • tdd测试使用了常用的手段：
    • 基本的测试
    • 辅助函数
    • 测试项集合
    • 基准测试
    • 性能分析
  • 不足的地方是没有使用第三方生成可视化图表
  • 另一个不足的地方是数据结构不是自定义的，而是使用go原生的
  • 如果使用自定义数据结构，结果应该会更好一点

总结

2019.10.16

考虑到现在硬件比较充裕，可靠优先考虑使用空间换性能的方案， 只有在链表节点值非常大，而空间资源不足的情况下，可以考虑创建映射链表， 如果不关心原始数据结构，可以直接修改原始数据结构。

总之，除非链表非常短，不然不推荐使用递归的方式来解决。