3
\$\begingroup\$

I am computing Nth element of the the sequence:

\$a_n=-2a_{n-1}+a_{n-2}+2a_{n-3}\$

Initial values are

  • \$a_1=-2\$
  • \$a_2=6\$
  • \$a_3=-8\$

Code

#include <iostream>
//#define NDEBUG
#include <cassert>
using namespace std;

struct Matrix
{
    int n, m;
    int* elements;

    int getElement(int r, int c) const
    {
        return elements[r*m + c];
    }
    void setElement(int r, int c, int e)
    {
        elements[r*m + c] = e;
    }
    void show() const
    {
        for (int i(0); i < n; ++i)
        {
            for (int j(0); j < m; ++j)
            {
                cout << getElement(i, j) << " ";
            }
            cout << endl;
        }
    }
    Matrix operator*(const Matrix& that)
    {
        Matrix res;
        res.n = n;
        res.m = that.m;
        res.elements = new int[n*m];

        for (int i(0); i < n; ++i)
        {
            for (int j(0); j < that.m; ++j)
            {
                int val(0);
                for (int k(0); k < m; ++k)
                {
                    val += getElement(i, k)*that.getElement(k, j);
                }
                res.setElement(i, j, val);
            }
        }

        return res;
    }
    Matrix operator^(const int& p) const
    {
        Matrix res;
        res.n = n;
        res.m = m;
        res.elements = new int[n*m];
        res.makeIdentity();

        Matrix k;
        k.copy(*this);

        int lP(p);

        while (lP)
        {
            if (lP & 1)
            {
                int* toBeDeleted = res.elements;
                res = res * k;
                delete[] toBeDeleted;
            }
            int* toBeDeleted = k.elements;
            k = k * k;
            delete[] toBeDeleted;
            lP >>= 1;
        }

        return res;
    }
    void makeIdentity()
    {
        for (int i(0); i < n; ++i)
        {
            for (int j(0); j < m; ++j)
            {
                if (i == j)
                {
                    setElement(i, j, 1);
                }
                else
                {
                    setElement(i, j, 0);
                }
            }
        }
    }
    void copy(const Matrix& that)
    {
        n = that.n;
        m = that.m;
        elements = new int[n*m];

        for (int i(0); i < n; ++i)
        {
            for (int j(0); j < m; ++j)
            {
                setElement(i, j, that.getElement(i, j));
            }
        }
    }
};

void prepareMatrix(Matrix&);
void prepareRow(Matrix&);

int fastSequence(const int&);
int sequence(const int&);

int main(void)
{
    for(int i(1); i < 20; ++i)
    {
        assert(sequence(i) == fastSequence(i));
    }
    return 0;
}

void prepareMatrix(Matrix& m)
{
    m.n = 3;
    m.m = 3;
    m.elements = new int[m.m*m.n];

    for (int i(0); i < m.n; ++i)
    {
        for (int j(0); j < m.m; ++j)
        {
            m.setElement(i, j, 0);
        }
    }

    m.setElement(0, 2, 2);
    m.setElement(1, 2, 1);
    m.setElement(2, 2, -2);
    m.setElement(2, 1, 1);
    m.setElement(1, 0, 1);
}
void prepareRow(Matrix& row)
{
    row.n = 1;
    row.m = 3;
    row.elements = new int[row.n*row.m];
    row.setElement(0, 0, -2);
    row.setElement(0, 1, 6);
    row.setElement(0, 2, -8);
}
int fastSequence(const int& n)
{
    Matrix m;
    prepareMatrix(m);

    Matrix row;
    prepareRow(row);

    int* toBeDeleted = row.elements;
    int* toBeDeleted2 = m.elements;

    if (n < 4)
    {
        int res(row.elements[n-1]);
        delete[] toBeDeleted;
        delete[] toBeDeleted2;
        return res;
    }

    m = m ^ (n - 3);
    int* toBeDeleted3 = m.elements;
    Matrix resRow = row*m;
    int* toBeDeleted4 = resRow.elements;
    int res(resRow.getElement(0, 2));
    delete[] toBeDeleted;
    delete[] toBeDeleted2;
    delete[] toBeDeleted3;
    delete[] toBeDeleted4;

    return res;
}


int sequence(const int& n)
{
    int val[] = { -2, 6, -8 };

    for (int i(3); i < n; ++i)
    {
        val[i % 3] = -2 * val[(i - 1) % 3] + val[(i - 2) % 3] + 2 * val[i % 3];
    }

    return val[(n - 1) % 3];
}

Concerns

  • Performance

  • Code clairty

  • General code quality

