Dictionary and array of [N] size - performance tuned

Hi All

I have a temperature reading device.
I require to store the last N records of its temperature reading in an object
it will either be 5, 10 or 20 records

I was thinking of a dictionary with ID and array:
it should look like this:

ID, array of [N] records

i.e. in this example, there are 2 ID's and I store the last 5 temperature values

12345, 10.01
             10.02
             11.05
             11.02
             11.20

42133, 11.01
             12.02
             12.05
             12.02
             12.20

Open in new window


My first question is about the array ordering
Can i define the size of the array, and push to it so it always inserts the latest temperature at top, and discards the oldest record at bottom, always keeping the correct size and order? (if not what other object should i use)

second question, is there a better way to do this, maybe using a different object??
I will be reading and updating it once a second so it needs to be FAST as there could be a million ID's each with 5-20 temperature readings
websssCEOAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Nitin SontakkeDeveloperCommented:
Please let me try to understand this properly. Are you saying that this not yet persisted anywhere in db? And you will persist this in db later and you want an intermediate data structure?

Or, this is already persisted and while fetching you want this structure?

At what level 5, 10 or 20 is decided?

Arrays will (to my knowledge) not provide a behavior you are expecting inherently. You will need to write one....complicated.

I am confused if you want a FIFO or FILO implementation. In either case both are implemented already as Queue class and Stack class.
0
Dr. KlahnPrincipal Software EngineerCommented:
I'd use a circular rotating array.  This is about as fast as possible for the described application.

Circular rotating arrays are most efficiently implemented in sizes that are a power of 2.

Consider an empty array of 6 slots.  Initialize head pointer at 0.

0,0,0,0,0 <- head pointer
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0

Open in new window


Now add a data item to the array at the head pointer.  Bump the head pointer forward.

2,35,387,0,6
0,0,0,0,0 <- head pointer
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0
0,0,0,0,0

Open in new window


Keep adding data until the array is full.

2,35,387,0,6
6,0,80,9,5
2,2,0,3,0
6,0,3,0,13
7,0,40,0,6
93,0,1,6,12
 <- head pointer

Open in new window


When the head pointer overflows, reset it to zero.  Adding the next item destroys the old data in slot zero.

4,65,1,4,-3
6,0,80,9,5 <- head pointer
2,2,0,3,0
6,0,3,0,13
7,0,40,0,6
93,0,1,6,12

Open in new window


If it is necessary to know how much data is in the array, also keep a tail pointer.  The array can be implemented without a tail pointer if it fills quickly and there is no need to know whether the array is full.

Circular rotating arrays are normally implemented in sizes that are exponents of 2 is because end-of-array pointer checking can be done as an AND with a bitmask, not a conditional.
0
websssCEOAuthor Commented:
Hi Nitin

Are you saying that this not yet persisted anywhere in db? And you will persist this in db later and you want an intermediate data structure?
Yes its also persisted in DB, but we are caching in memory object for performance issues... this is a design decision which is not up for discussion, and has to be in memory

Or, this is already persisted and while fetching you want this structure?
We get the value first, then we persist in DB
When we get the data, we first need to persist into an in memory object, and then save to DB

At what level 5, 10 or 20 is decided?
UI level, it will be different for each device, and this is already taken care of


I am confused if you want a FIFO or FILO implementation. In either case both are implemented already as Queue class and Stack class.
FILO, the function behind this data storage is to take the last N values and output an AVERAGE value of the last N data.

I hope that clarifies ?
0
Learn Ruby Fundamentals

This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

websssCEOAuthor Commented:
Hi Dr

I'd use a circular rotating array.  This is about as fast as possible for the described application.

is this available in a .Net object?
0
Dr. KlahnPrincipal Software EngineerCommented:
Sorry, I have no idea.  (I'm not a Windows programmer.)
0
Nitin SontakkeDeveloperCommented:
You may wish to have a look at Stack<T> class then. Have a custom class having one property for Id and another as Stack for temperatures.
0
Fernando SotoRetiredCommented:
Hi websss;

You can use a combination of a Dictionary and Queue for the readings such as in this code snippet.
// Holds the Device ID and the readings in a Queue
Dictionary<int, Queue<decimal>> readings = new Dictionary<int, Queue<decimal>>();
// Number of records to be stored in the Queue
int N = 5;

private void button1_Click(object sender, EventArgs e)
{
    // Test data to be used
    var setup = new [] { new { id = 12345, reading = 10.01 },
        new { id = 42133, reading = 11.01 },
        new { id = 12345, reading = 10.02 },
        new { id = 42133, reading = 12.02 },
        new { id = 12345, reading = 11.05 },
        new { id = 42133, reading = 12.05 },
        new { id = 12345, reading = 11.02 },
        new { id = 42133, reading = 12.02 },
        new { id = 12345, reading = 11.20 },
        new { id = 42133, reading = 12.20 },
        new { id = 12345, reading = 12.01 },
        new { id = 42133, reading = 12.50 }
    } ;

    // Load test data
    foreach (var item in setup)
    {
        // See if the Dictionary has the key already in it.
        if(readings.ContainsKey(item.id))
        {
            // Key was found add new value to the end of the Queue
            readings[item.id].Enqueue((decimal)item.reading);
            // Check to see how many values in the Queue if more then N remove first entry
            if (readings[item.id].Count() > N) readings[item.id].Dequeue();                   
        }
        else
        {
            // Key was not in the Dictionary. add new entry and reading
            Queue<decimal> que = new Queue<decimal>();
            que.Enqueue((decimal)item.reading);
            readings.Add(item.id, que);
        }
    }
}

Open in new window

1

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
websssCEOAuthor Commented:
thanks, this is more inline with my thinking
whats the performance of a QUEUE like? i've never used before.
And using the deQueue, and add are efficient?
0
käµfm³d 👽Commented:
Define "performance". What part of this needs to be fast? The read? The write? All of it?
0
Fernando SotoRetiredCommented:
The Queue collection uses a circular array internally and seeming the number of elements being used is small and arrays have direct access performance should not be an issue.
1
websssCEOAuthor Commented:
awesome!
0
Fernando SotoRetiredCommented:
Glad to help websss. Have a great day.
1
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C#

From novice to tech pro — start learning today.