c++ - 三角形二维数组比矩形数组占用更多内存

Question

我正在为我的大学类(class)编写一个程序。它是用于在 2 个处理器上调度任务的简单版本的动态编程算法的实现。因为这是一种浪费内存的方法，我想到了一些改进。例如，不必存储整个 S x n 矩形数组，其中 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;
}

Answer 1

妈的，我瞎了。我有一个该死的大内存泄漏，我没有看到。我只是查看了执行的部分，当 memorySaving == 1 并注意到我正在分配(天知道为什么)我数组的每一行 taskCount 次......这是完全不是我写这篇文章时的意思。出色地。已经是深夜了。

抱歉打扰大家了。问题应该关闭。