I've developed a program that reads numbers from .txt file where it will store into a vector to undergone a series of combinations and calculations to determine whether the result matches the number that I've wanted. These process will be done in multiple threads, where each thread will be in charge of handling various number of iterations within the parallel for loop.
Long story short, the processing time varies a lot when it comes to large number (e.g. 9 numbers) where the processing time could be as short as 3 minutes or it could be more than 10 minutes.
Here's the benchmark that I've tried so far:
8 numbers serial : 18.119 seconds
8 numbers multithread (first-try): 10.238 seconds
8 numbers multithread (second-try): 18.943 seconds
9 numbers serial : 458.980 seconds
9 numbers multithread (first-try): 172.347 seconds
9 numbers multithread (second-try): 519.532 seconds //Seriously?
//Another try after suggested modifications
9 numbers multithread (first-try): 297.017 seconds
9 numbers multithread (second-try): 297.85 seconds
9 numbers multithread (third-try): 304.755 seconds
9 numbers multithread (fourth-try): 396.391 seconds
So the question is, is there any possible way to improve the program (multi-thread) so that it only requires the least amount of time to shuffle/calculate the numbers?
Here's a portion of the code where parallel for loop occurs (Updated with slight modifications):
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <Windows.h>
#include <omp.h>
#define OPERATORSIZE 3
using namespace std;
int cur_target;
ofstream outFile;
string get_operator(int i) {
switch (i) {
case 0:
return "+";
case 1:
return "-";
case 2:
return "*";
case 3:
return "/";
default:
return "";
}
}
int prev_num_pos(vector<int> &cur_equation, int count) {
for (int i = count - 1; i >= 0; i--) {
if (cur_equation[i] != -1) return i + 1;
}
return 0;
}
bool nextoperator(int k, vector<int> &operator_array) {
for (int i = k - 2; i >= 0; i--) {
if (operator_array[i] < OPERATORSIZE) {
operator_array[i] += 1;
break;
}
else
operator_array[i] = 0;
switch (i) {
case 0:
return false;
}
}
return true;
}
void vector_combination(vector<int> int_list) { // Generate the number combinations from the number list
bool div_remainder = false;
int count = 0;
#pragma omp parallel for schedule(dynamic) firstprivate(div_remainder) reduction(+:count)
for (int i = 0; i < int_list.size(); ++i) {
vector<int> cur_equation, cur_temp, cur_list, operator_array;
auto list = int_list;
rotate(list.begin(), list.begin() + i, list.begin() + i + 1);
do
{
cur_list.clear();
operator_array.clear();
for (auto x : list)
cur_list.push_back(x);
for (int i = 0; i < cur_list.size() - 1; i++)
operator_array.push_back(0);
do
{
div_remainder = false;
count = 0;
cur_equation = operator_array;
cur_temp = cur_list;
for (int i = 0; i < cur_equation.size(); ++i) { // Check for equation priorities
if (cur_equation[i] == 3) {
count = i;
if (cur_temp[count] % cur_temp[count + 1] != 0) {
div_remainder = true;
break;
}
}
}
if (div_remainder)
continue;
for (int i = 0; i < cur_temp.size() - 1; ++i) {
count = -1;
if (cur_equation[i] == 2 || cur_equation[i] == 3) {
count = prev_num_pos(cur_equation, i);
}
else
continue;
if (cur_equation[i] == 2) {
cur_temp[count] *= cur_temp[i + 1];
cur_equation[i] = -1;
}
else if (cur_equation[i] == 3) {
if (cur_temp[i + 1] != 0) {
cur_temp[count] /= cur_temp[i + 1];
cur_equation[i] = -1;
}
else {
div_remainder = true;
break;
}
}
}
if (div_remainder)
continue;
for (int i = 0; i < cur_temp.size() - 1; ++i) {
switch (cur_equation[i]) {
case 0: {
cur_temp[0] += cur_temp[i + 1]; // Addition
cur_equation[i] = -1;
break;
}
case 1: { // Subtraction
cur_temp[0] -= cur_temp[i + 1];
cur_equation[i] = -i;
break;
}
}
}
if (cur_temp[0] == cur_target) {
#pragma omp critical
{
for (int i = 0; i < cur_list.size(); ++i) {
outFile << cur_list[i];
if (i < cur_list.size() - 1) { outFile << get_operator(operator_array[i]); }
}
outFile << "\n";
}
}
} while (nextoperator(cur_list.size(), operator_array));
// Send to function to undergone a list of operator combinations
} while (next_permutation(list.begin() + 1, list.end()));
}
}
int main(void) {
SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS);
vector<int> int_list;
string line;
ifstream myfile("Problem.txt");
if (myfile.is_open()) {
while (getline(myfile, line)) {
int num = stoi(line);
int_list.push_back(num);
cur_target = num;
}
}
else
cout << "Unable to open file." << endl;
myfile.close();
int_list.pop_back();
sort(int_list.begin(), int_list.end());
outFile.open("answer.txt");
vector_combination(int_list);
outFile.close();
int answer_count = 0;
myfile.open("answer.txt");
if (myfile.is_open()) {
while (getline(myfile, line)) {
++answer_count;
if (answer_count > 1)
break;
}
}
myfile.close();
if (answer_count == 0) {
outFile.open("answer.txt");
outFile << "-1" << endl;
}
outFile.close();
return 0;
}
As for the sample input, create a .txt file named "Problem.txt" with random numbers like so (The last number is the targeted result)(Updated with current sample input used for benchmark):
28
55
78
77
33
65
35
62
19
221
The hardware/software specification that the program runs on: Processor: i5 Sandy Bridge 2500K, Ram: 8GB, OS: Windows 10 Professional, IDE: Visual Studio 2015 Enterprise Edition,
