迭代合并 std::unordered_map

Question

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

• Node0 = w01 * Node1 + w02 * Node2 + w03 * Node3
• Node1 = w12 * Node2 + w14 * Node4

因此，我们有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}
}

- Phil-ZXX

---

在循环依赖的情况下会发生什么（我假设没有）？您的实际用例是否在不同分支之间有许多共同节点？ - Max Langhof

循环依赖在实际情况下永远不应该发生。但我同意，为此进行某种安全检查是很好的。至于问题2，它确实可能会有所不同。 - Phil-ZXX

没有级别的限制。一个节点可以分解成另一个节点，然后再分解成另一个节点，再分解成两个节点等等。 - Phil-ZXX

节点之间已经有顺序了吗？（即NodeN不依赖于具有K < N的节点NodeK吗）？编辑：是的，我在之前的问题中误解了规范。 - Max Langhof

@MaxLanghof 不必拘泥于节点的命名，可以随意使用ABC、Node23、Server10、TestNode等名称。 - Phil-ZXX

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

演示

由于每个节点最多只会被压扁一次，你不会遇到原始算法的指数级运行时间。

- Max Langhof

---

这是一个有趣的方法。如果我错了，请纠正我，但似乎每次进行分解时，我都必须通过 auto flattenedTree = weightTrees; 复制整个树？如果 weightTrees 很大怎么办？或者如果分解是微不足道的（或非常简单），那么我仍然需要先复制整个树吗？ - Phil-ZXX

这只是一种简单的实现方式。如果你不需要保留原始对象，那么使用这种方式更好。如果你需要保留原始对象，但又想避免进行深度复制，那么你可以在实现时仅存储每个叶子节点的表达式，而不是整棵树的完整表示形式。 - Max Langhof

让我考虑一下。谢谢！ - Phil-ZXX

我也刚意识到由于无序映射擦除与添加元素的交互方式，那里仍然有一个错误。让我来修复它。编辑：已修复。 - Max Langhof

看一下之前我所提到的修复版本：您可以基本上存储所有计算出的 leafOnlyWeights 而不是修改原始值（并在修改原始值之前检查这些值）。但是，这可能会导致异常增长，因为您必须保留所有只有叶子节点的表示形式。我怀疑在这里没有逃脱内存与速度之间的权衡。 - Max Langhof

Answer 2

我建议您使用拓扑排序算法，然后再使用动态规划算法进行优化。使用Khan算法的标准版本可以在O(V+E)的时间内完成拓扑排序，您可以通过此链接找到标准的版本。在您的情况下，V是节点数，E是所有表达式中出现的项数。

如果排序失败，则表示发现了循环依赖关系。通过这种方式发现循环依赖问题比代码崩溃更好。

一旦您获得了排序结果，从末尾到前面使用动态规划非常简单。

另外，如果您真的关心性能，那么您的性能约束之一就是每个操作都使用字符串比较。随意使用大量字符串很容易且方便，这就是为什么脚本语言经常使用它们的原因。但是这也很慢。我过去发现在进入性能关键代码之前创建一个将字符串转换为索引的查找结构很值得，并且使用某种类型的int而不是字符串。然后在最后使用查找将其转换回字符串。

- btilly

---

你能详细解释一下你最后一个观点吗？unordered_map不是使用内部哈希结构来存储/查找键吗？你有关于你的“标准”查找结构的设置示例吗（用C++实现）？ - Phil-ZXX

在C语言中，字符串是字节数组，每个字符串操作都需要循环遍历它们。而在C++中，字符串是一个复杂的数据结构，字符串操作可能需要跟随指针到实际存储位置，然后进行循环操作。相比之下，比较整数是CPU内置操作，没有指针，也没有可变长度的循环，因此更快。对于字符串的哈希查找需要对字符串进行可变长度的循环来计算哈希值，然后进行类似的循环以查看是否在哈希表中找到相同的字符串。这比对整数进行哈希运算要慢。 - btilly

对于实现，您可以简单地创建一个节点向量，一个查找映射以查找字符串的索引，然后在代码中使用这些索引。但是，对于复杂的代码来说，这并不可维护。过去我通过创建小类来解决这个问题，这些小类具有从std :: string到对象实例的查找，具有方便的方法将字符串转换为表示该字符串的唯一对象的指针，然后在其他地方只需使用指针即可。现在类型系统防止我将东西弄混。 - btilly