Как я могу изменить свой последовательный код на параллельный с помощью 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
Отложите код в сторону!!!
Подумайте о проблеме абстрактно и попробуйте перестроить алгоритм на параллельный... Можно ли это вообще сделать?