4 - zhiqiuyuan's blog

今日目标：

早晨

1
- 分析实验结果（输出表格式）
- 实现和跑idea_merge_map
- 设计新增msbfs_merge，因此实验体系：
  1. msbfs
  2. msbfs_merge: 比1(msbfs)加路径合并
  3. idea_sep: 比1(msbfs)加二级rev结构
  4. idea_sep_map: 比1(msbfs)加map rev结构
  5. idea_merge: 比3(idea_sep)加路径合并
  6. idea_merge_map: 比4(idea_sep_map)加路径合并
2
- 思考二级的必要性（二级的创新性有，但是和Map又有啥区别呢？）
  - map和两级都是解决这个问题：（每个instance一个记录）不同instance用相同的键去索引，且存储占用尽量每个instance只记录自己需要记录的
  - 更新友好？
- 发现实验结果idea_merge比idea_merge_map慢，决定再跑一次idea_merge

上午

1
- 分析下idea_merge和idea_merge_map的时间分布，二级慢在哪里？
  - 每一个阶段都慢了，但是path1阶段应该是完全一样的，所以要重新跑idea_merge
- 转移开发模式：本地调试，服务器跑，git同步（两处可增量）
  - 需要修改下m128实现和传递数据集文件
  - 学习AVX和AVX2下AVX512的平替
2
- 重新跑idea_merge
- AVX和AVX2和AVX512的实现（完成，尚未测试正确性）

下午

1
- 是否有必要实验msbfs_merge呢？感觉没必要，实验体系如下：
  1. msbfs degreeDescending
  2. msbfs oneHopNbrDegCross
  3. idea_sep: 比2加二级rev结构+一步走两步
  4. idea_sep_map: 比2加map rev结构+一步走两步
  5. idea_merge: 比3加路径合并
  6. idea_merge_map: 比4加路径合并
- 背单词
- 实验结果中5和6的找p1时间有不小差异，为什么会呢？检查下找p1的源码，按理这俩只有rev结构的差异
  - 检查了源码，按理5和6的找p1代码一模一样，可能是服务器的状态的原因
- 思考有没有加快二级结构的地方呢？
  - 实现：不是两级都vector动态增长
    - 改下这个试一试
  - 二级rev的大小（目前是路径长度的中位数）
2
- 调试AVX和AVX2和AVX512的实现（比特操作的接口正确性）
  - 这个通过test测试了，但是仍然有bug，disjoint_test的找p1有bug
- 改二级rev的实现（更新idea_sep和idea_merge_map实验结果）
  - 二级rev的实现目前想到的修改点是在构造时，即rev_p1时产生影响的，但是这个阶段和map相差不大
  - 主要要思考加速读
3
- 调整路径阶段也应该时间差不多
  - 检查下时间和代码：确实代码和rev结构的实现没有关系，但是时间差异在
  - 所以说一定要重新实验下
- 整理了下实验数据
  跑步（二级rev有没有优于map的地方呢？）
4
- 跑步的时候想到了新的一种数据结构：[vertex][instance]->ij，实验

晚上

1
- 实现vins merge（完成，开始调试）
2
- 完成调试，开始跑实验
3
- vins merge
  - 如果效果好的话，新实验体系：
    1->2 (i,j)发现和一步走两步 2->3路径合并 3&4&5&6数据结构存(i,j)
    1. msbfs (oneHopNbrDegCross)
    2. insV_sep_map: 比1加：insV_map rev结构+一步走两步
    3. insV_merge_map: 比1加：insV map rev结构+一步走两步+路径合并
    4. insV_merge: 比1加：insV二级rev结构+一步走两步+路径合并
    5. Vins_merge: 比1加：Vins rev结构+一步走两步+路径合并
    6. (running) Vij_merge: 比1加：Vij rev结构+一步走两步+路径合并
- 实现Vij_merge
4
- 检查Vins_merge实验结果
- 完成调试Vij_merge，跑

back

1
- 发现msbfs实现问题，更新之后也要重新跑
- 实现msbfs_merge
- 跑insV_merge,msbfs_merge,msbfs