Почему моя реализация на основе стека этого кода намного медленнее, чем рекурсия?
У меня есть дерево, чьи узлы хранят либо -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, чего я не ожидал. Что может сделать компилятор настолько умнее моего кода? Иными словами, что я делаю так неэффективно? Также меня озадачивает то, что если я попробую что-нибудь вроде проверки в версии B, то ли содержимое для детей -1, прежде чем положить их в стек, он резко замедляется (почти 3 раза). Для справки, я использую g++ в Cygwin с опцией -O3.
Update:
Мне удалось сопоставить рекурсивную версию, используя следующий код (версия 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];
}
}
}
}
Очевидными минусами являются длина кода и магическое число (и связанный с ним жесткий предел). И, как я сказал, это соответствует только производительности версии A. Я, конечно, буду придерживаться рекурсивной версии, но теперь я доволен тем, что это было главным образом из-за того, что я был в STL, кусая меня.
Ответы
Ответ 1
Версия A имеет одно существенное преимущество: гораздо меньший размер кода.
Версия B имеет один существенный недостаток: распределение памяти для элементов стека. Учтите, что стек начинается пустым и содержит элементы, вставляемые в него один за другим. Каждый раз так часто должно быть сделано новое распределение для лежащего ниже уровня. Это дорогостоящая операция, и ее можно повторить несколько раз для каждого вызова вашей функции.
Изменить: здесь сборка, сгенерированная g++ -O2 -S с GCC 4.7.3 на Mac OS, выполняется через 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 прямо сейчас, но достаточно сказать, что это сложнее из-за многих функций deque и набросания на гораздо большую память. Не удивительно, что это медленнее.
Ответ 2
Максимальный размер q в версии B значительно больше, чем максимальная глубина рекурсии в версии A. Это может сделать вашу производительность кэша довольно немного менее эффективной.
(версия A: глубина log(N)/log(b), версия B: длина очереди достигает b*log(N)/log(b))
Ответ 3
Второй код медленнее, поскольку он поддерживает вторую динамическую структуру данных в дополнение к возвращаемой коллекции. Это связано с большим объемом выделения памяти, большим количеством инициализаций объектов, добавлением и удалением списка.
Однако алгоритм во втором коде более гибкий: он может быть тривиально изменен, чтобы сначала сначала пройти обход в ширину вместо глубины, тогда как рекурсия выполняет только обход глубины. (Ну, сначала он может идти глубже, но изменение не совсем так тривиально, см. Комментарий в конце.)
Так как задача состоит в том, чтобы пересечь все и собрать некоторые узлы, возможно, лучше всего пройти первый проход, предполагая, что вам не нужен порядок глубины.
Но в ситуациях, когда вы ищете node, который удовлетворяет некоторому условию, может быть более целесообразным реализовать поиск по ширине. Если дерево бесконечно (потому что это не структура данных, а дерево поиска возможностей, например, будущие движения в игре или что-то еще), это может быть неразрешимым делать глубину в первую очередь, потому что нет дна. В некоторых ситуациях желательно найти node, который близок к корню, а не только любому node. Поиск по глубине может занять много времени, чтобы найти node, который близок к корню дерева. Если дерево глубокое, но обычно желаемый node находится недалеко от корня, поиск по глубине может потратить много времени, даже если рекурсивный механизм, который его реализует, быстро.
Рекурсия может сделать ширину - сначала путем итеративного углубления: рекурсия на максимальную глубину 1, затем повторить сверху, на этот раз до макс. глубины 2 и т.д. Обход на основе очереди просто должен изменить порядок, в котором он добавляет узлы в рабочую очередь.
