Member 11465955 Ответов: 1

Как я могу изменить свой последовательный код на параллельный с помощью openmp?


Привет, я написал программу, которая работает как 24-игровая головоломка, то есть из заданного целочисленного набора и целевого значения я перечисляю все возможные математические выражения для оценки этого целевого значения.
Теперь я хочу изменить этот код с помощью openMP, чтобы ускорить работу программы. Итак, может ли кто-нибудь помочь мне, какие сегменты кода должны быть изменены и как это можно сделать?

Что я уже пробовал:

#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;


//All the Declaration of my functions
vector<int> getQuestion();


#define EMPTY -1
#define DIV 0
#define MUL 1
#define PLUS 2
#define MINUS 3


//Declare Global Constant
const string problemFile = "problem.txt";
const string answerFile = "answer.txt";
ofstream writeToAnswerFile(answerFile);


/* Following function is needed for library function qsort(). */
int compare(const void *a, const void * b)
{
	return (*(int *)a - *(int *)b);
}

// A utility function two swap two characters a and b
void swap(int* a, int* b)
{
	char t = *a;
	*a = *b;
	*b = t;
}

// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil(int str[], int first, int l, int h)
{
	// initialize index of ceiling element
	int ceilIndex = l;

	// Now iterate through rest of the elements and find
	// the smallest character greater than 'first'
	for (int i = l + 1; i <= h; i++)
		if (str[i] > first && str[i] < str[ceilIndex])
			ceilIndex = i;

	return ceilIndex;
}


void releaseAnswerFile() {
	writeToAnswerFile.close();
}
//Main Program
int main() {
	writeToAnswerFile<<"-1"<<endl;
	writeToAnswerFile.close();
	atexit(releaseAnswerFile);
	vector<int> question = getQuestion();	//Retrieve Question from file

	int* questionArray = new int[question.size()]();
	char operatorList[] = { '/','*','+','-' };
	int targetAnswer = question.back();	//Get the final answer
	question.pop_back();	//remove the final answer from question list
	const int numberOfOperator = question.size() - 1;
	const int questionSize = question.size();
	bool hasAnswer = false;
	for (int i = 0; i < questionSize;i++) {
		questionArray[i] = question[i];
	}
	if (!question.empty()) {

		// Sort the string in increasing order
		qsort(questionArray, questionSize, sizeof(int), compare);

		//create dynamic allocation array
		int* tempOperationSequence = new int[numberOfOperator]();
		int* tempOperandSequence = new int[questionSize]();

		//algorithm starts for operands' permutation without duplication
		bool isFinished = false;
		while (!isFinished)
		{
			////////////////////////////////////////////////
			//brute force every operator combination algorithm start
			bool shouldContinueFindNewOperatorCombination = true;
			int* operationSequence = new int[numberOfOperator]();	//initialize the operand with all value 0
			operationSequence[0] = -1;
			int operatorPositionToChange = 0;
			bool containMultiplication = false;
			do {
				bool shouldSkipThisCombination = false;
				//generate next set of operand's combination
				if (++operationSequence[operatorPositionToChange] == 4) {
					for (int i = operatorPositionToChange; i < numberOfOperator;i++) {
						if (operationSequence[i] == 4) {
							operationSequence[i] = 0;
							if (i + 1 == numberOfOperator) {
								shouldContinueFindNewOperatorCombination = false;
								shouldSkipThisCombination = true;
								break;
							}
							operationSequence[i + 1]++;
						}
					}
				}
				operatorPositionToChange = 0;
				//Check Point 1
				if (shouldSkipThisCombination) {
					continue;
				}
				//Create a copy of operator array and operand array
				for (int operation = 0; operation < numberOfOperator;operation++) {
					tempOperationSequence[operation] = operationSequence[operation];
				}
				for (int operand = 0; operand < questionSize;operand++) {
					tempOperandSequence[operand] = questionArray[operand];
				}
				//Start the calculate the answer based on current set of operators and operands
				int finalResult;
				int fDigitPos = 0;	//First digit position
				int sDigitPos = 1;	//Second digit position

				//check all division operators first, if there are any invalid pairs, directly discard the whole combination
				for (size_t i = 0; i < numberOfOperator; i++) {
					if (tempOperationSequence[i] == DIV) {
						if (tempOperandSequence[i + 1] <= 0 || tempOperandSequence[i] % tempOperandSequence[i + 1] != 0) {
							operatorPositionToChange = i;
							shouldSkipThisCombination = true;
							break;
						}
					}
				}
				//Check Point 2
				if (shouldSkipThisCombination) {
					continue;
				}
				//entering the real calculation part
				//look for both multiplication and division operator
				for (size_t i = 0; i < numberOfOperator && fDigitPos != numberOfOperator; i++) {

					if (tempOperationSequence[i] == DIV) {
						if (tempOperandSequence[sDigitPos] > 0 && tempOperandSequence[fDigitPos] % tempOperandSequence[sDigitPos] == 0) {

							tempOperandSequence[fDigitPos] /= tempOperandSequence[sDigitPos];
							tempOperandSequence[sDigitPos] = -1;
							tempOperationSequence[i] = -1;
							sDigitPos++;
						}
						else {
							shouldSkipThisCombination = true;
							break;
						}
					}
					else if (tempOperationSequence[i] == MUL) {
						tempOperandSequence[fDigitPos] *= tempOperandSequence[sDigitPos];
						tempOperandSequence[sDigitPos] = -1;
						tempOperationSequence[i] = -1;
						sDigitPos++;
					}
					else {
						fDigitPos = sDigitPos;
						sDigitPos++;
					}
				}
				//Check Point 3
				if (shouldSkipThisCombination) {

					continue;
				}
				fDigitPos = 0;
				sDigitPos = 1;
				for (int i = 0; i < numberOfOperator;i++) {
					if (tempOperandSequence[i] != -1) {
						fDigitPos = i;
						sDigitPos = i + 1;
						break;
					}
				}
				//perform addition and subtraction
				for (size_t i = 0; i < numberOfOperator &&fDigitPos != numberOfOperator; i++) {

					if (tempOperationSequence[i] == EMPTY) {
						continue;
					}
					else if (tempOperandSequence[sDigitPos] == EMPTY) {
						i--;
						sDigitPos++;
						continue;
					}
					//Since plus and minus are the last section, no need to indicate used operands and operators is still ok
					else if (tempOperationSequence[i] == PLUS) {
						tempOperandSequence[fDigitPos] += tempOperandSequence[sDigitPos];
						sDigitPos++;
					}
					else if (tempOperationSequence[i] == MINUS) {
						tempOperandSequence[fDigitPos] -= tempOperandSequence[sDigitPos];
						sDigitPos++;
					}
				}
				//get the final result from array
				finalResult = tempOperandSequence[fDigitPos];
				//check result
				if (finalResult == targetAnswer) {
					//directly write answer into the file
					if(hasAnswer){
					
					writeToAnswerFile<<questionArray[0];
					for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
						writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
						writeToAnswerFile<<questionArray[answerPos];
					}
					}else{
						hasAnswer = true;
						writeToAnswerFile = ofstream(answerFile,ios::trunc);
						
						writeToAnswerFile<<questionArray[0];
						for (size_t answerPos = 1; answerPos < questionSize; answerPos++) {
							writeToAnswerFile<<operatorList[operationSequence[answerPos - 1]];
							writeToAnswerFile<<questionArray[answerPos];
						}
					}
					
					writeToAnswerFile << endl;

				}
			} while (shouldContinueFindNewOperatorCombination);
			delete [] operationSequence;

			////////////////////////////////////////////////
			// Find the rightmost character which is smaller than its next
			// character. Let us call it 'first char'
			int i;
			for (i = questionSize - 2; i >= 0; --i)
				if (questionArray[i] < questionArray[i + 1])
					break;

			// If there is no such chracter, all are sorted in decreasing order,
			// means we just printed the last permutation and we are done.
			if (i == -1)
				isFinished = true;
			else
			{
				// Find the ceil of 'first char' in right of first character.
				// Ceil of a character is the smallest character greater than it
				int ceilIndex = findCeil(questionArray, questionArray[i], i + 1, questionSize - 1);

				// Swap first and second characters
				swap(&questionArray[i], &questionArray[ceilIndex]);

				// Sort the string on right of 'first char'
				qsort(questionArray + i + 1, questionSize - i - 1, sizeof(int), compare);
			}
		}
		delete[] tempOperationSequence;	//release dynamic allocation memory
		delete[] tempOperandSequence; //release dynamic allocation memory
		writeToAnswerFile.close();
	}

	return 0;
}