\$\endgroup\$
  • \$\begingroup\$ I've reformatted the post and added some generic concerns. If they conflict with yours feel free to edit. Also, please follow the format I've used the next time. If you want to add some more info, like why you used matrix, or if you're using it all (e.g. the implementation path you've chosen), please add it. \$\endgroup\$ – Incomputable Nov 22 '17 at 17:36
  • \$\begingroup\$ This Matrix code is violating nearly every single rule in computer science in general and in c++ especially. It is not possible to do a review within a reasonable amount of time that would fix the code and teach you the reasoning. it would take a complete course, I'm sorry. i cannot think of any other way to do such code than generating an exam question. surprisingly there is a piece of code at the end that has a very different style. \$\endgroup\$ – stefan Nov 22 '17 at 21:32
  • \$\begingroup\$ I think that the approach of calculating a₄, a₅, ... etc is particularly inefficient. Instead, you should use your mathematical knowledge to transform the recurrence relationship into closed form, allowing you to compute any term in O(1) time. \$\endgroup\$ – Toby Speight Nov 24 '17 at 10:35
  • \$\begingroup\$ @TobySpeight, how can I tronsform the recurrence relationship into a closed form? \$\endgroup\$ – trafalgarLaww Nov 24 '17 at 10:53
  • \$\begingroup\$ That's a mathematical question, not a programming one. (In other words, I can no longer remember, as it's so long since I've done it - but you may find hints in Wikipedia or Mathematics.SE). \$\endgroup\$ – Toby Speight Nov 24 '17 at 11:09
2
\$\begingroup\$

For the most part, I can tell what most of this code is supposed to do. That's a good start. I do have a few issues with how things are implemented, so let's dive in and take a look.

Don't Use using namespace std

You should avoid using namespace std. This SO question has good information on why it's generally a bad idea.

RUGNI?

There's a principle that some developers subscribe to called YAGNI - You Aren't Going to Need It. It says that if you aren't using some functionality in this version of the app, don't write code to support it because there's a good chance you won't end up needing it in the future. My personal experience does not bear this out, so I've changed it to RUGNI - aRe yoU Going to Need It?

The reason I bring this up is that you've written a very general matrix class with 2 specific operators - multiplication and exponentiation. But you only ever use it for a 3x3 matrix and a 1x3 matrix. You do a lot of allocation and deletion, which tends to be tricky when done manually. If you're going to use this class for other matrix work, then it's fine to leave it as general as it is, but if you're not, you might be better off having 2 simpler classes - Matrix3x3 and Vector3 for the 2 cases you actually use. You'd need to add a vector-matrix multiply function or method, but I think the payoff would be worth it. You'd eliminate the funky math for figuring out which 2D element maps to which 1D element in the array you've allocated. You could just make a real 2D array and access elements using subscripts.

So are you going to need to use any matrix shape besides 3x3? If not, then simplify the code. If so, then it can work the way you have it.

RAII

One of the most common idioms in C++ is RAII - Resource Acquisition Is Initialization. The gist of it is that when you allocate an object and construct it, it should be a completely initialized object and the lifetime of the data members (resources) should be the concern of the object. You're code does neither of those things and it will likely lead to bugs when using it.

First, notice how you didn't write any constructors or a destructor for the Matrix class. Instead you have separate functions like prepareMatrix() and prepareRow() which a user of the class has to know to call. Most matrix classes I've used have a constructor that does something like this:

Matrix::Matrix(int numRows, int numCols, int defaultValue = 0)
{
    m = numRows; // OR have I reversed m and n?
    n = numCols; 
    elements = new int [ m * n ];
    for (int i(0); i < n; ++i)
    {
        for (int j(0); j < m; ++j)
        {
            setElement(i, j, defaultValue);
        }
    }
}

If you know you'll always have a square matrix, it would be better to initialize to identity.

Then, in the destructor, you'd need to delete the elements array:

Matrix::~Matrix()
{
    delete [] elements;
}

Notice how the object takes care of its own data. The way your code is written, someone else is deleting the data that belongs to the object. In fastSequence(), if you try to access any of the Matrix objects after the calls to delete [], they'll be invalid. This is a very dangerous situation.

Furthermore, C++ has the concept of a copy constructor where you pass in an existing instance and its member data is copied. You should use that (or operator=()) to copy rather than having a copy() method.

Naming

You should name variables and functions based on what they do. I can live with operator^() even though C++ doesn't use ^ as the exponentiation operator. (I don't think it ever makes sense to XOR a matrix, so there's unlikely to be confusion.) But I would recommend using more descriptive names elsewhere.

In the Matrix class you have n and m. Which is rows and which is columns? I've read hundreds of articles and text book examples of matrices, and I honestly don't remember the convention off the top of my head. You should just name them something like rows and cols so there's no confusion possible.

While i and j are somewhat standard for loop variables, it's easy to get them confused when reading or writing code. It also doesn't tell which they are working on. You should just name them row and col.

But by far, the worst offenders are toBeDeleted, toBeDeleted2, etc. That tells me absolutely nothing about how they are used. Everything will be deleted eventually, so it's useless as a name. What do those things represent in the calculation you're doing? It turns out it doesn't represent anything related to the calculation. And since it's data that should be owned by the object (and should probably be private), it should be deleted by the object's destructor and should not be known to a free function like fastSequence().

Performance

Constantly allocating and deleting can be a drain. In your operator^() method you're allocating and deleting up to 2 times per iteration. That's likely to be a performance bottleneck. (And again, if you were only using a fixed size, there'd be no need for any allocation and deletion.)

You're also creating more Matrix objects than you need. If you had an operator*=() method, you could do the multiplication and assignment at once saving you several array creations.

\$\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.