迭代合并std::unordered_map

Question

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

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

因此，我们有 Node0 = w01*w12 * Node2 + w03 * Node3 + w01*w14 Node4。

为给定的一组权重分解执行上述 aggregation/decomposition/merging 的 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

主要问题是您将 every 节点递归到 every 子节点，这通常是高度冗余的。避免这种情况的一种方法是在节点名称上引入顺序，其中 "higher" 节点仅依赖于 "lower" 节点，然后以相反的顺序计算它们（对于每个节点，您已经知道所有子节点重量准确）。但是，我认为没有 std 算法可以为您找到此顺序，因为您无法廉价地瞬时确定节点依赖关系 ("does node X depend on node Y? If it's not directly, we might have to search the entire tree...")。

因此，您可以走动态规划路线，将已完全计算出的节点存储在某处。或者甚至更好 - 你可以在遍历它时将整棵树压扁到只有叶子的权重。只要你在整个递归过程中保持扁平化，这在递归形式中实际上是相当优雅的：

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;
}

Demo

由于每个节点最多被展平一次，因此您不能运行进入原始算法所具有的指数运行时间。

Answer 2

我建议先进行拓扑排序，然后再进行动态规划算法。 Standard versions 使用 Khan 算法的拓扑排序需要时间 O(V+E)。（如果那个 link 变得陈旧，你可以只使用 Google 找到另一个。）在你的情况下 V 是节点数， E 是术语数出现在你所有的表情中。

如果排序失败，那么您发现了循环依赖。以这种方式发现它比让你的代码爆炸更好。

一旦你有了那种排序，那么用 DP 从头到尾就非常简单了。

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

迭代合并std::unordered_map

Merge std::unordered_map iteratively

c++

algorithm

merge

unordered-map

c++17