Codewars – optymalizacja kodu podającego piksele ze środka obszaru o zadanym kolorze

Witam,

Mocuję się z jednym zadaniem na Codewars. Program ma podawać piksele ze środka obszaru o zadanym kolorze.
Kod poniżej działa jak trzeba, ale nie przechodzi "Big Tests" czyli 16 Mpx obrazka (przekracza dozwolone 12s czasu wykonywania).
W jaki sposób mogę go zoptymalizować ? Czy muszę wyrzucić tworzenie matrycy i sprawdzać piksele wskaźnikiem ?

Link do zadania: https://www.codewars.com/kata/centre-of-attention

#include <algorithm>
#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

struct myImage
{
     vector<vector<unsigned>> matrix;
     vector<unsigned> shortest_route, ret_vector;
     unsigned width, height, *pixels, color, max_depth = 0;

     myImage(const unsigned &w, const unsigned &h, unsigned *p, const unsigned &c) : width(w), height(h), pixels(p), color(c)
     { }

    void conjure_up_matrix();
    vector<unsigned> central_pixels(unsigned colour);
    void assert_depth();
    unsigned find_depth(const int &row, const int &col);
    inline bool is_outof_bounds(const int &row, const int &col, const int &steps);
    inline void get_depth_linear_directions(const int &row, const int &col);
    inline int get_depth_sides(const int &row, const int &col, const int &max_steps);
};

void myImage::conjure_up_matrix()
{
    unsigned col = 0;
    unsigned row = 0;

    this->matrix.resize(this->height, vector<unsigned>(this->width, 0));
    for(unsigned i = 0; i < this->width*this->height; i++)
    {
        if(col >= this->width)
        {
            row++;
            col = 0;
        }
        this->matrix[row][col++] = pixels[i];
    }
}

vector<unsigned> Image::central_pixels(unsigned colour) const                                     /// funkcja z innej struktury (zdef. przez autora zadania)
{
    myImage myImg(this->width, this->height, this->pixels, colour);
    myImg.conjure_up_matrix();
    myImg.assert_depth();
    return myImg.ret_vector;
}

void myImage::assert_depth()
{
    this->shortest_route.reserve(200);
    unsigned p_pos, p_depth, row=0, col=0;

    for(unsigned *i = this->pixels, j=1; i<&this->pixels[this->width*this->height]; i++, j++)
    {
        if(*i == this->color)
        {
            p_pos = j-1;
            p_depth = this->find_depth(row, col);

            if(this->max_depth == p_depth)
                this->ret_vector.emplace_back(p_pos);
            else if(this->max_depth < p_depth)
            {
                this->max_depth = p_depth;
                this->ret_vector.clear();
                this->ret_vector.emplace_back(p_pos);
            }
        }
        if(j%this->width == 0)
        {
            row++;
            col=-1;
        }
        col++;
    }
}

inline void myImage::get_depth_linear_directions(const int &row, const int &col)
{
    int steps = 1;

    while(!is_outof_bounds(row, col, steps) && this->matrix[row-steps][col] == this->color &&
    this->matrix[row][col+steps] == this->color && this->matrix[row+steps][col] == this->color && this->matrix[row][col-steps] == this->color)
        steps++;

    if(this->get_depth_sides(row, col, steps) > 0)
        this->shortest_route.emplace_back(this->get_depth_sides(row, col, steps));

    this->shortest_route.emplace_back(steps);
}

inline int myImage::get_depth_sides(const int &row, const int &col, const int &max_steps)
{
    for(int i=1; i<max_steps-1; i++)
    {
        for(int j=1; j<max_steps-1; j++)
        {
            if(this->matrix[row-i][col+j] != this->color ||
                this->matrix[row-i][col-j] != this->color ||
                this->matrix[row+i][col+j] != this->color ||
                this->matrix[row+i][col-j] != this->color ||
                this->matrix[row-j][col+i] != this->color ||
                this->matrix[row+j][col+i] != this->color ||
                this->matrix[row-j][col-i] != this->color ||
                this->matrix[row+j][col-i] != this->color)
                    return i+j;
        }
    }
    return 0;
}

unsigned myImage::find_depth(const int &row, const int &col)
{
    this->shortest_route.clear();
    get_depth_linear_directions(row, col);
    sort(this->shortest_route.begin(), this->shortest_route.end());
    if(this->shortest_route.size() > 0)
        return this->shortest_route.front();
    else
        return 0;
}

inline bool myImage::is_outof_bounds(const int &row, const int &col, const int &steps)
{
    if(row-steps < 0 || col-steps < 0 || row+steps >= this->height || col+steps >= this->width)
        return true;
    else
        return false;
}

PS: kolorowanie składni wstawiłem jako c#. W jaki sposób zaznaczyć kod jako "c++" ?

Odpal se profiler.

1. Po co marnować czas na kopiowanie obrazka?
2. sort po kiego grzyba?

Złożoność twojego kodu (zakładam n=width=heigth):

• assert_depth - o(n * n * zlozonosc(find_depth))
• find_depth - o(n log(n)) (bo pesymistyczna długość shortest_route jest proporcjonalna do w lub h) lub równa złożoności get_depth_linear_directions, zależnie co większe.
• get_depth_linear_directions nie wiem jaki wpływ pętla while ma na złożoność (załóżmy x), ale ważniejsze jest to, że w środku wywołujesz get_depth_sides, które ma złożoność o(steps*steps) co w pesymistycznym przypadku jest proporcjonalne do n

