以迭代方式合并标准::unordered_map

Question

我有一个节点列表，每个节点分解为更多节点。例如

• 节点 0 = w01 * 节点 1 + w02 * 节点 2 + w03 * 节点 3
• 节点 1 = w12 * 节点 2 + w14 * 节点 4

因此，我们有 Node0 = w01*w12 * 节点 2 + w03 * 节点 3 + w01*w14 节点 4。

---

我用于对给定的一组权重分解执行上述聚合/分解/合并的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}
}

Answer 1

主要问题是您将每个节点递归到每个子节点，这通常是高度冗余的。避免这种情况的一种方法是在节点名称上引入一个顺序，其中"较高"节点仅依赖于"较低"节点，然后以相反的顺序计算它们(对于每个节点，您已经确切地知道所有子权重(。但是，我认为没有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;
}

演示

由于每个节点最多展平一次，因此您无法遇到原始算法的指数级运行时。

Answer 2

我建议先进行拓扑排序，然后再进行动态规划算法。 使用可汗算法的拓扑排序的标准版本需要时间O(V+E)。 (如果该链接过时，您可以使用Google查找另一个链接。 在您的例子中，V是节点数，E是出现在所有表达式中的字词数。

如果该排序失败，则您已经找到了循环依赖项。 以这种方式发现它比让你的代码爆炸要好。

一旦你有了这种排序，那么使用 DP 从末端到前面就非常简单了。

此外，如果您真正关心性能，您的性能约束之一是每个操作都是使用字符串比较完成的。 扔很多字符串既简单又方便 - 这就是脚本语言一直这样做的原因。 但是它也很慢。 我发现过去值得创建一个查找结构，在输入性能关键代码之前将字符串转换为索引，然后抛出某种类型的int而不是字符串。 然后在最后使用查找将其重新转换为字符串。