recursive union find 可以优化吗？
Can recursive union find be optimized?
在实现union-find的时候，我通常会这样写find带有路径压缩的函数：
def find(x):
if x != par[x]:
par[x] = find(par[x])
return par[x]
这很容易记住，而且可以说很容易阅读。这也是很多书籍和网站描述算法的方式。
然而，天真地编译，这将使用输入 大小的堆栈 线性内存。在许多语言和系统中，默认情况下会导致堆栈溢出。
我知道的唯一非递归的写法 find 是这样的：
def find(x):
p = par[x]
while p != par[p]:
p = par[p]
while x != p:
x, par[x] = par[x], p
return p
许多编译器似乎不太可能发现这一点。 （也许 Haskell 会？）
我的问题是在什么情况下使用 find 的旧版本是安全的？如果没有广泛使用的语言可以消除递归，我们难道不应该告诉人们使用迭代版本吗？是否有更简单的迭代实现？
这里好像有两个不同的问题。
首先 - 优化编译器能否注意到这一点并重写它？如果不测试所有编译器和所有版本，很难回答这个问题。我在以下代码中使用 gcc 4.8.4 进行了尝试：
size_t find(size_t uf[], size_t index) {
if (index != uf[index]) {
uf[index] = find(uf, uf[index]);
}
return uf[index];
}
void link(size_t uf[], size_t i, size_t j) {
uf[find(uf, i)] = uf[find(uf, j)];
}
这没有实现 union-by-rank 优化，但支持路径压缩。我使用优化级别 -O3 编译了它，程序集显示如下：
find:
.LFB23:
.cfi_startproc
pushq %r14
.cfi_def_cfa_offset 16
.cfi_offset 14, -16
pushq %r13
.cfi_def_cfa_offset 24
.cfi_offset 13, -24
pushq %r12
.cfi_def_cfa_offset 32
.cfi_offset 12, -32
pushq %rbp
.cfi_def_cfa_offset 40
.cfi_offset 6, -40
pushq %rbx
.cfi_def_cfa_offset 48
.cfi_offset 3, -48
leaq (%rdi,%rsi,8), %rbx
movq (%rbx), %rax
cmpq %rsi, %rax
je .L2
leaq (%rdi,%rax,8), %rbp
movq 0(%rbp), %rdx
cmpq %rdx, %rax
je .L3
leaq (%rdi,%rdx,8), %r12
movq %rdx, %rax
movq (%r12), %rcx
cmpq %rcx, %rdx
je .L4
leaq (%rdi,%rcx,8), %r13
movq %rcx, %rax
movq 0(%r13), %rdx
cmpq %rdx, %rcx
je .L5
leaq (%rdi,%rdx,8), %r14
movq %rdx, %rax
movq (%r14), %rsi
cmpq %rsi, %rdx
je .L6
call find // <--- Recursion!
movq %rax, (%r14)
.L6:
movq %rax, 0(%r13)
.L5:
movq %rax, (%r12)
.L4:
movq %rax, 0(%rbp)
.L3:
movq %rax, (%rbx)
.L2:
popq %rbx
.cfi_def_cfa_offset 40
popq %rbp
.cfi_def_cfa_offset 32
popq %r12
.cfi_def_cfa_offset 24
popq %r13
.cfi_def_cfa_offset 16
popq %r14
.cfi_def_cfa_offset 8
ret
.cfi_endproc
鉴于中间递归调用的存在，看来这个尾调用并没有被消除。公平地说，那是因为你所描述的转变非常重要，所以我对它没有找到它并不感到惊讶。这并不意味着 没有 优化编译器可以找到它，但一个主要的不会。
你的第二个问题是我们为什么要这样呈现算法。作为同时教授算法和编程的人，我认为使用尽可能简单的演示文稿来讨论算法是非常有价值的，即使这意味着抽象出一些特定的实现细节。在这里，算法背后的关键思想是更新在通往代表的路上遇到的所有节点的父指针。递归恰好是描述该想法的一种非常简洁的方式，即使在天真地实现时它有堆栈溢出的风险。然而，通过以这种特定方式表达伪代码，更容易描述和讨论它并证明它会像宣传的那样工作。我们可以用另一种方式来描述它以避免堆栈溢出，但在 Theoryland 中我们通常不担心这样的细节和更新的演示文稿，虽然可以更直接地转化为实践，但会让人更难看到关键思想。
在查看更高级算法和数据结构的伪代码时，通常会忽略极其重要的实现细节，并暗示某些任务可以在特定时间范围内完成。在讨论构建在更复杂算法和数据结构之上的算法或数据结构时，通常不可能为所有内容编写伪代码，因为您在 glossed-over 细节层之上的层之上层层叠叠。从理论上讲，这很好——如果 reader 确实想要实现它，他们可以填补空白。另一方面，如果 reader 对论文和理论中的关键技术更感兴趣（这在学术环境中很常见），他们就不会陷入实施细节的泥潭。
在实现union-find的时候，我通常会这样写find带有路径压缩的函数：
def find(x):
if x != par[x]:
par[x] = find(par[x])
return par[x]
这很容易记住，而且可以说很容易阅读。这也是很多书籍和网站描述算法的方式。
然而，天真地编译，这将使用输入 大小的堆栈 线性内存。在许多语言和系统中，默认情况下会导致堆栈溢出。
我知道的唯一非递归的写法 find 是这样的：
def find(x):
p = par[x]
while p != par[p]:
p = par[p]
while x != p:
x, par[x] = par[x], p
return p
许多编译器似乎不太可能发现这一点。 （也许 Haskell 会？）
我的问题是在什么情况下使用 find 的旧版本是安全的？如果没有广泛使用的语言可以消除递归，我们难道不应该告诉人们使用迭代版本吗？是否有更简单的迭代实现？
这里好像有两个不同的问题。
首先 - 优化编译器能否注意到这一点并重写它？如果不测试所有编译器和所有版本，很难回答这个问题。我在以下代码中使用 gcc 4.8.4 进行了尝试：
size_t find(size_t uf[], size_t index) {
if (index != uf[index]) {
uf[index] = find(uf, uf[index]);
}
return uf[index];
}
void link(size_t uf[], size_t i, size_t j) {
uf[find(uf, i)] = uf[find(uf, j)];
}
这没有实现 union-by-rank 优化，但支持路径压缩。我使用优化级别 -O3 编译了它，程序集显示如下：
find:
.LFB23:
.cfi_startproc
pushq %r14
.cfi_def_cfa_offset 16
.cfi_offset 14, -16
pushq %r13
.cfi_def_cfa_offset 24
.cfi_offset 13, -24
pushq %r12
.cfi_def_cfa_offset 32
.cfi_offset 12, -32
pushq %rbp
.cfi_def_cfa_offset 40
.cfi_offset 6, -40
pushq %rbx
.cfi_def_cfa_offset 48
.cfi_offset 3, -48
leaq (%rdi,%rsi,8), %rbx
movq (%rbx), %rax
cmpq %rsi, %rax
je .L2
leaq (%rdi,%rax,8), %rbp
movq 0(%rbp), %rdx
cmpq %rdx, %rax
je .L3
leaq (%rdi,%rdx,8), %r12
movq %rdx, %rax
movq (%r12), %rcx
cmpq %rcx, %rdx
je .L4
leaq (%rdi,%rcx,8), %r13
movq %rcx, %rax
movq 0(%r13), %rdx
cmpq %rdx, %rcx
je .L5
leaq (%rdi,%rdx,8), %r14
movq %rdx, %rax
movq (%r14), %rsi
cmpq %rsi, %rdx
je .L6
call find // <--- Recursion!
movq %rax, (%r14)
.L6:
movq %rax, 0(%r13)
.L5:
movq %rax, (%r12)
.L4:
movq %rax, 0(%rbp)
.L3:
movq %rax, (%rbx)
.L2:
popq %rbx
.cfi_def_cfa_offset 40
popq %rbp
.cfi_def_cfa_offset 32
popq %r12
.cfi_def_cfa_offset 24
popq %r13
.cfi_def_cfa_offset 16
popq %r14
.cfi_def_cfa_offset 8
ret
.cfi_endproc
鉴于中间递归调用的存在，看来这个尾调用并没有被消除。公平地说，那是因为你所描述的转变非常重要，所以我对它没有找到它并不感到惊讶。这并不意味着 没有 优化编译器可以找到它，但一个主要的不会。
你的第二个问题是我们为什么要这样呈现算法。作为同时教授算法和编程的人，我认为使用尽可能简单的演示文稿来讨论算法是非常有价值的，即使这意味着抽象出一些特定的实现细节。在这里，算法背后的关键思想是更新在通往代表的路上遇到的所有节点的父指针。递归恰好是描述该想法的一种非常简洁的方式，即使在天真地实现时它有堆栈溢出的风险。然而，通过以这种特定方式表达伪代码，更容易描述和讨论它并证明它会像宣传的那样工作。我们可以用另一种方式来描述它以避免堆栈溢出，但在 Theoryland 中我们通常不担心这样的细节和更新的演示文稿，虽然可以更直接地转化为实践，但会让人更难看到关键思想。
在查看更高级算法和数据结构的伪代码时，通常会忽略极其重要的实现细节，并暗示某些任务可以在特定时间范围内完成。在讨论构建在更复杂算法和数据结构之上的算法或数据结构时，通常不可能为所有内容编写伪代码，因为您在 glossed-over 细节层之上的层之上层层叠叠。从理论上讲，这很好——如果 reader 确实想要实现它，他们可以填补空白。另一方面，如果 reader 对论文和理论中的关键技术更感兴趣（这在学术环境中很常见），他们就不会陷入实施细节的泥潭。