c++ 提升属性树时间复杂度

drnojrws  于 2023-06-25  发布在  其他
关注(0)|答案(1)|浏览(137)

使用boost属性树的get_child_optional方法的时间复杂度是多少?与std::unordered_map查找相比,如果我们将节点名和属性树存储为KV对,它的速度有多快或多慢?
未找到相同的文档

afdcj2ne

afdcj2ne1#

它调用walk_path()来完成大部分工作,如下所示:https://github.com/boostorg/property_tree/blob/88a3b0ba8a6cd4ddf35f10d841bde9878241d64a/include/boost/property_tree/detail/ptree_implementation.hpp#L885-L900

// Recurse down the tree to find the path.
        key_type fragment = p.reduce();
        const_assoc_iterator el = find(fragment);
        if(el == not_found()) {
            // No such child.
            return 0;
        }
        // Not done yet, recurse.
        return el->second.walk_path(p);

那么find()呢?它位于Boost MultiIndex容器上:https://github.com/boostorg/property_tree/blob/88a3b0ba8a6cd4ddf35f10d841bde9878241d64a/include/boost/property_tree/detail/ptree_implementation.hpp#L40-L51
这里记录了ordered_non_unique类型:https://www.boost.org/doc/libs/1_67_0/libs/multi_index/doc/reference/ord_indices.html#complexity_signature
所以总的来说,它是O(n log m):线性时间以传递给get_child_optional()的路径组件数n表示,对数时间以遍历路径组件的每一步的子节点数m表示。
与std::unordered_map查找相比,它有多快或多慢?
你必须用你的实际数据来测试一下。

相关问题