Speed up a program to find the minimum Hamming distance

Question

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 2^K - 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 

Answer 1

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 bitwise 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.

Answer 2

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.