c++ - 离散事件仿真算法调试

Question

我正在使用 C++ 编写一个离散事件模拟程序。我的输出完全不正确，但所有输出值都非常接近正确的输出。我试过调试我的算法，但我找不到任何错误。下面是我模拟的主要算法。

我使用最小堆和数组实现了事件优先级队列。我不允许使用任何 STL 库。代码中使用的FIFO队列是一个链表。当我在优先级队列顶部打印事件时间时，事件并不总是按升序传递(我认为这是事件优先级队列应该如何工作)，我不明白为什么。升序主要在事件完成时间附近被打破。请帮忙!

#include <iostream>
#include <fstream>
#include "PQueue.h"
#include "SPqueue.h"
#include "LinkedList.h"

using namespace std;

int serverCount;               //number of servers
Spqueue spq;                   //priority queue for servers
Pqueue pq;                     //priority queue for events
LinkedList list;               //FIFO queue to put arriving events in
double totalTime;              //variables for statistics calculation
double timeNow;
double totalWait;
int ql;
int qlength = 0;
double totalQlength;
int time = 0;

bool available();      //checks availability of servers

int main() {
    ifstream fin;
    fin.open("Sample2.txt");
    if (!fin.good())
        cerr << "Couldn't find file/corrupted file" << endl;
    fin >> serverCount;      //reads number of servers and efficiency 
                                    //from file                        
 for (int i = 0; i < serverCount; i++) {
        server s;
        fin >> s.effi;
        s.status = true;
        s.count = 0;
        spq.insert(s);
    }
  //reads first event from file
    event e;
    fin >> e.eventTime;
    fin >> e.serviceTime;
    e.eventType = -1;
    pq.insert(e);
    int i = 1;
    //while priority queue is not empty
    while (!pq.isEmpty()) {
        timeNow = pq.getArrivalTime(1);

    while (time < pq.getArrivalTime(1)) {
        totalQlength = totalQlength + list.getLength();
        time++;
    }
    //get event from priority queue 
    if (pq.getServer(1) == -1) {   //if arrival event, add to FIFO queue
        list.AddTail(pq.getArrivalTime(1), pq.getServiceTime());
        if (list.getLength() > qlength) {
            qlength = list.getLength();
        }
        //read next arrival event from file
        if (!fin.eof()) {
            event e;
            fin >> e.eventTime;
            fin >> e.serviceTime;
            e.eventType = -1;
            pq.insert(e);
            i++;
        }

    }
    else  //must be customer complete event
    {
        spq.setIdle(pq.getServer(1));   //set the server to idle
    }
    pq.deleteMin();   //remove the evnt from priority queue
    //if FIFO queue is not empty and servers are available
    //process event
    if ((list.isEmpty() == false) && (available() == true)) {
        list.getHead();
        int s = spq.getMin();
        spq.setBusy(s);    //set server to busy
        spq.incrementCustNumber(s); //increment number of customers  
                                     //served
        double waitTime = timeNow - list.getHead().arrivalTime;
        totalWait = totalWait + waitTime;
        double serviceT = spq.getEffi(s) * list.getHead().serviceTime;
        double eventT = list.getHead().arrivalTime +serviceT;
        event e2;
        e2.eventTime = eventT;
        e2.serviceTime = list.getHead().serviceTime;
        e2.eventType = s;
        pq.insert(e2);  //add customer complete event to the priority  
                        //queue   
        list.RemoveHead();  //remove head from FIFO
    }
    totalTime = pq.getArrivalTime(1);
}
fin.close();
return 0;
}

bool available() {
    bool ava = false;
    for (int i = 1; i <= serverCount; i++) {
        if (spq.getStatus(i) == true) {
            ava = true;
            break;
        }
    }
    return ava;
}

优先级队列实现如下:

#include <iostream>
#include <fstream>
#include "PQueue.h"

using namespace std;

Pqueue::Pqueue() {
    inde = 0;                  //length of heap
}

void Pqueue::insert(event i) {     //inserts new element into the heap array and maintains min heap property
    inde++;
    pqueue[inde] = i;
    siftup(inde);
}

int Pqueue::getServer(int i) {
    return pqueue[i].eventType;
}

void Pqueue::siftup(int i) {       //shifts element up to the correct position in the heap
    if (i == 1)
        return;
    int p = i / 2;
    if (pqueue[p].eventTime > pqueue[i].eventTime)
    {
        swap(pqueue[i], pqueue[p]);
        siftup(p);
    }
}

void Pqueue::deleteMin() {            //removes element at the root of the heap
        swap(pqueue[inde], pqueue[1]);
        inde--;
        siftdown(1);
}