/***
getQuestion()
- Open Problem file and retrieve all the numbers from the file
return:
- vector<int> - List of Numbers

*/
vector<int> getQuestion() {
	vector<int> numbers;
	string line;
	ifstream opener;
	opener.open(problemFile);
	if (opener.is_open()) {
		while (getline(opener, line))
		{
			numbers.push_back(stoi(line));
		}
	}

	opener.close();
	return numbers;

}</int></int></int></int></int></vector></algorithm></fstream></string></iostream>

Mehdi Gholam

Похоже на домашнюю работу.

Member 11465955

да, это задание, я его выполнил, Олди. но теперь я хочу научиться этому параллельно для теста.

Kornfeld Eliyahu Peter

Отложите код в сторону!!!
Подумайте о проблеме абстрактно и попробуйте перестроить алгоритм на параллельный... Можно ли это вообще сделать?

1 Ответов

Рейтинг:
0

KarstenK

Параллельное выполнение кода-это не всегда решение, потому что оно также создает накладные расходы для этого. Ваша основная задача должна состоять в том, чтобы найти медленные части кода и перепроектировать их.

Как я вижу, вы часто пишете в файле writeToAnswerFile. Это похоже на узкое место. Я бы попытался сохранить эту информацию в строке и написать, если это необходимо однажды если все будет сделано.

//Create a copy of operator array and operand array
for (int operation = 0; operation < numberOfOperator;operation++) {
  tempOperationSequence[operation] = operationSequence[operation];
}


Я бы заменил
memcpy(tempOperationSequence, operationSequence, operation);

в разных местах вашего кода.

Единственная вещь для параллели-это сортировка. Google для получения дополнительной информации.