The advantages of a trie over an array for strings storage

joaquimandrade · **Author**

Those who are unaware of what a trie is and what's its purpose, when needing a data structure to store strings, use an array. Since you can also use tries for store strings there are best cases of use for each one.

What they are:

An array is a group of sequential bytes in memory subdivided in groups of the same length, being each one of the subdivided a individual place to store data, that you can access by its position in the array (usually referred as index).

A trie is a collection of data organized in the form of a hierarchy. The level zero is a start point. From there on, each level is a group of strings of length equal to the level number and different from each other. Each string can be associated to a value and to strings in the level below that share its characters. If one is associated to a value, it is stored in the trie.

From wikipedia:

In the tree above there are stored the strings:

A , i , to , in , tea , ted , ten , inn

(since they are those who have associated values).

Which one should be used where you can use both:

An array should be used when you know the index of the string that you want to posteriorly access or if you need to iterate over its values.

A trie should be used when you want to posteriorly search for a string.

To show the differences of its usage, in a case where you should use a trie, i created the following situation:

I want to know if in a list of steam Ids there is a given steam Id. I have a list of 69 steam Ids and the given steam Id is not on the list.

When comparing algorithms it must be tested what's referred to as "worst case". The worst case is the case on which you force the algorithm to test every possibility. That's why the steam Id is not on the list.

The code and the profiling results go as attachments.

A note:

While the superiority of tries over arrays for this case should be obvious i think that the results for ArrayGetString are not accurate. So or:

They are accurate and i am wrong
I made something wrong
There's something wrong with ArrayGetString
There's something wrong with the profiling.

**Arkshine**

Interesting ! Thanks joaquimandrade.

joaquimandrade

Quote:

Originally Posted by arkshine

Interesting ! Thanks joaquimandrade.

Thank you for having the patience to read it.

**Arkshine**

Hope to see more tutos from you !

stupok · *Last edited by stupok; 03-24-2009 at 19:07.*

Thanks for taking the time to write this. It's very concise and well-written.

The results for cellArray are quite strange...

joaquimandrade

Quote:

Originally Posted by stupok

Thanks for taking the time to write this. It's very concise and well-written.

The results for cellArray are quite strange...

Thanks.

About the results of the time spent by ArrayGetString:

I think that they should be far lower. Since they are so closer to those of strcmp my guess is that the problem is with the profiling.