[ create a new paste ] login | about

Link: http://codepad.org/pqs9uz72    [ raw code | fork ]

C++, pasted on May 29:
#include <iostream>
#include <iomanip>
#include <climits>
#include <sys/time.h>
#include <cstdlib>
#include <string.h>
#include <math.h>
#include <omp.h>

int A[4096];
int B[13][4096];
int prefix[13][4096];

void omp_function(int m)
{
	int h;

	for (h = 1; (1 << h) <= m; h++)
		#pragma omp parallel for
		for (int j = 0; j < m >> h; j++)
			B[h][j] = std::min(B[h-1][2*j], B[h - 1][2*j + 1]);

	//h = log(m) / log(2) - 1;
	for (h = h - 1; h >= 0; h--)
	{
		int end = (m >> h) - 1;

		prefix[h][0] = B[h][0];

		#pragma omp parallel for
		for (int j = 1; j <= end; j++)
		{
			if (j % 2 == 1)
			{
				prefix[h][j] = prefix[h+1][(j-1)/2];
			}
			else
			{
				prefix[h][j] = std::min(prefix[h+1][j/2 - 1], B[h][j]);
			}
		}
	}
}

void ser_function(int m)
{
	int h;

	for (h = 1; (1 << h) <= m; h++)
		for (int j = 0; j < m >> h; j++)
			B[h][j] = std::min(B[h-1][2*j], B[h - 1][2*j + 1]);

	//h = log(m) / log(2) - 1;
	for (h = h - 1; h >= 0; h--)
	{
		int end = (m >> h) - 1;

		prefix[h][0] = B[h][0];

		for (int j = 1; j <= end; j++)
		{
			if (j % 2 == 1)
			{
				prefix[h][j] = prefix[h+1][(j-1)/2];
			}
			else
			{
				prefix[h][j] = std::min(prefix[h+1][j/2 - 1], B[h][j]);
			}
		}
	}
}

int main(int argc, char * argv[])
{
	srand(time(NULL));

	for (int i = 0; i < 4096; i++)
	{
		A[i] = rand();
	}

	struct timeval startt, endt, result;
	int max = INT_MIN;
	int min = INT_MAX;
	int rnd;

	gettimeofday(&startt, NULL);
	for (int i = 0; i < 10000; i++)
	{
		memcpy(B, A, sizeof(int) * 4096);
		ser_function(4096);
	}
	gettimeofday (&endt, NULL);
	result.tv_usec = (endt.tv_sec * 1000000 + endt.tv_usec) - (startt.tv_sec * 1000000 + startt.tv_usec);
	std::cout << " " << result.tv_usec / 1000000 << "." << std::setfill('0') << std::setw(6) << result.tv_usec % 1000000 << std::endl;

	gettimeofday(&startt, NULL);
	//#pragma omp parallel for
	for (int i = 0; i < 10000; i++)
	{
		memcpy(B, A, sizeof(int) * 4096);
		omp_function(4096);
	}
	gettimeofday (&endt, NULL);
	result.tv_usec = (endt.tv_sec * 1000000 + endt.tv_usec) - (startt.tv_sec * 1000000 + startt.tv_usec);
	std::cout << " " << result.tv_usec / 1000000 << "." << std::setfill('0') << std::setw(6) << result.tv_usec % 1000000 << std::endl;

	return 0;
}


Create a new paste based on this one


Comments: