Сокращение времени расчета алгоритма кластеризации - PullRequest
Новая
       9

Сокращение времени расчета алгоритма кластеризации

0 голосов
/ 26 июня 2018

Я написал небольшой код, который группирует области пола на карте. Это работает хорошо, однако я хотел бы оптимизировать время вычислений. Есть ли у вас какие-либо советы по сокращению времени вычислений?

Идея оптимизировать алгоритм состояла в том, чтобы использовать только один вектор для кластеров и проходить все пиксели только один раз.

Алгоритм работает следующим образом: он сканирует все ячейки, начиная с верхнего левого угла и анализируя каждую строку за другой. Если ячейка обнаружена как этаж, она анализирует соседние объекты слева и определяет, принадлежит ли один из них к кластеру. В этом случае назначается тот же номер кластера, если нет, то назначается новый номер кластера. Если два соседних узла имеют разные номера кластеров, они объединяются вместе с помощью операции «замена». 

   std::vector<int> PathPlanning::clustering(){
        const int unknown = -1;
        int clusterCount = 0;
        std::vector<int> clusters(m_map.size(), unknown);
        for (size_t i = 0; i < clusters.size(); ++i) {
            if(m_map.at(i) != e_mapState::FLOOR)
                continue;

            for(auto& nb : neighborLeft(i)) {
                if(clusters.at(nb)!= unknown){
                    if(clusters.at(i) == unknown){
                        clusters.at(i) = clusters.at(nb);
                    }else{
                        std::replace (clusters.begin(), clusters.end(), clusters.at(nb), clusters.at(i));
                    }
                }
            }
            if(clusters.at(i) == unknown){
                clusterCount+=1;
                clusters.at(i) = clusterCount;
            }
        }

        return clusters;
    }

1 Ответ

0 голосов
/ 01 июля 2018

Это похоже на проблему непересекающегося множества , где время выполнения составляет O (α (n)), O (1) на практике для каждого элемента, поэтому O (n α (n)), O (n) на практике.

Где ваш код O (n соседей n), n и соседей для циклов и дополнительный n для замены.

Также имеется некоторый код повышения , так что вы можете сэкономить время на его реализацию.

...