- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我有一个节点列表,每个节点都分解成更多节点。例如
因此,我们有 Node0 = w01*w12 * Node2 + w03 * Node3 + w01*w14 Node4。
为一组给定的权重分解执行上述聚合/分解/合并的 C++ 代码如下所示。但是,我觉得还有很多优化要做。仅举一个例子,我正在遍历 topWeights
的键并将它们收集到 topNodeNames
中,这似乎非常低效。
是否有任何 STL 算法可以帮助我加快速度,并可能避免不必要的复制?
#include <string>
#include <unordered_map>
template<class T, class U> using umap = std::unordered_map<T, U>;
umap<std::string, double> getWeights(const std::string& nodeName, const umap<std::string, umap<std::string, double>>& weightTrees)
{
const auto it = weightTrees.find(nodeName);
if (it == weightTrees.end())
return umap<std::string, double>();
umap<std::string, double> topWeights = it->second;
std::vector<std::string> topNodeNames;
for (const auto& kv : topWeights)
topNodeNames.push_back(kv.first);
for (const std::string& topNodeName : topNodeNames)
{
umap<std::string, double> subWeights = getWeights(topNodeName, weightTrees);
if (subWeights.size() > 0)
{
const double topWeight = topWeights[topNodeName];
topWeights.erase(topNodeName);
for (const auto& subWeight : subWeights)
{
const auto it = topWeights.find(subWeight.first);
if (it == topWeights.end())
topWeights[subWeight.first] = topWeight * subWeight.second;
else
it->second += topWeight * subWeight.second;
}
}
}
return topWeights;
}
int main()
{
umap<std::string, umap<std::string, double>> weightTrees = {{ "Node0", {{ "Node1",0.5 },{ "Node2",0.3 },{ "Node3",0.2 }} },
{ "Node1", {{ "Node2",0.1 },{ "Node4",0.9 }} }};
umap<std::string, double> w = getWeights("Node0", weightTrees); // gives {Node2: 0.35, Node3: 0.20, Node4: 0.45}
}
最佳答案
主要问题是您将每个 节点递归到每个 子节点,这通常是高度冗余的。避免这种情况的一种方法是在节点名称上引入一个顺序,其中“较高”节点仅依赖于“较低”节点,然后以相反的顺序计算它们(对于每个节点,您已经确切地知道所有子权重)。但是,我不认为有 std
算法可以为您找到此顺序,因为您无法廉价地暂时确定节点依赖性(“节点 X 是否依赖于节点 Y?如果不是直接的,我们可能必须搜索整棵树...").
因此,您可以走动态规划路线,将已完全计算的节点存储在某处。或者甚至更好 - 你可以在遍历它时将整棵树压扁到只有叶子的权重。只要在整个递归过程中保持扁平化,这在递归形式中实际上是相当优雅的:
using NodeWeights = std::unordered_map<std::string, double>;
using NonLeaves = std::unordered_map<std::string, NodeWeights>;
// Modifies the tree so that the given root has no non-leaf children.
void flattenTree(std::string root, NonLeaves& toFlatten)
{
auto rootIt = toFlatten.find(root);
if (rootIt == toFlatten.end())
return;
NodeWeights& rootWeights = rootIt->second;
NodeWeights leafOnlyWeights;
for (auto kvp : rootWeights)
{
const std::string& childRoot = kvp.first;
double childWeight = kvp.second;
std::cout << "Checking child " << childRoot << std::endl;
// If the graph is indeed acyclic, then the root kvp here is untouched
// by this call (and thus references to it are not invalidated).
flattenTree(childRoot, toFlatten);
auto childIt = toFlatten.find(childRoot);
// The child is a leaf after flattening: Do not modify anything.
if (childIt == toFlatten.end())
{
leafOnlyWeights[childRoot] = childWeight;
continue;
}
// Child is still not a leaf (but all its children are now leaves):
// Redistribute its weight among our other child weights.
const NodeWeights& leafWeights = childIt->second;
for (auto leafKvp : leafWeights)
leafOnlyWeights[leafKvp.first] += childWeight * leafKvp.second;
}
rootWeights = leafOnlyWeights;
}
int main()
{
umap<std::string, umap<std::string, double>> weightTrees = {{ "Node0", {{ "Node1",0.5 },{ "Node2",0.3 },{ "Node3",0.2 }} },
{ "Node1", {{ "Node2",0.1 },{ "Node4",0.9 }} }};
auto flattenedTree = weightTrees;
flattenTree("Node0", flattenedTree);
umap<std::string, double> w = flattenedTree["Node0"]; // Should give {Node2: 0.35, Node3: 0.20, Node4: 0.45}
for (auto kvp : w)
std::cout << kvp.first << ": " << kvp.second << std::endl;
}
由于每个节点最多被展平一次,因此您不会遇到原始算法所具有的指数运行时间。
关于c++ - 迭代合并 std::unordered_map,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52932680/
我目前正在寻找 std::map 的更好替代方案,并且遇到了帖子标题中提到的类。有人可以阐明它们之间的区别,不是在性能/API 方面,而是在它们与当前和 future 的通信标准相关的地方。 最佳答案
我正在尝试使用一个 unordered_map 和另一个 unordered_map 作为键(自定义哈希函数)。我还添加了一个自定义的 equal 函数,尽管它可能并不需要。 代码没有达到我的预期,但
关闭。这个问题是not reproducible or was caused by typos .它目前不接受答案。 这个问题是由于错别字或无法再重现的问题引起的。虽然类似的问题可能是on-topi
我正在尝试从 unordered_map 中返回 unordered_map 的拷贝。 下面的代码更清楚地说明了我的问题: typedef std::unordered_map Foo; typede
我有一个类型为unordered_map的容器,我想确认要向 map 添加元素时应使用哪个版本。我希望它使用新呈现的旧值覆盖旧的值(如果存在),如果不存在则仅添加它。 我看到insert会在元素退出时
所以我试图将 unordered_map 设置为另一个 unordered_map 的值。 现在我遇到了无法将值放入第二个 unordered_map 的问题。 我的代码看起来像这样。 std::
我有一个数据结构,它是 unordered_map 的 unordered_map: typedef std::unordered_map map1; typedef std::unordered_m
我们正在用 C++ 为学校开发一个游戏项目。我负责 map 对象,它将包含炸弹、玩家、墙壁和盒子等实体。我的 map 中有 3 个容器: 玩家的 std::list(多个玩家可以站在同一个盒子上)。
我正在使用 unordered_maps 的 unordered_map,这样我就可以使用“多键”语法来引用元素: my_map[k1][k2]。 有没有一种方便的方法可以在尝试访问之前使用相同的“多
假设我有一个 unordered_map 定义如下: unordered_map> f_table; f_table[1][3] = 10; f_table[1][2] = 1; f_table[1]
我正在 interviewbit.com 上解决竞争性编程问题我基本上使用 unordered_map 来跟踪访问过的数字。当我使用 operator[] 时,我的代码无法及时执行,但是当我使用 fi
我有一张 map ,如下所示。 struct B { int b1; int b2; int b3; }; struct A { B a1; B a2; }; unordered
我有以下数据结构问题?你能帮帮我吗?所以我的要求是在我将新数据项添加到此 map 时将此数据结构初始化为默认值。 我怎样才能有效地做到这一点? 对于我要添加的每个条目,我需要将 a1、a2、a3 设置
对于我的下一个任务,我需要使用一个非常大的散列;因为我有一个旧的编译器,所以我不能使用 C++0x std::unordered_map。理想情况下,我需要调用 reserve 为大量元素提前腾出空间
我不明白为什么这个简短示例中的第二个代码块无法正确编译。我的理解是 <> 中的第二个参数表示值,它不需要是唯一的。为什么第二个代码块抛出编译器错误,我需要做什么来补救它? // Unordered M
这段代码运行成功,结果为“Character Found”。 unordered_map mp; mp['a'] = 'b'; char b='b'; if(mp['a'] && mp['a'] ==
std::unordered_map::emplace和std::unordered_map::insert在C++中有什么区别? 最佳答案 unordered_map::insert 将键值对复制或
哪个更有效率?有什么好的基准吗? 最佳答案 C++11 的 std::unordered_map 规范类似于基于 tr1::unordered_map 的 boost::unordered_map。话
使用 gcc 4.8.1 和 libboost 1.53,根据我用于编译代码的优化级别,我得到了不同的结果。作为更大程序的一部分,函数 insertValues 对相同的 a、key 和 value
我正在尝试使用 boost::mulprecision 类型创建一个 STL(或 boost)unordered_map,例如cpp_int 但 gcc 在尝试将元素插入此容器后抛出错误。 #incl
我是一名优秀的程序员,十分优秀!