5
\$\begingroup\$

I have a solution to the puzzle at https://kattis.csc.kth.se/problem?id=codes. What can I do to make my algorithm much much faster? What the algorithm does is take an N×K matrix and search for the minimum distance — that is, the least number of 1 for all the products of the matrix and a vector that ranges from 00001 to 11111 (where the top is 2K - 1).

#include <iostream>

using namespace std;

void DataEntry(int &a, int &b, int** &matrix) {

    cin >> a >> b;

    matrix = new int*[a];

    for (int i = 0; i < a; i++) {
        matrix[i] = new int[b];
    }

    for (int i = 0; i < a; i++) {
        for (int j = 0; j < b; j++) {
            matrix[i][j] = -1;
            cin >> matrix[i][j];
        }
    }

}

int* BinaryAdd(int* a, int* b, int tam) {
    int* c;
    int ac = 0;
    c = new int[tam];

    for (int i = tam - 1; i > -1; i--) {
        c[i] = a[i] + b[i] + ac;
        if (c[i] == 2) {
            c[i] = 0;
            ac = 1;
        } else
            ac = 0;
    }

    return c;
}

int* MultiplyMatrices(int** a, int* b, int tamF, int tamC) {
    int * c;
    c = new int[tamF];
    for (int i = 0; i < tamF; i++) {
        c[i] = 0;
        for (int j = 0; j < tamC; j++) {
            c[i] = c[i] + (a[i][j] * b[j]);
            c[i] = c[i] % 2;
        }
    }
    return c;
}

int MinimumDistance(int* a, int tam) {
    int MD = 0;

    for (int i = 0; i < tam; i++) {
        if (a[i] == 1)
            MD++;
    }
    return MD;
}

int pot(int a, int b) {
    int c = 1;
    for (int i = 1; i < b + 1; i++) {
        c = a * c;
    }
    return c;
}

int main() {
    int t = 0, n = 0, k = 0, d = -1, max = -1;
    int ** lecc;
    int * pro;
    int * sal;
    int * sol;
    int * zero;
    int * uno;
    int * pro1;

    cin >> t;

    for (int p = 0; p < t; p++) {

        DataEntry(n, k, lecc);

        pro = new int[k];
        uno = new int[k];
        sal = new int[n];
        zero = new int[n];

        for (int i = 0; i < k; i++) {
            pro[i] = 0;
        }
        for (int i = 0; i < k - 1; i++) {
            uno[i] = 0;
        }
        uno[k - 1] = 1;

        for (int i = 0; i < n; i++) {
            zero[i] = 0;
        }

        pro1 = BinaryAdd(pro, uno, k);

        pro = pro1;

        max = pot(2, k);

        sal = MultiplyMatrices(lecc, pro, n, k);

        d = MinimumDistance(sal, n);

        for (int i = 0; i < max - 1; i++) {

            sal = MultiplyMatrices(lecc, pro, n, k);

            pro1 = BinaryAdd(pro, uno, k);

            pro = pro1;

            int ad = MinimumDistance(sal, n);

            if (ad < d)
                d = ad;
        }
        cout << d << endl;
    }

}

Edit: I give you a sample input and output

Sample input     Sample output
2
7 4
1 0 0 0
0 1 0 0
0 0 1 0           3
0 0 0 1           0
0 1 1 1
1 0 1 1
1 1 0 1
3 2
1 1
0 0
1 1 
\$\endgroup\$
  • \$\begingroup\$ Can you give an example matrix and desired output? \$\endgroup\$ – Quentin Pradet May 23 '13 at 6:33
  • \$\begingroup\$ Can I divide the problem in thread? Is possible that? \$\endgroup\$ – Trouner May 23 '13 at 10:09
  • 1
    \$\begingroup\$ This is the problem in case it helps kattis.csc.kth.se/problem?id=codes \$\endgroup\$ – Trouner May 24 '13 at 13:03
  • 1
    \$\begingroup\$ Sure, it's always possible to get some improvement with threading, but those problems are designed to be only solvable with the correct, non-naive algorithm. \$\endgroup\$ – Quentin Pradet May 24 '13 at 13:56
  • \$\begingroup\$ It seems like you are using a very brute force approach. Have you thought about using another algorithm instead of optimizing your algorithm? \$\endgroup\$ – toto2 Sep 21 '13 at 13:33
