代码之家 › 专栏 › 技术社区 › Thomas Ahle

递归联合查找是否可以优化?

union-find tail-recursion stack-overflow recursion loops

Thomas Ahle · 技术社区 · 9 年前

在执行联合查找时,我通常会编写 find 路径压缩功能如下:

def find(x):
    if x != par[x]:
        par[x] = find(par[x])
    return par[x]

这很容易记住,也很容易阅读。这也是许多书籍和网站描述该算法的原因。

然而,如果天真地编译,这将使用堆栈 输入内存线性 大小在许多语言和系统中,默认情况下会导致堆栈溢出。

我知道的唯一一种非递归的写作方式 发现 这是:

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会?)

我的问题是在什么情况下使用以前版本的 发现 ? 如果没有广泛使用的语言可以消除递归,我们不应该告诉人们使用迭代版本吗?还有可能有更简单的迭代实现吗?

1 回复 | 直到 9 年前

templatetypedef 9 年前

这里似乎有两个独立的问题。

首先,优化编译器能注意到这一点并重写它吗?如果不测试所有编译器和所有版本,很难回答这个问题。我使用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)];
}

这不会实现按排名的联合优化,但支持路径压缩。我使用优化级别-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中,我们通常不担心这样的细节,而更新的演示文稿虽然更直接地转化为实践,但会让我们更难看到关键思想。

当查看更高级的算法和数据结构的伪代码时,通常会忽略非常重要的实现细节,并手动保存某些任务可以在特定时间范围内完成。当讨论建立在更复杂的算法和数据结构之上的算法或数据结构时,通常不可能为所有内容编写伪代码,因为您在一层又一层的细节上有一层。从理论角度来看,这是可以的——如果读者确实想实现它,他们可以填补空白。另一方面,如果读者对论文和理论中的关键技术更感兴趣(这在学术环境中很常见),他们就不会陷入实现细节的泥潭。