我有一棵树,其节点存储 -1 或非负整数,即顶点名称。每个顶点在树中最多出现一次。以下函数是我代码中的瓶颈:
版本 A:
void node_vertex_members(node *A, vector<int> *vertexList){
if(A->contents != -1){
vertexList->push_back(A->contents);
}
else{
for(int i=0;i<A->children.size();i++){
node_vertex_members(A->children[i],vertexList);
}
}
}
B 版:
void node_vertex_members(node *A, vector<int> *vertexList){
stack<node*> q;
q.push(A);
while(!q.empty()){
int x = q.top()->contents;
if(x != -1){
vertexList->push_back(x);
q.pop();
}
else{
node *temp = q.top();
q.pop();
for(int i=temp->children.size()-1; i>=0; --i){
q.push(temp->children[i]);
}
}
}
}
由于某种原因,版本 B 的运行时间明显长于版本 A,这是我没有预料到的。编译器可能在做什么比我的代码聪明得多?换句话说,我在做什么这么低效?让我感到困惑的是,如果我在将 child 的内容放入堆栈之前尝试检查版本 B 是否为 -1,它会显着减慢(几乎 3 倍)。作为引用,我在 Cygwin 中使用带有 -O3 选项的 g++。
更新:
我能够使用以下代码(版本 C)匹配递归版本:
node *node_list[65536];
void node_vertex_members(node *A, vector<int> *vertex_list){
int top = 0;
node_list[top] = A;
while(top >= 0){
int x = node_list[top]->contents;
if(x != -1){
vertex_list->push_back(x);
--top;
}
else{
node* temp = node_list[top];
--top;
for(int i=temp->children.size()-1; i>=0; --i){
++top;
node_list[top] = temp->children[i];
}
}
}
}
明显的缺点是代码长度和魔数(Magic Number)(以及相关的硬限制)。而且,正如我所说,这仅匹配版本 A 的性能。我当然会坚持使用递归版本,但现在我很满意它基本上是 STL 开销咬我。
最佳答案
版本 A 有一个显着优势:代码量要小得多。
版本 B 有一个明显的缺点:堆栈元素的内存分配。考虑堆栈一开始是空的,并且有元素一个一个地插入其中。每隔一段时间,就必须为底层的双端队列进行新的分配。这是一项昂贵的操作,每次调用函数时可能会重复几次。
编辑:这是 g++ -O2 -S
在 Mac OS 上使用 GCC 4.7.3 生成的程序集,通过 c++filt
运行并由我注释:
versionA(node*, std::vector<int, std::allocator<int> >*):
LFB609:
pushq %r12
LCFI5:
movq %rsi, %r12
pushq %rbp
LCFI6:
movq %rdi, %rbp
pushq %rbx
LCFI7:
movl (%rdi), %eax
cmpl $-1, %eax ; if(A->contents != -1)
jne L36 ; vertexList->push_back(A->contents)
movq 8(%rdi), %rcx
xorl %r8d, %r8d
movl $1, %ebx
movq 16(%rdi), %rax
subq %rcx, %rax
sarq $3, %rax
testq %rax, %rax
jne L46 ; i < A->children.size()
jmp L35
L43: ; for(int i=0;i<A->children.size();i++)
movq %rdx, %rbx
L46:
movq (%rcx,%r8,8), %rdi
movq %r12, %rsi
call versionA(node*, std::vector<int, std::allocator<int> >*)
movq 8(%rbp), %rcx
leaq 1(%rbx), %rdx
movq 16(%rbp), %rax
movq %rbx, %r8
subq %rcx, %rax
sarq $3, %rax
cmpq %rbx, %rax
ja L43 ; continue
L35:
popq %rbx
LCFI8:
popq %rbp
LCFI9:
popq %r12
LCFI10:
ret
L36: ; vertexList->push_back(A->contents)
LCFI11:
movq 8(%rsi), %rsi
cmpq 16(%r12), %rsi ; vector::size == vector::capacity
je L39
testq %rsi, %rsi
je L40
movl %eax, (%rsi)
L40:
popq %rbx
LCFI12:
addq $4, %rsi
movq %rsi, 8(%r12)
popq %rbp
LCFI13:
popq %r12
LCFI14:
ret
L39: ; slow path for vector to expand capacity
LCFI15:
movq %rdi, %rdx
movq %r12, %rdi
call std::vector<int, std::allocator<int> >::_M_insert_aux(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&)
jmp L35
这相当简洁,乍一看似乎没有“减速带”。当我使用 -O3 进行编译时,我会遇到一团糟,包括展开的循环和其他有趣的东西。我现在没有时间注释版本 B,但我只想说它更复杂,因为它有许多双端队列函数和更多的内存。速度慢一点也不奇怪。
关于c++ - 为什么我基于堆栈的代码实现比递归慢得多?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17257862/