search and find the shortest queue and search after some condition

2013-03-07

An answer to this question on Stack Overflow.

Question

I am trying to implement a Task scheduler where i have n number of tasks. The Idea behind my task scheduler is that in a loop of queues of a vector, task should get enqueued to the shortest queue among the loop of queues, which is done by the following code.

#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
int min_index = 0;
task t // implemented in the other part of the program
std::size_t size = q.size();
for( i=0; i<size; i++){ //accessing loop of queues
    if(q[min_index].size() > q[i].size())
        min_index = i; // Now q[min_index] is the shortest queue
} 
q[min_index].push(Task);

Next i am trying to extend this paradigm to reduce the overhead time of the scheduler, Instead of searching the shortest queue every time, search after some condition ie. search the shortest queue after 5 tasks gets enqueued to the shortest queue.

i need to do something like this

#include <vector> 
#include <queue> 
std::vector<std::queue<int> > q
task t // implemented in the other part of the program
while(q[min_index].size()!=q[min_index].size()+5) // check whether current min_index  queue's size is increased 5 more times if not goto enqueue
        {
        goto enqueue;
        }
       
    int min_index = 0;
    std::size_t size = q.size();
    for( i=0; i<size; i++){ //accessing loop of queues
        if(q[min_index].size() > q[i].size())
            min_index = i; // Now q[min_index] is the shortest queue
    } 
    enqueue:  
    q[min_index].push(Task);

can someone please help me how to proceed it correctly. thanks in advance

Updated Instead of having 5 ( a random number) i thought of having a number which is reliable and approximate everytime. so i thought of get the difference of min_value size and max_value size for the loop of queues and compare it with the counter each time.

// global variables 
std::vector<std::queue<int> > q;
int counter = INT_MAX; // 
int min_index = 0;
int max_size = -1;
void enqueue(scheduler::task new_task) { 
 if ( counter > diff_size ){
  // look for new min and maximum
  std::size_t size = q.size();
  for( i=0; i<size; i++){ 
    if(q[min_index].size() > q[i].size())
     min_index = i; 
       if(q[i].size() > max_size)
        max_size = q[i].size(); 
    diff_size=max_size - min_index;
  } 
  // counter reset
  counter = 0;
 }
 // enqueue in minimum queue
 q[min_index].push(new_task)
 // increase counter
 counter ++;
}

Answer

I guess I would try this (the code does compile, and it does work):

#include <vector> 
#include <queue>
#include <cassert>
#include <iostream>
using namespace std;
class multi_queue{
  private:
    typedef std::vector<std::queue<int> > mq_type;
    mq_type q;
    int min_queue;
    int min_queue_inc;
    int max_inc;
    void find_min_queue(){
      max_inc=q[min_queue].size();
      min_queue_inc=0;
      min_queue=0;
      for(int i=1;i<q.size();++i)
        if(q[i].size()<q[min_queue].size())
          min_queue=i;
    }
  public:
    multi_queue(int n) {
      assert(n>0);
      min_queue=0;
      min_queue_inc=0;
      max_inc=5;
      increase_queues(n);
    }
    void increase_queues(int n){ 
      if(n<q.size()) return;
      q.resize(n);
    }
    void push(int item){
      if(min_queue_inc++==max_inc)
        find_min_queue();
      q[min_queue].push(item);
    }
    int queues() const {
      return q.size();
    }
    int pop_from(int qnum){
      assert(qnum>=0);
      assert(qnum<q.size());
      assert(can_pop_from(qnum));
      int temp=q[qnum].front();
      q[qnum].pop();
      return temp;
    }
    bool can_pop_from(int qnum) const {
      return q[qnum].size()>0;
    }
    int largest_queue() const {
      int largest=0;
      for(int i=1;i<q.size();++i)
        if(q[i].size()>q[largest].size())
          largest=i;
      return q[largest].size();
    }
};
int main(){
  multi_queue q(10);
  for(int i=0;i<100;++i){
    cout<<"Current largest queue: "<<q.largest_queue()<<endl;
    cout<<"Pushing: " <<i<<endl;
    q.push(i);
  }
  for(int i=0;i<10;++i)
  for(int j=0;j<100;++j)
    if(q.can_pop_from(i))
      cout<<q.pop_from(i)<<endl;
}

Naturally you would not want to display q.largest_queue() each time because that would defeat the point, but I do it here so that you will be able to see that things are working.

The important methods from the stand-point of answering your question are push() and find_min_queue().

I use two state variables, min_queue and min_queue_inc to keep track of what's going on.

min_queue always points to the shortest queue. min_queue_inc keeps track of how many items have been added to that queue.

In push() we check to see whether the current minimum queue has 5 items added to it; if so, it is time to see whether there is a new minimum queue we should be using, and we therefore call find_min_queue().

find_min_queue() resets min_queue_inc, finds the shortest queue, and makes a note of that queue in min_queue.

Depending on what you want to do, adjust the behavior of the variable max_inc to suit your needs.