Suggest a good method with minimal search time complexity
I have a structure that has 3 id fields and one value field. I have a list of these objects. To give an analogy, ID fields are like the primary keys to an object. These 3 fields uniquely identify the object.
Class
{
int a1;
int a2;
int a3;
int value;
};
I will have a list of 1000 objects of this datatype. I need to check for specific values of these identity key values by passing the values a1, a2 and a3 to a search function that will check if any object exists with those specific values a1, a2 and a3 and returns that value. What is the most efficient way to implement this to achieve the best lookup times?
One solution I could think of is to have a 1000-length 3D matrix and fill its value. This is O (1) search time. But the disadvantages. 1. I need to know the length of the array. 2. For higher identity fields (say 20) I need a matrix of size 20 which will be overflowed in memory. For my actual implementation, I have 23 identification fields.
Can you suggest a good way to store this data that would give me the best time to search?
source to share
Create a key class that contains all of the ID fields and define an appropriate equality function and hash method, and then use a hash map to map from the key class to its associated value. This will give you O (1) time complexity to search in the expected case, and it requires space proportional to the number of actual keybindings (usually double that, although you can adjust the constant for the time / space tradeoff you desire) rather than space proportional to all possible key combinations.
source to share
I would just sort the array by key and use binary search.
(unverified)
int compare_entry(ENTRY *k1, ENTRY *k2) {
int d = k1->a1 - k2->a1;
if (d == 0) {
d = k1->a2 - k2->a2;
if (d == 0) {
d = k1->a3 - k2->a3;
}
}
return d; // >0 is k1 > k2, 0 if k1 == k2, <0 if k1 < k2
}
// Derived from Wikipedia
int find(ENTRY *list, int size, ENTRY *value) {
int low = 0;
int n = size - 1;
int high = n;
while (low < high) {
int mid = low + (high - low) / 2
int cmp = compare_entry(&list[mid], value);
if (cmp < 0) {
low = mid + 1;
} else {
high = mid;
}
}
if (low < n) {
int cmp = compare_entry(&list[low], value);
if (cmp == 0) {
return low; // found item at 'low' index
}
} else {
return -1; // not found
}
}
Absolutely worst case, you run this thing that, 10 times, and end up doing all the comparisons in a key comparison. So, what, 85 whole math operations (additions, subtractions and 1 shift)?
if your a1-a3 is in the range 0-100 then you can make your key a1 * 10000 + a2 * 100 + a3 and do one comparison and the worst is 63 whole math exercises. And your entire array fits into the cache on most modern CPUs. And this is effective memory.
You can write memory with a perfect hash or some other sparse matrix. Even with a great hash, I'm sure the hash calculation itself will be competitive with this time, given that the multiplication is expensive. This is obviously on the memory bus.
source to share