# Speed up a program to find the minimum Hamming distance

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

• Can you give an example matrix and desired output? May 23, 2013 at 6:33
• Can I divide the problem in thread? Is possible that? May 23, 2013 at 10:09
• This is the problem in case it helps kattis.csc.kth.se/problem?id=codes May 24, 2013 at 13:03
• 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. May 24, 2013 at 13:56
• It seems like you are using a very brute force approach. Have you thought about using another algorithm instead of optimizing your algorithm? Sep 21, 2013 at 13:33

## 2 Answers

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.

• You may eventually find this handy. Sep 22, 2013 at 19:10

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.

• Thank you very much I will try to rewrite all the code using the vector. May 23, 2013 at 6:09
• 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. May 23, 2013 at 6:31
• I've modified the code and only drops from 0,53s to 0,491s so the change isn't very helpful May 23, 2013 at 9:50
• @QuentinPradet My entire point was std::vector allows for better memory management which can give a significant speed up if used correctly. May 23, 2013 at 14:23
• @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. Sep 21, 2013 at 20:21