月度归档:2020年06月

CSAPP-记录

Last Updated on 2020年7月20日

  • Question In CSAPP:
    • switch比if-else高效吗?
    • switch可能更高效,比较相关的开销移动可能会移动到编译期.
    • while比for高效吗?
    • 二者相同
    • 指针比数组索引更高效吗?
    • 二者相同
    • 为什么在求和时,将结果存在本地变量中要比存储在传入的指针中更快?
      • 本地对象一般是在寄存器中, 而通过指针IO时,可能会触发内存操作
    • 为什么表达式的求值顺序会影响性能(括号的位置)
      • 限定求值顺序会影响编译器的优化.
      • 限定求值顺序有可能会改善内存访问的模式.
    • 函数调用的开销到底有多大?
Read More

KD树与SKD树

KD树与SKD树

首先给出两个搜到的有点内容的KD树文章,论述的比我说的更完整(更冗长),可以先看,也可以看完本文再看.
* https://www.zybuluo.com/l1ll5/note/967681
* http://www.whudj.cn/?p=920

主体思想

  • KD树和SKD树都使用坐标轴对齐的最小包围盒来描述空间.
    • 例如,平面内,一堆点的点集对应的空间可以用点A=(min(all_x),min(all_y)),B=(max(all_x),max(all_y)) 对应的矩形空间来描述. 当点的个数变为1时,这个矩形空间也会自然地退化为一个点.
  • 构建时的主要思想: 每个节点
Read More