www.digitalmars.com         C & C++   DMDScript  

c++ - Queues & Random Numbers

reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
I'm not sure what exactly I'm doing wrong here, please advise.
I'm trying to randomly select numbers from the interval [0, 3]
If the number is either 0 or 3, I will ignore it, otherwise I will
enqueue that many customers at the time of arrival.

For every minute that passes I will take one serve one customer,
thereby removing them from the queue.

The problem I'm facing with the current implementation is that
the program does not accurately track the customers upon
arrivial. Additionally, it crashes for any for intervals less than
four minutes (simLength = 4).

Thanks in Advance,
Andrew

========================================
for ( minute = 0 ; minute < simLength ; minute++ )
{
    // Dequeue the first customer in line (if any). Increment
    // totalServed, add the time that this customer waited to
    // totalWait, and update maxWait if this customer waited
    // longer than any previous customer.
    if (!custQ.isEmpty())
    {
      timeArrived = custQ.dequeue();
      waitTime = minute - timeArrived;
      totalServed++;
      totalWait += waitTime;
      if (waitTime > maxWait)
        maxWait = waitTime;
    }

    // Determine the number of new customers and add them to
    // the line.
    const int N = 4;
    srand((unsigned)time(NULL)+minute);
    numArrivals = (rand() % N);

    switch(numArrivals)
    {
      case 0:
      case 3: break;
      case 1: custQ.enqueue(minute); break;
      case 2: custQ.enqueue(minute); custQ.enqueue(minute); break;
    }
}
Jun 29 2003
parent reply "Wichetael" <wichetael gmx.net> writes:
The code looks allright to me, so I'm thinking the problem's in CustQ.

Oh, and btw, you don't need to seed the random number generator for every
random number you get. Actually, for simulations it is most likely better to
do it only once at the start of the simulation and provide a choice whether
to take a random (usually time based) seed or provide one manually. This way
you actually have a pseudo random list which means you can test the same
input on several different implementations of the algorithm to see which one
works better.

Regards,
Remko van der Vossen


"Andrew Edwards" <edwardsac spamfreeusa.com> wrote in message
news:bdn1f6$gra$1 digitaldaemon.com...
 I'm not sure what exactly I'm doing wrong here, please advise.
 I'm trying to randomly select numbers from the interval [0, 3]
 If the number is either 0 or 3, I will ignore it, otherwise I will
 enqueue that many customers at the time of arrival.

 For every minute that passes I will take one serve one customer,
 thereby removing them from the queue.

 The problem I'm facing with the current implementation is that
 the program does not accurately track the customers upon
 arrivial. Additionally, it crashes for any for intervals less than
 four minutes (simLength = 4).

 Thanks in Advance,
 Andrew

 ========================================
 for ( minute = 0 ; minute < simLength ; minute++ )
 {
     // Dequeue the first customer in line (if any). Increment
     // totalServed, add the time that this customer waited to
     // totalWait, and update maxWait if this customer waited
     // longer than any previous customer.
     if (!custQ.isEmpty())
     {
       timeArrived = custQ.dequeue();
       waitTime = minute - timeArrived;
       totalServed++;
       totalWait += waitTime;
       if (waitTime > maxWait)
         maxWait = waitTime;
     }

     // Determine the number of new customers and add them to
     // the line.
     const int N = 4;
     srand((unsigned)time(NULL)+minute);
     numArrivals = (rand() % N);

     switch(numArrivals)
     {
       case 0:
       case 3: break;
       case 1: custQ.enqueue(minute); break;
       case 2: custQ.enqueue(minute); custQ.enqueue(minute); break;
     }
 }

Jun 29 2003
parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
"Wichetael" <wichetael gmx.net> wrote ...

 The code looks allright to me, so I'm thinking the problem's in CustQ.

