Home » programming » Optimizing

Optimizing

How can we decrease the memory consumption of some code? Our reference problem is Palindrome. The code that follows does not pass the test of the judge.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <utility>

using namespace std;

int** cache;

int palindrome(const char* a, const int start, const int end) {
	if (end - start <= 0)
		return 0;
	if (cache[start][end] != -1)
		return cache[start][end];
	if (a[start] == a[end])
		return cache[start][end] = palindrome(a, start + 1, end - 1);

	return cache[start][end] = 1 + min(palindrome(a, start, end - 1),  palindrome(a, start + 1, end));
}

int main() {
	int length;
	cin >> length;
	char* input;
	input = new char[length + 1];
	cin >> input;
	cache = new int*[length];
	for (int i = 0; i < length; ++i)
	{
		cache[i] = new int[length];
		for (int j = 0; j < length; ++j)
			cache[i][j] = -1;
	}
	cout << palindrome(input, 0, length - 1) << endl;

	return 0;
}

Let’s convert the recursive calls to a for loop and store the intermediate results in an array. A position [i][j] in array D denotes how many characters we have to append to the string starting at position i with length j in order to get a palindrome. Of course, the result for strings of length 0 and length 1 does not have to be stored. We know that the answer is 0. Therefore, we can shift the rest of the values and save O(n) memory, where n is the length of the input.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <utility>

using namespace std;

short palindrome(const char* a, const int end) {
	short **D;
	D = new short*[end];
	for (int i = 0; i < end; ++i) {
		D[i] = new short[end - i];
	}

	for (int t = 1; t <= end; ++t) {
		for (int i = end - t; i >= 0; --i) {
			if (a[i] == a[i + t])
				D[i][t - 1] = (i + 1 >= end || t <= 2) ? 0: D[i + 1][t - 3];
			else {
				if (t == 1)
					D[i][t - 1] = 1;
				else
					D[i][t - 1] = 1 + min(D[i + 1][t - 2], D[i][t - 2]);
			}
		}
	}

	short res = D[0][end - 1];

	for (int i = 0; i < end; ++i) {
		delete [] D[i];
	}
	delete [] D;

	return res;
}

int main() {
	int length;
	cin >> length;
	char* input;
	input = new char[length + 1];
	cin >> input;
	cout << palindrome(input, length - 1) << endl;

	delete [] input;

	return 0;
}

Unfortunately, our answer now is too slow to pass from the judge system. We compute intermediate values that we don’t need. How can we solve the problem efficiently then?

The answer is simply use short instead of int in our initial solution. We don’t need the whole range that an integer offers. Moreover, the recursive calls will be limited only to necessary subproblems.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <utility>

using namespace std;

short** cache;

short palindrome(const char* a, const int start, const int end) {
	if (end - start <= 0)
		return 0;
	if (cache[start][end] != -1)
		return cache[start][end];
	if (a[start] == a[end])
		return cache[start][end] = palindrome(a, start + 1, end - 1);

	return cache[start][end] = 1 + min(palindrome(a, start, end - 1),  palindrome(a, start + 1, end));
}

int main() {
	int length;
	cin >> length;
	char* input;
	input = new char[length + 1];
	cin >> input;
	cache = new short*[length];
	for (int i = 0; i < length; ++i)
	{
		cache[i] = new short[length];
		for (int j = 0; j < length; ++j)
			cache[i][j] = -1;
	}
	cout << palindrome(input, 0, length - 1) << endl;

	return 0;
}

Take home point: Try simple/trivial optimizations before changing completely your whole algorithm. We could save half the amount of memory by just switching from int to short.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: