使用boost属性树的get_child_optional方法的时间复杂度是多少?与std::unordered_map查找相比,如果我们将节点名和属性树存储为KV对,它的速度有多快或多慢?未找到相同的文档
afdcj2ne1#
它调用walk_path()来完成大部分工作,如下所示:https://github.com/boostorg/property_tree/blob/88a3b0ba8a6cd4ddf35f10d841bde9878241d64a/include/boost/property_tree/detail/ptree_implementation.hpp#L885-L900
walk_path()
// 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查找相比,它有多快或多慢?你必须用你的实际数据来测试一下。
find()
ordered_non_unique
get_child_optional()
1条答案
按热度按时间afdcj2ne1#
它调用
walk_path()
来完成大部分工作,如下所示:https://github.com/boostorg/property_tree/blob/88a3b0ba8a6cd4ddf35f10d841bde9878241d64a/include/boost/property_tree/detail/ptree_implementation.hpp#L885-L900那么
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查找相比,它有多快或多慢?
你必须用你的实际数据来测试一下。