尝试定性分析「快慢指针」寻找链表中点

尝试定性分析「快慢指针」寻找链表中点

warning
WARNING
本文不是成熟可靠、达成普遍共识的结论，也不是有可靠数据支撑的学术研究成果．
本文只是笔者根据从书中学到的知识分析和猜测遇到的现实问题，并尝试着给予答案的过程，并不能作为真正可靠的结论使用．
笔者在目前尚未具有验证自己得到的分析结果的能力．

相信看本文的读者已经熟悉这道经典的算法题目了．说实话，自从笔者接触这道题目的「快慢指针」题解之后产生的想法是疑惑：「为什么『快慢指针』的方式来取链表的中点比单指针遍历两遍能更快？」
众所周知，这两种不同的算法拥有相同的时间复杂度 O(N)，此时无法仅根据时间复杂度对这两种算法在相同规模的数据下的运行速度作出判断．

测试结果

当然，两种算法究竟哪种更优应该让数据来证明，而不仅仅是纸面上的分析．但十分遗憾，笔者无法提供一个较为可靠的数据．笔者的机器上运行着众多的应用，机器的性能受各种因素影响较多，性能波动较大，无法提供一个数据．在 leetcode 上以两种方式的提交结果中也未见差异．而没有可靠的数据证实的分析也是本文标题中含有「尝试」的原因．

对比算法的 C 语言描述

首先，作为链表节点的结构体为：

struct ListNode
{
    int val;
    struct ListNode *next;
};

「快慢指针方式」的C语言描述为：

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *slow, *fast, *tmp;
    slow = head;
    fast = head;
    while (fast != NULL && (tmp = fast->next) != NULL)
    {
        fast = tmp->next;
        slow = slow->next;
    }
    return slow;
}

「单指针方式」的C语言描述为：

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *cur = head;
    int n = 0;
    while (cur != NULL)
    {
        ++n;
        cur = cur->next;
    }
    int k = 0;
    cur = head;
    while (k < n / 2)
    {
        ++k;
        cur = cur->next;
    }
    return cur;
}

假设有一条长度为9个节点的链表，使用「快慢指针方式」，快指针完整的遍历链表 9 个节点，慢指针遍历前 5 个节点；使用「单指针方式」首先遍历链表一次共 9 个节点，后再次遍历至中点共 5 个节点．
两种方式都涉及对链表的 14 个节点的内存位置进行访问．其他的差异则可以忽略不计．

那么，只好首先从汇编语言的层面对两种算法进行分析．

对比算法的机器代码描述

用 GCC 分别编译两个文件后便可得到下文中的汇编代码（GCC 的参数中添加 -S 对文件只执行「编译」，-Og 禁用编译器优化，防止代码变形）．
info
INFO
下文的汇编代码较 GCC 产生的代码，省略了无关的内容．
注意：下文为 AT&T 格式的汇编语言代码．

「快慢指针方式」的汇编代码：

	movq	%rdi, %rax
	jmp	.L2
.L4:
	movq	8(%rax), %rax //fast = tmp->next
	movq	8(%rdi), %rdi //slow = slow->next
.L2:
	testq	%rax, %rax //判断 fast == 0 ？ 也就是判断 fast == NULL ？
	je	.L3 // 如果 fast == NULL 就跳转至 .L3
	movq	8(%rax), %rax //把 tmp = fast->next
	testq	%rax, %rax //判断 tmp == NULL ?
	jne	.L4 //如果 tmp != NULL 就跳转至 .L4
.L3:
	movq	%rdi, %rax //把返回值复制至 %rax
	ret// 函数返回

「单指针方式」的汇编代码：

	movq	%rdi, %rax // cur = head
	movl	$0, %edx //n = 0
	jmp	.L2
.L3:
	addl	$1, %edx // ++n
	movq	8(%rax), %rax // cur = cur->next
.L2:
	testq	%rax, %rax // cur == NULL ?
	jne	.L3//如果  cur  != NULL 就跳转至 .L3
	movl	$0, %ecx // k = 0
	jmp	.L4
