3
\$\begingroup\$

Previous question:

Rotate image 90 degree clockwise

In this code I have used tail recursive, which is bad. Time complexity is still \$O(N^2)\$, which is worse-case. The only good part is memory complexity.

How can I improve the recursive part of this code?

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

template<typename T>
using matrix = std::vector<std::vector<T>>;

// for debug info
static size_t numTotalSwaps = 0;

template<typename T>
matrix<T> rotateImage(matrix<T>&& image, size_t row = 0, size_t column = 0)
{
    if (row == image.size())
    {
        std::cout << "\nNumber of total swaps: " << numTotalSwaps << '\n';
        return image;
    }

    if ( ++column == image.size() )
    {
        std::reverse(image[row].begin(), image[row].end());
        ++row;
        column = 0;
    }

    if (row != column && row < column)
    {
        ++numTotalSwaps;
        std::swap(image[row][column], image[column][row]);
    }

    return rotateImage(std::move(image), row, column);
}

int main()
{
    const size_t SIZE = 7;

    matrix<int> image(SIZE, std::vector<int>(SIZE));

    std::cout << "******* original image ******\n";

    int value = 0;

    for (auto&& i : image)
    {
        for (auto&& j : i)
        {
            std::cout << std::setfill(' ') << std::setw(3) << (j = value++) << ' ';
        }

        std::cout << '\n';
    }

    std::cout << "******* rotated image ******\n";

    for (const auto& i : rotateImage(std::move(image)))
    {
        for (const auto& j : i)
        {
            std::cout << std::setfill(' ') << std::setw(3) << j << ' ';
        }

        std::cout << '\n';
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Why do you think tail recursion is bad? It's the kind that is easy to optimize out. One could argue that recursion in general is bad, but tail recursion is less bad than most. Also, why are you doing this recursively? Your previous solution was fine. All solutions that involve swapping the data are going to be at best \$O(N^2)\$ because there are \$N^2\$ pieces of memory to swap. If you want a better solution, you'll need to come up with one that doesn't involve swapping the data. \$\endgroup\$ – Brythan Dec 19 '14 at 5:36
  • \$\begingroup\$ i don't know i was viewing question for someone he has tail recursion and most of answers point that out as bad habit mush be avoided. thanks really i wish i had your comment. it would save my time. \$\endgroup\$ – MORTAL Dec 19 '14 at 5:43
  • \$\begingroup\$ A function named simply recursive? What does it do? \$\endgroup\$ – David K Dec 19 '14 at 6:54
  • \$\begingroup\$ @DavidK ... it swaps half of 2d array. it start from top-left and bottom-right and applying swapping until it reachs the diagonal axes (top-right - bottom-left). i know it must has proper name but i had this problem which is bothering me most. \$\endgroup\$ – MORTAL Dec 19 '14 at 7:19
  • \$\begingroup\$ @DavidK .. i updated code. \$\endgroup\$ – MORTAL Dec 19 '14 at 11:21
2
\$\begingroup\$

Nitpicks

using matrix = std::vector<std::vector<T>>;

The standard is to capitalize names of user defined types, so matrix should be Matrix. I may have misled you in my other review, so I edited it for clarity.

// for debug info
static size_t numTotalSwaps = 0;

While I understand that it can often be helpful to define a global variable to do some quick and dirty debugging, by the time that you are sending code out for code review, this should be gone. You should be done debugging your code, so you can leave just the actual code.

What I would actually like to see here are the results. Given a particular input, what is the output?

if (row == image.size())

This can be fragile.

if ( row >= image.size() )

By switching to the inequality, you can avoid a class of bugs where you start incrementing by more than one row at a time but don't update your gate condition. The check costs the same either way, so you might as well do the more expansive check.

if (row != column && row < column)

This is redundant. If row < column, then you know that row != column.

if ( row < column )

This is sufficient, as it covers both cases.

    std::reverse(image[row].begin(), image[row].end());
    std::swap(image[row][column], image[column][row]);

I find this harder to follow than just saying

    std::swap(image[row][column], image[image.size() - 1 - column][row]);

I'm not sure which performs better. It might be worth profiling if that matters to you.

    for (const auto& j : i)
    {
        std::cout << std::setfill(' ') << std::setw(3) << j << ' ';

I don't know what i and j are here.

    for ( const auto& element : row )
    {
        std::cout << std::setfill(' ') << std::setw(3) << element << ' ';

Now I can easily see what I'm printing. Using i and j didn't tell me what they actually were, but row and element do.

Move Semantics

matrix<T> rotateImage(matrix<T>&& image, size_t row = 0, size_t column = 0)
        return image;
    return rotateImage(std::move(image), row, column);
    for (const auto& i : rotateImage(std::move(image)))

This seems a bad place to use move semantics. Note that the point of move semantics is to avoid doing a copy when you don't need to do so. However, here it may create a copy that you don't need. Note that your algorithm passes an rvalue reference to the function but returns an lvalue. If each recursive call triggers a full copy on return, your algorithm goes from \$O(n^2)\$ to \$O(n^4)\$.

You might be able to fix this by saying

        return std::move(image);

This will turn the named variable image back into an rvalue reference.

We shouldn't need to pass by value inside the recursive function. We can work with the actual matrix. We need to make one copy at most to avoid changing the variable outside the function.

const Matrix<T> & rotateImage(Matrix<T> & image, size_t row = 0, size_t column = 0)
    return rotateImage(image, row, column);

And then insist outside

    Matrix<int> rotatedImage = std::move(image);
    for ( const auto& row : rotateImage(rotatedImage, 0, 0) )

This makes a more regular use of move semantics. If there is an assignment function that uses move semantics, this will just work.

We also enjoy the speed advantages of working with a reference when dealing with the recursive function. We don't have to worry if move semantics get used or not, as our function always passes a reference. We don't force the caller to use std::move, which is more commonly used with an assignment or copy constructor.

At the same time, I added the starting row and column numbers back. I don't think that the code will work without them. It looks like they got lost in an edit.

Recursion

The normal advantage of using recursion is that it allows for a more elegant solution. However, in this case, I don't think that it does. Your iterative solution traversed the grid smoothly and understandably. The recursive solution is more complex, as you have to transform the grid into a one dimensional object.

It's also problematic in that the caller has to understand more than it should about what's happening internally. It has to call std::move and add the initial row and column numbers. You can sort of fix this by providing two functions. The first function for use by the caller. The first function then calls the second function with the right arguments for the recursion. The second function does the actual work. Note that it makes sense for the second function to use references. The first function could pass by value. Calling with std::move would trigger move semantics on the copy constructor.

The problem with recursion is that it works by making use of the stack. For each function call, you have to push the current state onto the stack. However, most of the state doesn't change from call to call, so saving it is redundant. Further, since this is tail recursion, we're done with the current state by the time that we save it. A good compiler will optimize this out, but why not go ahead and do it yourself?

Rather than relying on the compiler to fix things, just write the iterative version. Tail recursion will have a natural transformation into an iterative solution. In this case, we can do even better. The recursive solution maps the grid into a vector. An iterative solution can work with a grid directly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.