c - 在 DFS 实现中使用程序堆栈

Question

我的代码中有一个标准的 DFS 实现，它在每次调用时使用动态分配的堆栈。

我经常调用这个函数。通常仅在小型运行(200-1000)个节点上运行，但有时会存在具有一百万个或更多节点的大型连接组件。

分析器显示大量的计算时间浪费在分配堆栈上。我想尝试重用现有内存(例如调用堆栈)。但是该函数必须保持线程安全。

是否有一种有效的方法来动态使用调用堆栈而不使函数递归？

到目前为止，我最好的想法是使用一个额外的参数使函数递归，该参数使每次后续调用的自动堆栈大小加倍。

伪C:

void dfs(size_t stack_length, void * graph, graphnode_t start_node) {
    graphnode_t stack[stack_length];
    size_t stack_size = 0;

    for (all nodes) {
        // do something useful
        if (stack_size < stack_length) {
            stack[stack_size++] = new_node;
        } else {
            dfs(stack_length * 2, graph, new_node);
        }
    }

}

Answer 1

听起来您正在描述您的算法只需使用系统的单个 graphnode_t 数组即可正常工作(尽管您将其称为堆栈，但我认为这并不真正适用)此处)，唯一真正的问题是您在开始时不确定它应该有多大。

如果是这种情况，我首先建议您不要将这个(可能很大)数组设置为局部变量，因为这会导致实际程序堆栈出现问题。相反，让它成为一个静态指针，指向动态大小的内存，如果需要，您可以定期扩展该内存。

ensure_size(graphnode_t **not_a_stack_ptr, unsigned long *length_ptr)
{
    if (!*not_a_stack_ptr)
    {
        *not_a_stack_ptr = malloc(sizeof(graphnode_t) * MINIMUM_ENTRY_COUNT);
        *length_ptr = MINIMUM_ENTRY_COUNT;
    }
    else if (size needs to double)
    {
        *length_ptr *= 2;
        *not_a_stack_ptr = realloc(*not_a_stack_ptr, sizeof(graphnode_t) * (*length_ptr));
    }
}


struct thread_arguments {
    void * graph;
    graphnode_t start_node;
}

dfs_thread(void *void_thread_args)
{
    struct thread_arguments *thread_args = void_thread_args;
    graphnode_t *not_a_stack = NULL;
    unsigned long not_a_stack_length = 0;

    for (all nodes)
    {
        ensure_size(&not_a_stack, &not_a_stack_length);
        stack[stack_size++] = new_node;
    }

    if (not_a_stack) free(not_a_stack);
}

注意:您的伪代码表明最大大小可以根据您拥有的节点数量来确定。通过使用它预先执行一个完整大小的 malloc，您将获得最大的性能增益。