Какую структуру данных я должен использовать для реализации UPGMA? - PullRequest
Новая
       26

Какую структуру данных я должен использовать для реализации UPGMA?

0 голосов
/ 18 мая 2018

Я собираюсь заранее извиниться, поскольку не знаю, как задать этот вопрос, иначе мой заголовок будет лучше.

Я пытаюсь реализовать алгоритм UPGMA из Википедии .Скажем, у меня есть вектор вектора целых чисел. 

std::vector<std::vector<int>> test = { {0},{1},{2},{3},{4},{5}}

Где целые числа представляют конкретную строку, которая есть в моей программе.Теперь, скажем, у меня есть определенный ввод, говорящий мне объединить test[0] и test[3] вместе, как только они объединены, мы отодвигаем объединенные векторы до конца и удаляем test[0] и test[3], которые выглядели бы какthis: 

test = { {1}, {2}, {4}, {5}, {0,3} }

Это легко достигается с помощью следующего фрагмента кода: 

int x = 0;
int y = 3;
merge = {test[x][0],test[y][0]}; // merge is a std::vector<int>
test.push_back(merge);
test.erase(test.begin() + x)
test.erase(test.begin() + y - 1); // -1 since the first erase shifts everything over

Проблема возникает, когда я хочу объединить test[1] и test[4].Желаемый результат будет выглядеть примерно так: 

test = { {1}, {4}, {5}, {2,{0,3} };

Вот где я столкнулся с проблемой, потому что, похоже, я сейчас ввел std::vector<std:vector<int>> в позицию 3 моего теста.И использование merge = {test[x][0],test[y][0]} не удастся.Это будет ухудшаться с течением времени.Поскольку у меня могло быть что-то, что потенциально могло бы выглядеть следующим образом: 

test = { {1}, {{4,5},{2,{0,3}}} }

Я думаю, что быстро осознаю, что у меня неправильная структура данных для этого, но я абсолютно не знаю, какую структуру данных мне нужно использоватьза это.Какую структуру данных я могу использовать, чтобы легко реализовать это?

Опять прошу прощения за плохой вопрос.

Ответы [ 2 ]

0 голосов
/ 18 мая 2018

Вы строите двоичное дерево.Каждый дочерний элемент является либо int, либо поддеревом.Это бесполезно моделируется в vector чего-либо. 

#include <vector>
#include <variant>
#include <memory>
#include <utility>

using Node = std::variant<std::shared_ptr<class Tree>, int>;

struct Tree {
    Tree(Node left, Node right) : left(left), right(right) {}
    Node left;
    Node right;
};

std::pair<std::vector<Node>::iterator, std::vector<Node>::iterator> decide_merge(const std::vector<Node> & v)
{
    // Some process to choose elements
    return { v.begin(), v.begin() + 1 };
}

int main()
{
    std::vector<Node> nodes = { {0}, {1}, {2}, {3}, {4}, {5} };
    while (nodes.size() > 1)
    {
        auto [left, right] = decide_merge(nodes);
        auto tree = std::make_shared<Tree>(*left, *right);
        nodes.erase(left);
        nodes.erase(right);
        nodes.push_back(tree);
    }
}
0 голосов
/ 18 мая 2018

Вы строите дерево здесь.Вероятно, лучше сделать это, создав новые узлы здесь.Поэтому, когда вы объединяете {0} и {3}, вы создаете новый узел со значением {0,3}.И если вы затем объедините {2}, вы создадите узел {2,0,3}.

В этот момент вы можете возразить и сказать, что вам нужна структура {2, {0,3}}.Это на самом деле не нужно, а на самом деле неэффективно.Вам нужна только структура в конце процесса.В этот момент вы можете восстановить дерево из того факта, что вы на самом деле не стерли старые узлы - вы просто отложили их в сторону.

Это в основном означает, что вам нужен второй вектор векторов.После того как вы создали {0,3}, вы перемещаете {0} и {3} в этот второй вектор.После того как вы создали {2,0,3}, вы добавляете {2} и {0,3} к этому второму вектору.

Конечно, это не самая эффективная реализация памяти.Второй вектор имеет размер O (N * N), поскольку он хранит каждый промежуточный узел дерева.Более эффективная реализация пространства будет состоять в том, чтобы заменить второй вектор векторов простым деревом, где конечные узлы имеют только одно значение, а неконечные узлы имеют только два дочерних указателя.Это дерево просто сохраняет структуру.

...