6
\$\begingroup\$

Considering that this is meant to be a puzzle, I'll write my review as a sequence of escalating hints.

  1. Everybody who is suggesting the use of threads or std::vector or matrix libraries is on the wrong track! How do you think error correction is implemented in your CD player or hard disk firmware? No threads or matrix libraries there, I assure you.
  2. Don't simulate the computer; use the computer.
  3. All operations are modulo 2. The puzzle guarantees k ≤ 16. Under these conditions, you can massively parallelize vector dot products. (Think SIMD or AltiVec, except you don't need SIMD or AltiVec.)
  4. I've added the tag to this question.

I'll conclude with a remark that you've basically written C code. The only thing that makes it C++ is your use of iostream. C++ can be much more expressive than that.

\$\endgroup\$
  • \$\begingroup\$ You may eventually find this handy. \$\endgroup\$ – 200_success Sep 22 '13 at 19:10
3
\$\begingroup\$

I would consider use the Eigen library for matrix stuff. It is already optimized for that.

Next consider using higher level contains instead of plan arrays. std::vector is a good choice. For a quick example of how std::vector will improve the run time consider pro, uno, sal, and zero. Right now they are all not efficient because your making a OS level requires for memory over and over. Instead create an std::vector and reserve the size you want if you know it in advance then simple clear the vector at the beginning of the loop and reuse the memory.

Also your code is leaking memory like crazy. Stop using pointers Stop using new[] without delete [].


I'm happy to hear you made a 7% improvement, but you missed the other parts of my suggestion.

int main(int argc, char *argv[]) {
    int t=0, n=0, k=0, d=-1, max=-1;
    vector< vector<int> > lecc(n, vector<int>(k));
    cin >> t;
    vector<int> sal; 
    vector<int> uno;
    vector<int> pro;
    vector<int> pro1;
    //if you have an idea what the max capacity will be use `std::vector::reserve()`
    //This will avoid the time consuming task of allocating more capacity.

    for(int p=0; p<t; p++){

        lecc = EntradaDatos(n, k);
        //by resizing you might avoid a possible allocation of new space which 
        //will saves alot of time.
        sal.resize(n, 0);
        uno.resize(k, 0);
        pro.resize(k, 0);
        pro1.resize(k, 0);

The first suggestion was to use Eigen for the matrix but if that's not possible consider using a 1D array implementation of a matrix. Here is an example array_2D using one vector. This will avoid page faults for small matrix which gives nice speed ups. Note this is limited to about 2GB(std::vector::max_size()) capacity. If your matrix need more than 2GB capacity this will not work.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much I will try to rewrite all the code using the vector. \$\endgroup\$ – Trouner May 23 '13 at 6:09
  • \$\begingroup\$ How would std::vector bring better performance? Of course they're more idiomatic C++ but saying they will solve the performance problem isn't helpful. \$\endgroup\$ – Quentin Pradet May 23 '13 at 6:31
  • \$\begingroup\$ I've modified the code and only drops from 0,53s to 0,491s so the change isn't very helpful \$\endgroup\$ – Trouner May 23 '13 at 9:50
  • \$\begingroup\$ @QuentinPradet My entire point was std::vector allows for better memory management which can give a significant speed up if used correctly. \$\endgroup\$ – ahenderson May 23 '13 at 14:23
  • 2
    \$\begingroup\$ @Trouner: If anything, follow his advice regarding the pointers. This is C++, and there are pointer implementations in the STL that improve on raw pointers typically used in C. To be honest, I almost mistook your code as C just by looking at the raw pointers. \$\endgroup\$ – Jamal Sep 21 '13 at 20:21

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.