View unanswered posts | View active topics It is currently Wed Nov 26, 2014 4:17 pm






Reply to topic  [ 5 posts ] 
Some hints needed to improve my code for queues 
Author Message
Expert
User avatar

Joined: Mon Oct 06, 2008 6:30 pm
Posts: 176
Location: Netherlands
Post Some hints needed to improve my code for queues
Hi,

I wrote some code to create a queue type data structure, see below. This code is written to store data of type float. Now I want to use the same code for other data types, like integers but also my own structs. I rather not copy and modify this code for every datatype. Instead, I want to use macro code to do this. But I do not know how. I messed a bit with the define statement but I couldn't get it to work. Can anyone give me some direction? For the moment it is ok to assume that I need to use only one datatype per program. So there is no need to find alternatives for overloading the functions provided.

The code is more complex than you might expect. The reason for this is in performance. I found out that moving items in an array (as a queue should behave when you add an item) is time consuming, especially when the queues are large. So instead of moving items I use arrays that are double the size of the queue and I use pointers to the first and last item in the queue. The disadvantage of this solution is that it uses double the amount of memory. I wander if it is possible to move all items in an array with a single function like memcopy (the doc says memcopy is for characters).


Code:

const int queuesize=20;

typedef struct    {
   float values[queueSize*2-1];
   int size;
   int start;
   int end;
}    tqueue;

float atToQueue (tqueue &queue, float newValue)
{
   float returnValue;
   if (queue.size==queueSize)
   {
     returnValue=queue.values[queue.start];
     queue.sum=queue.sum-returnValue;
     if (++queue.start==queueSize*2-1) queue.start=0;
   }
   if (++queue.end==queueSize*2-1) queue.end=0;
   queue.values[queue.end]=newValue;
   if (queue.end>=queue.start)
     queue.size=queue.end-queue.start;
   else
     queue.size=queueSize*2-1-queue.start+queue.end;
   queue.sum=queue.sum+newValue;
   return returnValue;
}

float getItem(tqueue &queue, int index)
{
   float returnValue;
   if (0<=index && index<queue.size+1)
   {
      returnValue=queue.values[(index+queue.start) % (queueSize*2-1)];
   }
   return returnValue;
}

void clearQueue(tqueue &queue)
{
   queue.start=0;
   queue.end=0;
   queue.size=0;
}

_________________
My most recent blog: A grain of sugar


Fri Nov 07, 2008 10:15 am
Profile WWW
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
Post Re: Some hints needed to improve my code for queues
Aswin,

Looking at #define was a good idea. To understand how it works, just keep in mind that macros created by #define are pre-processor commands. That means they run before the compiler does. Essentially, when you have a #define, every place in the code that references the macro gets replaced before the compiler runs.

Here is an example:
Code:
#define DTYPE int

DTYPE showPI()
{
  DTYPE PiVal = (DTYPE)3.14159;

  eraseDisplay();
  nxtDisplayTextLine(0, "%d", (DTYPE)PiVal, 0);
}

task main()
{
  showPI();
  while(1);
}

In the code above, I've created a 'DTYPE' macro, which defines the data type I will be using. Then, any place I want to use the data type, I just use the macro. If you run this code as is, you'll notice the code correctly behaves as if the 'PiVal' variable was an integer.

Next, try switching the first line to: "#define DTYPE float". (You also need to change the display line to "%f" instead of "%d". You'll notice the code now works with the data being represented by a float.

The same thing can be done in your queue code:
Code:
#define QTYPE float

const int queuesize=20;

typedef struct    {
   QTYPE values[queueSize*2-1];
   int size;
   int start;
   int end;
}    tqueue;

QTYPE atToQueue (tqueue &queue, QTYPE newValue)
{
   QTYPE returnValue;
   if (queue.size==queueSize)
   {
       ..... etc ....


That would allow you to switch the data type. As you mentioned, you would only be able to use one data type per program.

As a sidenote, is this code in progress? I notice that it doesn't compile due to references to a "queue.sum" member of the struct that isn't defined. Also, it seems unlikely that moving both the start and end indices in the 'add' routine is what you would want to be doing. Your 'get' routine is interesting as well. You allow people to access any element of the queue? Not just the one at the front?

Best of luck in your work.


Wed Nov 12, 2008 12:10 am
Profile
Expert
User avatar

Joined: Mon Oct 06, 2008 6:30 pm
Posts: 176
Location: Netherlands
Post Re: Some hints needed to improve my code for queues
Thanks for the example. I know now what I did wrong (I refferenced the macro using #DTYPE instead of DTYPE).

The code is functional for integers but I stripped it for this example. I use these queues to calculate moving averages amongst other things. The sum member of the struct is used to keep track of the sum of the values in my queue. This gives me a big performance boost as I do not have to add up all the values everytime I want to know the moving average (taking queueLength+1 calculations), instead I have to update the sum everytime I add a value to the queue (taking 2 calculations). It seems I didn't completely strip it from my code.

I have also found out that the code only works for simple data types but not for structs as functions cannot return struct datatypes.

And yes, I can access the members of the queue, so it is not really a queue. But I didn't feel like implementing the limitations of a queue.

Thanks again.

_________________
My most recent blog: A grain of sugar


Wed Nov 12, 2008 4:30 am
Profile WWW
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
Post Re: Some hints needed to improve my code for queues
If you wanted to make it work for structs as well, you could have the 'return value' passed in by reference. Then, rather than returning the result, you just set the value of the variable they passed in.

To do this, you would need to use memcpy and 'sizeof' to deal with arbitrary types.


Wed Nov 12, 2008 9:28 am
Profile
Expert
User avatar

Joined: Mon Oct 06, 2008 6:30 pm
Posts: 176
Location: Netherlands
Post Re: Some hints needed to improve my code for queues
Thanx,

AvidProgrammer wrote:
If you wanted to make it work for structs as well, you could have the 'return value' passed in by reference. Then, rather than returning the result, you just set the value of the variable they passed in.

I realized that and did some experimenting with it. I was not sure if passing simple data by reference would work just as it works for structs. It does. So this is valid code:
Code:
void myFunction(int &parm1);


AvidProgrammer wrote:
To do this, you would need to use memcpy and 'sizeof' to deal with arbitrary types.


I also tested these functions for moving data along an array. Also this does seem to work. But only if you copy up the array (from 0 to 1) but not if you copy it down the array. Here's the code:
Code:
const int myLength=10;
memcpy(myArray[1], myArray[0], sizeof(myArray[0])*(myLength-1) );

I didn't test it for performance, but it will half the size of my queues.

Last thing to find out is how to use macro code to give different function names for different type of data. Like: addIntToStack, addFloatToStack. Then I can finish my include file for queues.

_________________
My most recent blog: A grain of sugar


Wed Nov 12, 2008 7:20 pm
Profile WWW
Display posts from previous:  Sort by  
Reply to topic   [ 5 posts ] 

Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.