Skip to content

Instantly share code, notes, and snippets.

@Quinny
Created February 6, 2015 22:02
Show Gist options
  • Save Quinny/e81ab2e73f2e545acd31 to your computer and use it in GitHub Desktop.
Save Quinny/e81ab2e73f2e545acd31 to your computer and use it in GitHub Desktop.
Parallel vs series queueing
#include <iostream>
#include <queue>
#include <random>
#include <ctime>
#include <vector>
#define NCUSTOMERS 100
// for my own sanity
using engine = std::default_random_engine;
using dist = std::uniform_int_distribution<int>;
// N queues, using engines and dists to generate times
double series(int n, engine, dist, engine, dist);
double parallel(int n, engine, dist, engine, dist);
int main(){
// Customers arrive every [2,3] units of time
engine arrival_engine;
arrival_engine.seed(time(0));
dist arrival_time(2, 5);
// Customers take [1,6] units to be served
engine serve_engine;
serve_engine.seed(time(0));
dist served_time(10, 20);
std::cout << "Average wait time series: " << std::endl;
std::cout << series(3, arrival_engine, arrival_time, serve_engine, served_time) << std::endl;
std::cout << "Average wait time parallel: " << std::endl;
std::cout << parallel(3, arrival_engine, arrival_time, serve_engine, served_time) << std::endl;
}
double series(int n, engine arrival_engine, dist arrival_time, engine serve_engine, dist served_time) {
std::vector<std::queue<int>> queues(n);
std::vector<int> time_till_front(n, 0);
float total_wait_time = 0;
for(int i = 0; i < NCUSTOMERS; i++) {
int coming_in = arrival_time(arrival_engine);
int served_in = served_time(serve_engine);
// update the queues to get state at arrival time of new customer
for(int i = 0; i < queues.size(); i++) {
int c = coming_in;
while(c > 0 && queues[i].size() > 0) {
// By the time our new customer arrives, this one will be gone
if(c > queues[i].front()) {
time_till_front[i] -= queues[i].front();
queues[i].pop();
}
// This customer will still be here, but mid service
else {
queues[i].front() -= c;
time_till_front[i] -= c;
}
c -= queues[i].front();
}
}
// find the shortest queue for our new customer to join
int index = 0, shortest = queues[0].size();
for(int i = 0; i < queues.size(); i++) {
if(queues[i].size() < shortest) {
index = i;
shortest = queues[i].size();
}
}
// Increase the time for that queue
time_till_front[index] += served_in;
queues[index].push(time_till_front[index]); // add the customer to the shortest queue
total_wait_time += time_till_front[index];
}
return total_wait_time / NCUSTOMERS;
}
double parallel(int n, engine arrival_engine, dist arrival_time, engine serve_engine, dist served_time) {
// (time to be served, time waited in line)
std::vector<std::pair<int, int>> q;
std::vector<int> time_till_done(n, 0);
double total_wait_time = 0;
for(int i = 0; i < NCUSTOMERS; i++){
int coming_in = arrival_time(arrival_engine);
int served_in = served_time(serve_engine);
// Add new customer to the common queue (do this yet?)
// q.push(served_in);
for(int j = 0; j < time_till_done.size(); j++) {
int c = coming_in;
// Find the state of the common queues,
// and the tellers when our new customer comes in
while(c > 0 && !q.empty()) {
// If the person at the teller will be gone
if(c > time_till_done[j]) {
c -= time_till_done[j];
// move the next person in the queue to this teller
time_till_done[j] = q.front().first;
total_wait_time += q.front().second;
// and take them out of the queue
q.erase(q.begin());
}
else {
// Otherwise they will mid be service
time_till_done[j] -= c;
c = 0;
}
}
}
q.push_back(std::make_pair(served_in, 0));
for(int i = 0; i < q.size(); i++)
q[i].second += coming_in;
// Find the minimum time of all the people being helped, this is the time that it will take
// for the next person in line to be served
/*int shortest = time_till_done[0];
for(int i = 1; i < time_till_done.size(); i++)
shortest = std::min(shortest, time_till_done[i]);
time_till_front += shortest;
total_wait_time += time_till_front;*/
}
return total_wait_time / NCUSTOMERS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment