Data structure searched
-
Hi everyone,
I currently have a problem with a data structure I could use some advice with, since I can come up with anything good.
There are 4 hash tables with the same keys but different values. It also would be possible to put them together in a new container. The 4 different values for each key should be ordered (asc or desc doesn't matter) and I want the average of the 2nd and 3rd.
The idea I have is to iterate through one table to get the keys, go to each tables and get the values, add them to a list, qSort() the list with the 4 values and save the result in a new hashtable with the key.
I guess that would work but does not perform very well. Any idea?Thanks
-
Hi,
What are your hash tables currently ? Do you want to replace them ?
-
In light of current cache and CPU architectures you could consider something simple like this:
@
struct Data {
SomeType key;
std::array<SomeOtherType,4> values;
};
std::vector<Data> mySortedData;
@
...with some access functions that would ensure sorted insertion and something like binary search for look up.This all depends of course on the size, type and access patterns of your data.
Stuff like cache locality and branch prediction make many algorithmic complexity assumptions void these days. Profiling and benchmarking seem to be the mantra of today.
