Storing array of integers as keys

This is a discussion on Storing array of integers as keys within the C Programming forums, part of the General Programming Boards category; Hi, I have to store sequences of integers as keys, which have a value associated to the sequence. e.g. a ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    6

    Question 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!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,397
    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?
    I have never heard of a trie data structure. Do you mean tree, in particular a balanced binary tree?

    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).
    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".

    A hash table would be the most efficient when it comes to searching. A balanced binary tree would also be a good choice, especially if you want to maintain order.

    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".
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    6
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Assignment HELP!!
    By cprogrammer22 in forum C Programming
    Replies: 35
    Last Post: 01-24-2009, 01:24 PM
  2. input row of integers via scanf into an array...
    By noodles355 in forum C Programming
    Replies: 1
    Last Post: 11-20-2006, 09:12 AM
  3. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 08:51 AM
  4. Array Program
    By emmx in forum C Programming
    Replies: 3
    Last Post: 08-31-2003, 12:44 AM
  5. Reading strings from a file and storing into an array
    By Rizage in forum C++ Programming
    Replies: 1
    Last Post: 10-24-2002, 03:04 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21