0

私はC++を初めて使用するので、まだ学習中です。ツリーを再帰的に構築するアルゴリズムを作成しようとしています。通常は、以下の方法1に従って作成しますが、関数が返されると、RandomTreeNodeの（深い）コピーが作成されるため、呼び出すことが心配です。再帰的に、したがって方法2を好むでしょう。私の考えは正しいですか？

方法1

RandomTreeNode build_tree(std::vector<T>& data, const std::vector<funcion_ptr>& functions){
        if(data.size() == 0 || data_has_same_values(data)){
            RandomeTreeNode node = RandomTreeNode();
            node.setData(node);
            return node;
        }

        RandomTreeNode parent = RandomTreeNode();
        vector<T> left_data = split_data_left(data);
        vector<T> right_data = split_data_right(data);
        parent.set_left_child(build_tree(left_data));
        parent.set_right_child(build_tree(right_data));
        return parent;
    }

方法2

void build_tree(RandomTreeNode& current_node, vector<T> data){
    if(data.size() == 0 || data_has_same_values(data)){
        current_node.setData(node);
    }

    vector<T> left_data = split_data_left(data);
    vector<T> right_data = split_data_right(data);

    RandomTreeNode left_child = RandomTreeNode();
    RandomTreeNode right_child = RandomTreeNode();
    current_node.set_left_child(left_child);
    current_node.set_right_child(right_child);

    build_tree(left_child, left_data);
    build_tree(right_child, right_data);

}
4

1 に答える 1

1

いくつかの改善点があります。

  • まず、ベクトルをコピーします。関数の名前を理解しているので、ベクトルを2つのブロックに分割しています（[left|right]ではありません[l|r|lll|r|...]）。したがって、毎回ベクトルを渡す代わりに、インデックスを渡すだけで範囲を指定できます。

  • 方法2は、適切に実装されていれば、メモリ内でより効率的になります。したがって、その背後にある考え方を改善する必要があります。

  • 最後に、問題により適した補助関数を使用できます（方法1と方法2の組み合わせ）。

サンプルコードは次のとおりです。

// first is inclusive
// last is not inclusive
void build_tree_aux(RandomTreeNode& current_node, std::vector<T>& data, int first, int last)
{
    if(last == first || data_has_same_values(data,first,last))
    {
        current_node.setData(data,first,last);
        // ...
    }

    // Find new ranges
    int leftFirst = first;
    int leftLast = split_data(data,first,last);
    int rightFirst = leftLast;
    int rightLast = last;

    // Instead of copying an empty node, we create the children
    // of current_node, and then process these nodes
    current_node.build_left_child();
    current_node.build_right_child();

    // Recursion, left_child() and right_child() returns reference
    build_tree_aux(current_node.left_child(),data,leftFirst,leftLast);
    build_tree_aux(current_node.right_child(),data,rightFirst,rightLast);
    /*
        // left_child() and right_child() are not really breaking encapsulation,
        // because you can consider that the child nodes are not really a part of
        // a node.
        // But if you want, you can do the following:
        current_node.build_tree(data,leftFirst,leftLast);
        // Where RandomTreeNode::build_tree simply call build_tree_aux on the 2 childrens
    */
}

RandomTreeNode build_tree(std::vector<T>& data)
{
    RandomTreeNode root;

    build_tree_aux(root,data,0,data.size());

    return root;
}
于 2012-10-16T21:01:33.257 に答える