Data structure design question...

[MrViggy]

Hey all,

I have a liner set of data points. Instead of x/y coordinates, I have value/time pairs. The value is a simple integer (an enumeration, but stored as an int).

My question is this, what is the best data structure for this type of data? I'm currently using a vector of maps. The time points are in femto-seconds, so they can get quite large. The index into the vector is "timeval / MAX_INT"; the key into the map is "timeval % MAX_INT". I was curious if there was a better method for this. Most of the time, clients will be either requesting a value at a specific time; or iterating between two time points.

Thanks!!!

Viggy

[Yves M]

Why not just use a simple map for everything? Then you can do both things quickly. Looking up is O(log(N)) which is still pretty fast and you'll get better clarity.

How large are the time values? Since you're using INT_MAX, I guess that a time value can be larger than INT_MAX, so are you storing them as int64? Or as double? In either case, using a single map would still be fine.

This is of course assuming that the data is not dense. If you have data for pretty much every point in time, then a vector is probably better.

[kuphryn]

What data type is defined as the map key?

Kuphryn

[T.G.]

I think two vectors can be used. one vector of doubles, the other is of ints.

[MrViggy]

Yes, it's possible that a particular data set has a lot of data, and data points can easily exceed MAX_INT.

I was looking for a speed/memory tradeoff. If the dataset is sparse, then a simple map of INT64->INT is okay. Once the data starts to become dense (which is pretty easy to do), then I'm storing a lot of INT64's, and using up a lot of memory.

This is for a digital simulator, and the base time is femto-seconds. There's nothing to stop a user from creating a design with a clock that has a 2ns period, and simulate for 10 seconds! As you can prolly tell, that's a LOT of data. Of course, I can "compress" the clock data (just store the clock's attributes). However, the user can have other signals in the design that are not necessarily clocks.

Doubles are out of the question. Computers stink at storing floating point numbers, and FP arithmatic is SLLLLLOOOOWWWW! :)

The map key is an unsigned integer.

A co-worker suggested a B-Tree, and I had thought of using one. But, when I sat down to think about it, a B-Tree is kinda overkill...

Viggy

[MrViggy]

Oh, yeah, the data is also going to be stored on disk. But I was thinking that as long as I can get a nice memory data structure implemented, I can just implement some kind of caching system.

Another caveat is that most access to the data will be linear. In other words, the display will have a start time -> end time and the GUI will just ask for all values within those two times.

Viggy