0

私のコードには、呼び出しごとに動的に割り当てられたスタックを使用する標準の DFS 実装があります。

私はその機能をよく呼び出します。多くの場合、小規模な実行 (200 ～ 1000) ノードですが、場合によっては、100 万ノード以上の大規模な接続コンポーネントがあります。

プロファイラーは、スタックの割り当てにかなりの計算時間が浪費されていることを示しています。既存のメモリ (コール スタックなど) を再利用したいと考えています。ただし、関数はスレッドセーフのままにする必要があります。

関数を再帰的にせずにコールスタックを動的に使用する効率的な方法はありますか?

これまでの私の最善のアイデアは、後続の呼び出しごとに自動スタック サイズを 2 倍にする追加の引数を使用して、関数を再帰的にすることでした。

疑似 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);
        }
    }

}
4

1 に答える 1

0

あなたのアルゴリズムはシステムの単一の配列だけでうまく機能すると説明しているように聞こえますが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 を 1 つだけ前もって実行することで、最大のパフォーマンスが得られます。

于 2013-11-12T11:49:43.093 に答える