To daje mi złożoność około o(n^4) (w najlepszym wypadku o(n^3 log(n))) co jest bardzo źle, bo do głowy od razu przychodzi algorytm o złożoności o(n^2).

Jak ja bym to zrobił.
Najpierw tak:

std::vector<int> deptMatrix;
auto maxSteps = std::min(width, heigth) / 2;
deptMatrix.reserve(width * heigth);
std::transform(pixels, pixels + width * heigth, 
               std::back_inserter(deptMatrix), 
               [color, maxSteps](auto x) { return x == color ? maxSteps : 0; } );

Potem iterować od lewej do prawej tak by kolejne komórki się zwiększały o jeden, ale tylko wtedy gdy obecna wartość jest większa od nowo nadanej.
Potem to samo w od prawej do lewej, od góry do dołu, od dołu do góry.
Znaleźć maksimum i wszystkie jego wystąpienia.
Wszystkie kroki występują po sobie i mają złożoność o(n^2), więc całość też ma taką złożoność.

Dzięki za te uwagi.
Spróbuję poprawić całość zgodnie z Twoimi wytycznymi.

Z ciekawości przetestowałem swoje rozwiązanie, przeszło bez problemu.

Hej,
nie do końca ogarniam problem, ale możnaby w sumie próbować operować na obszarach wyznaczonych przez punkty będące wierzchołkami danych prostokątów, (w sumie chyba dwa wystarczą). przykład (sorry Python), domyślny kolor, np. "w": "white", "y": "yellow":

a = [10*["w"] for i in range(10)]
V={}
V["y"] = [[(1, 3), (4, 5)], [(7, 8), (8, 9)]]

Czyli obszar wyglądałby tak:

w  w  w  w  w  w  w  w  w  w
w  w  w  y  y  y  w  w  w  w
w  w  w  y  y  y  w  w  w  w
w  w  w  y  y  y  w  w  w  w
w  w  w  y  y  y  w  w  w  w
w  w  w  w  w  w  w  w  w  w
w  w  w  w  w  w  w  w  w  w
w  w  w  w  w  w  w  w  y  y
w  w  w  w  w  w  w  w  y  y
w  w  w  w  w  w  w  w  w  w

Napiszcie co o tym myślicie ??

#include <algorithm>
#include <iterator>

class CentralPixelsSolver
{
public:
    CentralPixelsSolver(const unsigned *pixels,
                        unsigned width,
                        unsigned height)
        : pixels(pixels)
        , width(width)
        , height(height)
    {}
    
    std::vector<unsigned> central_pixels(unsigned color) {
        setupDistances(color);
        trimDistancesFromLeft();
        trimDistancesFormRigth();
        trimDistancesFormTop();
        trimDistancesFormBottom();
        
        return maxDistancesPositions();
    }
    
private:
    void setupDistances(unsigned color)
    {
        distances.clear();
        distances.reserve(width * height);
        
        auto maxDistance = (1 + std::min(width, height)) / 2;
        
        std::transform(pixels, pixels + width * height,
                       std::back_inserter(distances),
                       [color, maxDistance](auto x) {
                           return x == color ? maxDistance : 0;
                       });
    }
    
    void trimDistancesFromLeft()
    {
        for (size_t row = 0; row < height; ++row) {
            trimDistances(distances.begin() + row * width, 1, width);
        }
    }
    
    void trimDistancesFormRigth()
    {
        for (size_t row = 0; row < height; ++row) {
            trimDistances(distances.begin() + row * width + width - 1,
                          -1,
                          width);
        }
    }
    
    void trimDistancesFormTop()
    {
        for (size_t column = 0; column < width; ++column) {
            trimDistances(distances.begin() + column, width, height);
        }
    }
    
    void trimDistancesFormBottom()
    {
        auto it = distances.begin() + width * (height - 1);
        for (size_t column = 0; column < width; ++column) {
            trimDistances(it + column, -width, height);
        }
    }
    
    using Container = std::vector<unsigned>;
    
    void trimDistances(Container::iterator it,
                       int toNextOffset,
                       size_t count)
    {
        unsigned distance = 0;
        for (size_t i = 0; i < count; ++i)
        {
            ++distance;
            if (distance < *it) {
                *it = distance;
            } else {
                distance = *it;
            }
            std::advance(it, toNextOffset);
        }
    }
    
    std::vector<unsigned> maxDistancesPositions() const
    {
        auto it = std::max_element(distances.begin(), distances.end());
        auto maxDist = *it;
        if (maxDist == 0) return {};
        
        std::vector<unsigned> result;
        result.reserve(0x100);
        while (it != distances.end())
        {
            result.push_back(std::distance(distances.begin(), it));
            it = std::find(it + 1, distances.end(), maxDist);
        }
        
        return result;
    }
    
private:
    const unsigned *const pixels;
    const unsigned width;
    const unsigned height;
    Container distances;
};

vector<unsigned> Image::central_pixels(unsigned colour) const
{
    CentralPixelsSolver solver{ pixels, width, height };
    return solver.central_pixels(colour);
}

Dzięki, nie wklepuję jako gotowca - wierzę że działa, ale teraz mam co analizować :) Czy możesz jeszcze napisać krótko o złożoności Twojego kodu ? Zawsze mi się wydawało, że dużo pętli to duża złożoność... Pewnie to kwestia ich zagnieżdżenia (?)