Thread: Storing array of integers as keys

Hi, I have to store sequences of integers as keys, which have a value associated to the sequence. e.g. a key could be '100 200 3000'. What is the most efficient way to store the keys? (I care mainly about access speed, memory is second).

Tries offer an efficient way to store strings, but the tries I found use a char as the label for each arc/link. Is it better to use an int instead of converting the integers to chars? Any other better alternative to trie?

Using ints will make the trie more compact, because I don't have to break the ints into chars. However, there will be more arcs at each level and the searches could take longer, wouldn't it?

Thanks in advance!

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