.L5:
	addl	$1, %ecx // ++k
	movq	8(%rdi), %rdi // cur = cur->next
.L4:
	movl	%edx, %eax //int tmp = n
	shrl	$31, %eax //tmp = tmp < 0 ? 1 : 0
	addl	%edx, %eax // tmp +=n
	sarl	%eax // tmp >>= 1
	cmpl	%ecx, %eax// tmp - k
	jg	.L5
	movq	%rdi, %rax //把返回值复制至 %rax
	ret // 函数返回

「单指针方式」的汇编代码中，第 16 行至第 19 行的代码可能在理解上有些难度，这些指令是为了计算 n / 2 的结果，因为除数是 2 的幂，那么除法总是可以用偏置和右移运算来代替．

可能有人会关注到在循环中，反复的进行了对 n /2 求值，甚至求值中的偏置是不必要的（因为 k 不可能为负值）．但这些问题在更高阶的编译优化中消失，并不能真正的影响 release 版本时的性能，那么这两种算法存在性能差异吗？笔者认为仍旧存在性能差异．

存储器的层次结构

在真正的说明笔者自己认为的两种算法的性能差异之前，还需要在回顾一下「存储器的层次结构」．
首先，程序运行中的数据和代码被加载至「DRAM」之中．
为解决 「CPU」 频率与 「DRAM」频率的巨大差异并权衡制造的成本，计算机学家们引入 「SRAM」 分 「L3 cache」、「L2 cache」、「L1 cache」三层，逐层的进行缓存，加速「CPU」访问「DRAM」中的内容的时间．
当 CPU 试图访问的数据不在缓存中时，即发生了 缓存不命中时，将触发「不命中惩罚」，造成程序效率的降低．「缓存不命中」是不可避免的，但可以通过一定的优化方式来减少「缓存不命中」．
当然，关于「存储器的层次结构」这庞大的知识非笔者只言片语能说明，在本文不再方便展开．

一个编写良好的计算机程序常常具有良好的局部性．也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身．这种倾向性被称为「局部性原理」．[1]
具有良好的局部性的程序能有效的减少「缓存不命中」，也就是更好的利用「存储器的层次结构」，使「CPU」更快速的访问所需的数据．

局部性通常有两种不同的形式：「时间局部性」和「空间局部性」．在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用．在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置．[1]

• 从空间局部性来考虑：
  链表中的节点存储的位置并无规律，每个节点是分散的，都具有较差的空间局部性．可大致认为两种算法的空间局部性相同．
• 从时间据局部性来考虑：
  • 「快慢指针方式」中：在一次循环中，链表的前半部分中，快指针访问完成之后循环结束之前慢指针已经访问了相同的节点．同一个节点被两次访问的时间间隔较近．
  • 「单指针方式」中：在一次循环中，链表的前半部分中，同一个节点的第二次访问在第一次遍历完成之后，同一个节点被两次访问的时间间隔较远．

可见，「快慢指针方式」具有更好的时间局部性，单指针第二次遍历链表时，可供其利用的「前半段链表中的节点」的缓存有更大的概率被链表的「后半段链表中的节点」的缓存所替换，由此将更频繁的触发「不命中处罚」．
更严重的是，若链表的节点增大，则在相同的缓存中能缓存的节点更少，缓存的替换将更频繁，「单指针方式」的性能想较「快慢指针方式」遍历可能下降更多．
同样的，若链表的长度增加，也会导致前半段的链表的节点的缓存被更多的替换．

循环展开

此时更换一个角度，再次回看「单指针方式」的 C语言代码，忽略次要部分后，可以视为使用一个循环 1.5 倍链表节点个数次，而「快慢指针方式」循环 1 倍节点个数次．
而「快慢指针」方式可视为由「单指针方式」进行「循环展开」得到的代码．

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数．[1]

循环展开能够从两个方面改进程序的性能．首先，它减少了不直接有助于程序结果的操作数量，例如循环索引计算和条件分支．第二它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量．[1]

参考资料

¹. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