我正在为我的大学课程编写一个程序。它是动态规划算法的实现，用于 2 个处理器上的简单版本的调度任务。因为这是一种浪费内存的方法，我想到了一些改进。例如，不必存储整个 S xn 矩形数组，其中 S 是所有任务的次数之和，n 是任务数。因为在算法的第一次迭代中，数据只会存储在 n 轴的小索引值中，我想我可以让我的数组成为一个三角形，即每个下一个子数组都是一定数量的元素更长。
然后我在任务管理器中查看内存使用情况，我很震惊。带有矩形阵列的版本占用了 980KB。带有三角形阵列的版本（所以较小的）花了将近 15MB！也许我对系统使用的内存分配方式一无所知，或者我有错觉。或者我在代码中犯了一些愚蠢的错误。但我敢打赌我什么都不知道。有人可以启发我吗？
这是我的代码：
#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;
}