void Pqueue::siftdown(int i) {          //shifts element to its position in the min heap
    int c = i * 2;
    int c2 = (i * 2) + 1;
    if (c > inde) return;
    int in = i;
    if (pqueue[i].eventTime > pqueue[c].eventTime)
    {
        in = c;
    }
    if ((c2 < inde) && (pqueue[i].eventTime > pqueue[c2].eventTime))
    {
        in = c2;
    }
    if (pqueue[c].eventTime < pqueue[c2].eventTime) {
        in = c;
    }
    if (in != i) {
        swap(pqueue[i], pqueue[in]);
        siftdown(in);
    }
}

void Pqueue::swap(event& i, event& j) {
    event temp;
    temp = i;
    i = j;
    j = temp;
}

bool Pqueue::isEmpty() {        //checks if the priority queue is empty
    if (inde == 0) return true;
    else
    return false;
}

double Pqueue::getArrivalTime(int i) {
    return pqueue[i].eventTime;
}

double Pqueue::getServiceTime() {
    return pqueue[1].serviceTime;
}

有五台服务器，效率各不相同。将使用最高效的空闲服务器。为此，我在开始时明智地对服务器阵列进行了排序。

#include <iostream>
#include <fstream>
#include "SPqueue.h"

using namespace std;

Spqueue::Spqueue() {
    inde = 0;
}

void Spqueue::insert(server i) {     //inserts new element into the array
    inde++;
    spqueue[inde] = i;

}

void Spqueue::heapify(int n, int i)
{
    int largest = i;  // Initialize largest as root
    int l = 2 * i;  // left = 2*i + 1
    int r = 2 * i +1;  // right = 2*i + 2

                        // If left child is larger than root
    if (l < n && spqueue[l].effi > spqueue[largest].effi)
        largest = l;

    // If right child is larger than largest so far
    if (r < n && spqueue[r].effi > spqueue[largest].effi)
        largest = r;

    // If largest is not root
    if (largest != i)
    {
        swap(spqueue[i], spqueue[largest]);

        // Recursively heapify the affected sub-tree
        heapify(n, largest);
    }
}

void Spqueue::heapSort()
{
    // Build heap (rearrange array)
    for (int i = inde / 2 - 1; i > 0; i--)
        heapify(inde, i);

    // One by one extract an element from heap
    for (int i = inde - 1; i > 0; i--)
    {
        // Move current root to end
        swap(spqueue[1], spqueue[i]);

        // call max heapify on the reduced heap
        heapify(i, 1);
    }
}

void Spqueue::swap(server& i, server& j) {
    server temp;
    temp = i;
    i = j;
    j = temp;
}

int Spqueue::getMin() {      //iterates to the next available server in the sorted list of servers
    int i = 0;
    while (i <=20){
        if (spqueue[i].status == true)
        {
            return i;
        }
        else
        {
            i++;
        }
    }
}

bool Spqueue::getStatus(int i) {
    return spqueue[i].status;
}
void Spqueue::setBusy(int i) {
    spqueue[i].status = false;
}

void Spqueue::addServiceTime(int i,double s) {
    spqueue[i].busyTime = spqueue[i].busyTime + s;
}

double Spqueue::getTotalServiceTime(int i) {
    return spqueue[i].busyTime;
}

void Spqueue::setIdle(int i) {
    spqueue[i].status = true;
}

double Spqueue::getEffi(int i) {
    return spqueue[i].effi;
}

void Spqueue::incrementCustNumber(int i) {
    spqueue[i].count++;
}

int Spqueue::getCount(int i) {
    return spqueue[i].count;
}

下面的函数应该返回最高效的服务器。

int Spqueue::getMin() {      //iterates to the next available server in  
                                      the already sorted array       
    int i = 0;
    while (i <=20){
        if (spqueue[i].status == true)
        {
            return i;
        }
        else
        {
            i++;
        }
    }
}

Answer 1

siftdown 的优先级队列实现有一些问题。

void Pqueue::siftdown(int i) {          //shifts element to its position in the min heap
    int c = i * 2;
    int c2 = (i * 2) + 1;
    // *** Possible bug
    // *** I think that if c == inde, then c is indexing beyond the current queue
    if (c > inde) return;
    int in = i;
    if (pqueue[i].eventTime > pqueue[c].eventTime)
    {
        in = c;
    }
    if ((c2 < inde) && (pqueue[i].eventTime > pqueue[c2].eventTime))
    {
        in = c2;
    }
    // ***************
    // ** Bug here
    if (pqueue[c].eventTime < pqueue[c2].eventTime) {
        in = c;
    }
    if (in != i) {
        swap(pqueue[i], pqueue[in]);
        siftdown(in);
    }
}

首先，我想你想测试c1 >= inde .此外，当您检查是否 pqueue[c].eventTime < pqueue[c2].eventTime 时, 你这样做没有确保 c2在范围内。

我发现以下是一种更清晰简洁的做事方式:

// find the smallest child
int in = c;
if (c2 < inde && pqueue[c2] < pqueue[c])
{
    in = c2;
}
if (pqueue[in] < pqueue[i]) {
    swap(pqueue[i], pqueue[in]);
    siftdown(in);
}