私は大学のクラスにプログラムを書いています。これは、2 つのプロセッサでタスクをスケジューリングするための単純なバージョンの動的計画法アルゴリズムの実装です。メモリの無駄使いなので、改善策を考えてみました。たとえば、S xn 長方形配列全体を格納する必要はありません。ここで、S はすべてのタスクの時間の合計であり、n はタスクの数です。アルゴリズムの最初の反復では、データは n 軸の小さなインデックス値にのみ格納されるため、配列を三角形にすることができると考えました。つまり、次の各サブ配列は特定の量の要素が長くなります。
次に、タスク マネージャーでメモリ使用量を調べたところ、ショックを受けました。長方形配列のバージョンは 980KB かかりました。トライアングル アレイを使用したバージョン (小さい方のアレイ) は、ほぼ 15 MB かかりました。システムで使用されるメモリ割り当ての方法について何も知らないか、妄想を持っているのかもしれません。または、コードで愚かな間違いを犯しました。でもきっと何かわからない。誰かが私を啓発できますか？
これが私のコードです：
#include <iostream>
#include <fstream>
#include <conio.h>
#include <stack>
using namespace std;
void readTasks(char* filename, int*& outTaskArray, int& outTaskCount)
{
ifstream input = ifstream();
input.open(filename, ios::in);
input >> outTaskCount;
outTaskArray = new int[outTaskCount];
for (int i = 0; i < outTaskCount; ++i)
{
input >> outTaskArray[i];
}
input.close();
}
void coutTasks(int* taskArray, int taskCount)
{
cout << taskCount << " tasks:\n";
for (int i = 0; i < taskCount; ++i)
{
cout << i << ": " << taskArray[i] << endl;
}
}
void Scheduling2(int* taskArray, int taskCount, int memorySaving,
stack<int>*& outP1Stack, stack<int>*& outP2Stack)
{
bool** scheduleArray = new bool*[taskCount];
int sum;
// I know that construction below is ugly cause of code repetition.
// But I'm rather looking for performance, so I try to avoid e.g.
// checking the same condition too many times.
if (memorySaving == 0)
{
sum = 0;
for (int i = 0; i < taskCount; ++i)
{
sum += taskArray[i];
}
scheduleArray[0] = new bool[sum + 1];
for (int j = 0; j < sum + 1; ++j)
{
scheduleArray[0][j] = j == 0 || j == taskArray[0];
}
for (int i = 1; i < taskCount; ++i)
{
scheduleArray[i] = new bool[sum + 1];
for (int j = 0; j < sum + 1; ++j)
{
scheduleArray[i][j] = scheduleArray[i - 1][j] ||
j >= taskArray[i] &&
scheduleArray[i - 1][j - taskArray[i]];
}
}
getch(); // I'm reading memory usage from Task Manager when program stops here
int halfSum = sum >> 1;
while (!scheduleArray[taskCount - 1][halfSum]) --halfSum;
for (int i = taskCount - 1; i > 0; --i)
{
if (scheduleArray[i - 1][halfSum])
outP1Stack->push(i);
else if (scheduleArray[i - 1][halfSum - taskArray[i]])
{
outP2Stack->push(i);
halfSum -= taskArray[i];
}
}
if (halfSum) outP2Stack->push(0);
else outP1Stack->push(0);
}
else if (memorySaving == 1)
{
sum = 0;
for (int i = 0; i < taskCount; ++i)
{
sum += taskArray[i];
scheduleArray[0] = new bool[sum + 1];
for (int j = 0; j < sum + 1; ++j)
{
scheduleArray[0][j] = j == 0 || j == taskArray[0];
}
for (int i = 1; i < taskCount; ++i)
{
scheduleArray[i] = new bool[sum + 1];
for (int j = 0; j < sum + 1; ++j)
{
scheduleArray[i][j] = scheduleArray[i - 1][j] ||
j >= taskArray[i] &&
scheduleArray[i - 1][j - taskArray[i]];
}
}
}
getch(); // I'm reading memory usage from Task Manager when program stops here
int halfSum = sum >> 1;
while (!scheduleArray[taskCount - 1][halfSum]) --halfSum;
for (int i = taskCount - 1; i > 0; --i)
{
if (scheduleArray[i - 1][halfSum])
outP1Stack->push(i);
else if (scheduleArray[i - 1][halfSum - taskArray[i]])
{
outP2Stack->push(i);
halfSum -= taskArray[i];
}
}
if (halfSum) outP2Stack->push(0);
else outP1Stack->push(0);
}
for (int i = 0; i < taskCount; ++i)
{
delete[] scheduleArray[i];
}
delete[] scheduleArray;
}
int main()
{
char* filename = "input2.txt";
int memorySaving = 0; //changing to 1 in code when testing memory usage
int* taskArray; // each number in array equals time taken by task
int taskCount;
readTasks(filename, taskArray, taskCount);
coutTasks(taskArray, taskCount);
stack<int>* p1Stack = new stack<int>();
stack<int>* p2Stack = new stack<int>();
Scheduling2(taskArray, taskCount, memorySaving, p1Stack, p2Stack);
cout << "\np1: ";
while (p1Stack->size())
{
cout << p1Stack->top() << ", ";
p1Stack->pop();
}
cout << "\np2: ";
while (p2Stack->size())
{
cout << p2Stack->top() << ", ";
p2Stack->pop();
}
delete p1Stack;
delete p2Stack;
delete[] taskArray;
return 0;
}