Объединить std :: unordered_map итеративно - PullRequest
Новая
       51

Объединить std :: unordered_map итеративно

0 голосов
/ 22 октября 2018

У меня есть список узлов, каждый из которых разбивается на несколько узлов.Например,

  • Node0 = w01 * Node1 + w02 * Node2 + w03 * Node3

Следовательно,у нас есть 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}
}

Ответы [ 2 ]

0 голосов
/ 22 октября 2018

Я бы предложил выполнить топологическую сортировку с последующим алгоритмом динамического программирования. Стандартные версии топологического вида с использованием алгоритма Хана занимают время O(V+E).(Если эта ссылка устарела, вы можете просто использовать Google, чтобы найти другую.) В вашем случае V - это количество узлов, а E - это число терминов, которые встречаются во всех ваших выражениях.

Если сортировка не удалась, значит, вы нашли циклическую зависимость.Обнаружить его таким способом лучше, чем взорвать ваш код.

Как только вы это сделаете, переход с конца на передний план с DP будет очень простым.

Также, если выодно из ваших ограничений производительности заключается в том, что каждая операция выполняется с использованием сравнения строк.Бросать много строк легко и удобно - вот почему языки сценариев делают это постоянно.Однако это также медленно.В прошлом я считал целесообразным создать структуру поиска, которая превращает строки в индексы перед вводом кода, критичного для производительности, а затем разбрасывает некоторый тип int вместо строки.А затем в конце используйте поиск, чтобы превратить его обратно в строки.

0 голосов
/ 22 октября 2018

Основная проблема заключается в том, что вы рекурсивно обрабатываете для каждого узла до каждого подузла, что, как правило, сильно избыточно.Один из способов избежать этого - ввести порядок имен узлов, где «более высокие» узлы зависят только от «более низких» узлов, а затем вычислять их в обратном порядке (для каждого узла вы уже точно знаете все дочерние веса).Тем не менее, я не думаю, что есть 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;
}

Демо

Поскольку каждый узел выравнивается не более одного раза, вы не можете столкнуться с экспоненциальной средой выполнения вашего исходного алгоритма.

...