CustQ is an instance of a queue template implementation I did a few weeks back. To this point I had no problems with it, and after looking it over, I still cannot find the problem. This is what it looks like: Que<dType>:: Que( int maxN ) throw (bad_alloc) { maxQue = maxN + 1; head = maxN; tail = maxN; items = new dType[maxQue]; } Que<dType>:: ~Que() { delete [] items; } void Que<dType>:: enqueue( const dType &newItem ) throw ( logic_error ) { if(full()) throw logic_error("some error"); else { tail = (tail + 1) % maxQue; items[tail] = newItem; } } dType Que<dType>:: dequeue() throw (logic_error) { if(empty()) throw logic_error("some error"); else head = (head + 1) % maxQue; return items[head]; } bool Que<dType>:: empty() { return (tail == head);} bool Que<dType>:: full() { return ((tail + 1) % maxQue == head);} your help is greatly appreciated, Andrew
Jun 29 2003
parent reply "Wichetael" <wichetael gmx.net> writes:
Again the code looks perfectly fine to me.

The following code, which is essentialy your code copy-pasted into an empty
file and commenting out a couple of things and adding the rest of the code
to make it all compile, works beautifully for me whether I take a simLength
of 2, 3, 10, or a hundred...

My best advise for you is to either use a debugger to try and find what is
causing your problem or cut pieces out of the code bit by bit to see what's
causing the problem...

Regards,
Remko van der Vossen

----------------------------------------------------------

#include <iostream>
#include <time.h>

template<class dType> class Queue {
private:
  int maxQueue;
  int head;
  int tail;
  dType* items;
public:
  Queue(int maxN) {
    maxQueue = maxN + 1;
    head = maxN;
    tail = maxN;
    items = new dType[maxQueue];
  }
  ~Queue() {
    delete[] items;
  }
  void enqueue(const dType &newItem) {
    if(full())
      ;//throw logic_error("some error");
    else {
      tail = (tail + 1) % maxQueue;
      items[tail] =  newItem;
    }
  }

  dType dequeue() {
    if(empty())
      ;//throw logic_error("some error");
    else
      head = (head + 1) % maxQueue;
    return items[head];
  }

  bool empty() {return (tail == head);}
  bool full()  {return ((tail + 1) % maxQueue == head);}
};

void main() {
  Queue<int> custQ(100);

  int simLength = 100;
  int totalServed = 0;
  int totalWait = 0;
  int maxWait = 0;

  srand((unsigned)time(0));

  for (int minute = 0 ; minute < simLength ; minute++ ) {
    // Dequeue the first customer in line (if any). Increment
    // totalServed, add the time that this customer waited to
    // totalWait, and update maxWait if this customer waited
    // longer than any previous customer.
    if (!custQ.empty()) {
      int waitTime = minute - custQ.dequeue();
      totalServed++;
      totalWait += waitTime;
      if (waitTime > maxWait)
        maxWait = waitTime;
    }

    // Determine the number of new customers and add them to
    // the line.
    const int N = 4;
    int numArrivals = (rand() % N);

    switch(numArrivals) {
      case 0:
      case 3: break;
      case 1: custQ.enqueue(minute); break;
      case 2: custQ.enqueue(minute); custQ.enqueue(minute); break;
    }
  }

  std::cout << "total customers served: " << totalServed << std::endl;
  std::cout << "total wait time: " << totalWait << std::endl;
  std::cout << "average wait time per customer: " <<
((float)totalWait/totalServed) << std::endl;
  std::cout << "maximum wait time per customer: " << maxWait << std::endl;
}
Jun 30 2003
parent reply "Andrew Edwards" <edwardsac spamfreeusa.com> writes:
"Wichetael" <wichetael gmx.net> wrote ...

 My best advise for you is to either use a debugger to try and find what is
 causing your problem or cut pieces out of the code bit by bit to see

 causing the problem...

Thanks! :-) I found the culprit; A devide by zero error on the last line of main! Sorry about the confusion! Andrew
Jul 01 2003
parent "Wichetael" <wichetael gmx.net> writes:
Glad to hear you've found your problem.

Regards,
Wichetael

"Andrew Edwards" <edwardsac spamfreeusa.com> wrote in message
news:bdtrgg$1o5u$1 digitaldaemon.com...
 "Wichetael" <wichetael gmx.net> wrote ...

 My best advise for you is to either use a debugger to try and find what


 causing your problem or cut pieces out of the code bit by bit to see

 causing the problem...

Thanks! :-) I found the culprit; A devide by zero error on the last line of main! Sorry about the confusion! Andrew

Jul 02 2003