Производительность c Союз-++ найти решение, как это ни странно, бедные


Проблема резюме (USACO Gold на 3 февраля 2016 года)

Дана прямоугольная координатная плоскость измерений (A,B)есть N вертикальных перегородок, и M горизонтальные заборы. Ясно, что пересечение этих заборов в большом прямоугольнике создает (n+1)(m+1) регионы.

Учитывая A,B,N,Mх-координаты N вертикальные заборы и y координаты M горизонтальные заборы, найдите минимальное количество забора, чтобы удалить, чтобы создать минимальное остовное дерево (подключиться все регионы). Для того, чтобы убрать забор и, таким образом, союз двух соседних регионов, по всей длине забора между ними должны быть удалены.

Решение

Это явно непересекающиеся проблему Союза (Союз-найти/Kruskals), но самая сложная часть-это здание края-список и дерево Союза. Каждое ребро-это взвешенный по длине забора между двух вершин, которые она соединяет.

Вот краткий набросок ниже код:

  1. Читал в X и y координаты вертикальных, горизонтальных ограждений (добавить 0,0,а,в качестве "ограды")

  2. Для каждого пересечения заборов (в некоторых особых случаях на концах), добавить в левую сторону и вверх-перед края до края список, а также добавить в области между двумя кромками в качестве узла Союза-найти дерево.

  3. Запустить Kruskals, отслеживания расстояния.

Этот алгоритм за o(ElogV), которые должны быть более чем достаточно быстро, так как n и M не менее 2000. Обратите внимание, что данное решение (ссылка выше) работает достаточно быстро, где это нужно слишком много времени (отказа) за последние 4/10 тестов.

Скачать Тестовые Случаи (10)

Где производительность? Как это может быть улучшено?

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

#define ll long long

using namespace std;

const string PROJ_NAME = "fencedin";

struct edge {
    ll dist;
    int start;
    int finish;
    bool operator< (const edge &rhs) const { return dist < rhs.dist || (!(rhs.dist < dist) && start < rhs.start) || (!(rhs.start < start) && finish < rhs.finish); }
};

struct uf_node {
    int parent;
    int level;
};

ll A, B;
int N, M;
set<edge> edge_list;
vector<uf_node> tree;

void make_edge_list(ifstream &fin){
    fin >> A >> B >> N >> M;

    vector<int> vert(N+2);
    vert[0] = 0;
    for(int i = 1; i<=N; i++) fin >> vert[i];
    vert[N+1] = A;
    N++;

    vector<int> hori(M+2);
    hori[0] = 0;
    for(int i = 1; i<=M; i++) fin >> hori[i];
    hori[M+1] = B;
    M++;

    sort(vert.begin(), vert.end());
    sort(hori.begin(), hori.end());

    tree.resize(N*M);
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=M; j++){
            int curr = (i-1)*M+(j-1);

            //Add node to DSU tree
            uf_node n = {.parent = curr, .level = 0};
            tree[curr] = n;

            //Add leftward edge if not at bottom
            if(i != N){
                edge left = {.dist = hori[j]-hori[j-1], .start=curr, .finish=curr+M};
                edge_list.insert(left);
            }

            //Add upward edge if not at right
            if(j != M){
                edge up = {.dist = vert[i]-vert[i-1], .start=curr, .finish=curr+1};
                edge_list.insert(up);
            }
        }
    }
}

int find_par(int i) {
    if(i != tree[i].parent) {
        tree[i].parent = find_par(tree[i].parent);
    }
    return tree[i].parent;
}

void do_union(int i, int j) {
    int r = find_par(i);
    int s = find_par(j);
    if(r == s) return;
    else if (tree[r].level > tree[s].level) {
        tree[r].parent = s;
    } else if (tree[s].level > tree[r].level) {
        tree[s].parent = r;
    } else {
        tree[r].parent = s;
        tree[r].level += 1;
    }
}

int main()
{
    ifstream fin (PROJ_NAME + ".in");
    ofstream fout (PROJ_NAME + ".out");

    make_edge_list(fin);

    int total_dist = 0;
    for(edge e: edge_list){
        if(find_par(e.start) != find_par(e.finish)){
            do_union(e.start, e.finish);
            total_dist += e.dist;
        }
    }

    fout << total_dist << endl;
    return 0;
}


Комментарии
1 ответ

Это очень интересная проблема! Вот некоторые вещи, которые я заметил о своей реализации.

Производительности

Смотрю на профиль ваш код (откомпилированный с помощью LLVM на высокой Сьерра с Xcode и macOS 9.2), похоже, большинство времени провел в этих 3 местах:


  • 85% в make_edge_list(), в частности, 2 звонка set::insert()

  • 7% в find_par()

  • 7% в std::tree::iterator::operator++() (Так что увеличиваем итератор на список, я считаю)

Что это означает, Я думаю, что std::set может быть, не самый лучший выбор контейнера в этом случае. Поскольку вы не можете выделить место для пользования в set как можно с vector или arrayон должен делать отчисления на лету, которые могут снизить производительность. Также, выбирая, куда вставить вещи, кажется, быть частью времени раковины insert() как хорошо. С vector вы можете выделить память, а потом push_back() просто добавляет его в конец. Не понятно, что вы получаете с помощью set вот, вот и я говорю, брось ее. Связанное решение использует только один vector и статический массив из ~2000 х 2000 элементов и сортировка. Так что может быть выигрышной стратегии здесь.

Именования

Макросы имеют все виды проблем. Но даже когда вам удастся написать макрос, который не будет иметь каких-либо из этих проблем, как вы сделали здесь, Если есть способ лучше, вы должны использовать его. (Например, если кто-то изменив этот код создает переменную с именем ll или записывает строку со словом "все" в нем?) Если вы хотите иметь свое название покороче long longтогда сделать:

using ll = long long;

или, по крайней мере:

typedef long long ll;

Но на самом деле - лень типа long long? Просто введите его. Это известный тип.

Я не фанат 1-буквы имена переменных в большинстве случаев. Значения A и B размеры. Я бы назвал их width и height. N и M количество вертикальных и горизонтальных ограждений, так почему бы их не назвал num_vert_fences и num_horz_fences? Или даже просто rows и columns?

Избежать using namespace std

Вы действительно должны избегать использования using namespace std по всем причинам, указанным там.

Глобалс

Использование глобальных переменных затрудняет чтение кода. В do_union()мне приходилось прокручивать весь путь обратно до верхней части файла, чтобы увидеть, какой тип tree был. Вы должны определить эти переменные в main() и передать их функции, которые их используют. Это будет сделать это намного легче разобраться в потоке программы и избежать проблем, когда некоторые функции изменения переменной вы не прошли его, пока вы используете ту же самую переменную в другую функцию.

Я уже говорил в мой комментарий, что глобалы облажался мой анализ производительности. Это отличный пример непреднамеренных последствий глобалс. Потому что код был запущен слишком быстро для анализа, я взял main()переименовал ее main2()и потом написала новое main() для того, чтобы просто назвать его 100 раз в цикле. А потому, что tree и edge_list являются глобальными, они не очищены, когда main2() выходили, как они бы, если бы они были местные. Так, что приводили цифры мой анализ быть неверным, поскольку контейнеры могут иметь различные характеристики, когда есть много больше деталей, чем когда меньше. Урок. Я должен был сделал локальных переменных до выполнения моих тестов производительности.

Будьте осторожны с менее известными инструментами

Мне очень нравится этот способ инициализации членов struct или union:

uf_node n = {.parent = curr, .level = 0};

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

5
ответ дан 30 января 2018 в 04:01 Источник Поделиться