Hi laserlight, thanks for the answer.
I have never heard of a trie data structure. Do you mean tree, in particular a balanced binary tree?
A trie is a type of tree, normally used to store data (strings) in a compact way. The links b/w nodes have a label (a char, commonly), and these are shared among keys. http://en.wikipedia.org/wiki/Trie
From what understand of your description, you want to map lists of integers to values, e.g.,
100, 200, 3000 -> "Hello"
9, 8, 7 -> "World"
then your concern would be given (9, 8, 7), you want to efficiently get the value "World".
Exactly.
Concerning the type of the key: storing an array or linked list of integers would be more efficient than storing a string, both in terms of space and time, since there would be less comparisons needed. For example, contrast a maximum of 3 comparisons for 100, 200, 3000 and 12 (or 13 as the case may be) for "100 200 3000".
If I use a trie I don't know if it'd be faster to search for the key using ints in the labels. e.g. let's say I need to find the int 22
Code:
1) using char* 2) using int
/|\ / \ \
0 1 2 0...21 22
/|\
0 1 2
In 1) I need to check 6 times at the worst. In case 2) I need to check 22 times at the worst.
So with large numbers, I thought it'd take longer to search for a key. Does this make sense?
Anyway, I will test a hash table too. I wanted first to know of the various options, and try to understand why a particular option would be faster.
Thanks