Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need to have a data structure with say 4 keys . I can sort on any of these keys. What data structure can I opt for? Sorting time should be very little.

I thought of a tree, but it will be only help searching on one key. For other keys I'll have to remake the tree on that particular key and then find it. Is there any data structure that can take care of all 4 keys at the same time?

these 4 fields [source ip, destination ip, source port, destination] are of total 12 bytes and total size for each record - 40 bytes.. have memory constraints too...

around one lac records

operations are : insertion, deletion, sorting on different keys.

For printing , sorting the records on any of one keys should not take more than 5 seconds.

share|improve this question
    
what operations do you need apart form sort and with what sort of performance? –  jk. Sep 18 '12 at 12:30
2  
4 trees would do, one per each key. If data size is large, you'd need to use "pointers" instead of copies of it in the trees –  gnat Sep 18 '12 at 12:39
    
Do you have linq (Dot Net)? –  Emmad Kareem Sep 18 '12 at 12:39
    
@jk. : add and delete records and print the entries which are around one Lac –  jshah Sep 18 '12 at 12:55
2  
so what are your memory constraints? and how many records do you need to store? don't just hint at problems, tell us what they are! –  jk. Sep 18 '12 at 13:03
show 10 more comments

3 Answers

1. If you rarely add and remove data

What about using the same technique as the one used in RDBMS with indexes?

In other words, you'll have the unordered set containing the data, and four ordered sets containing the keys and the pointers to the items in the data set.

Of course, this may cause performance issues if you need to frequently add and remove lots of data.

2. If data is added or removed frequently

You can slightly modify the algorithm to reduce the performance impact of sorting the four index sets every time you add or remove an item. You may, for example, have four unordered index sets, create from them the sorted sets when needed, and invalidate those sorted sets when an element is added or removed.

3. Profile

Note that profiling is important, since you can't possibly guess where the bottleneck will be. Remember than:

  • When you remove an item from the data set, removing four keys from four index sets is fast, since those sets are already ordered;

  • When you add an item, adding four keys to the index sets is not hugely slow: you just have to walk through the sets, and insert the keys at the appropriate position:

    Let the list be:

     3, 7, 8, 12, 16, 22, 23, 24, 27
    

    If you need to add the value 25, position yourself at the middle of the list:

     3, 7, 8, 12, 16, 22, 23, 24, 27
                  ↑
    

    Since 25 is greater then 16, go to the right:

     -, -, -, --, --, 22, 23, 24, 27
                             ↑
    

    And again to the right:

     -, -, -, --, --, --, --, 24, 27
                                 ↑
    

    Found the position.

share|improve this answer
    
yeah will have to frequently add and remove data. –  jshah Sep 18 '12 at 12:44
add comment

Keeping four keys sorted is not really any different than keeping one key sorted.

Since you say that sort time should be very little, you are pretty much limited to using some sort of tree-like structure (tree, skip-list, trie, etc.). Which one is best for your application depends on the nature of the keys; if you can use a bitwise trie, that's very likely the best. Otherwise, you can select from among the many tree variants depending on how you want to trade off insertion time and lookup time/memory usage. For example, AVL trees are more dense than red-black trees, which means that insertion/deletion into AVL trees is slower (more work to maintain the dense structure), but lookup is faster and memory usage is less. If you tend to access the same few elements repeatedly, a splay tree is preferable.

Once you have an appropriate data structure selected for a single key, you just duplicate it as many times as you need for all the keys you want to sort on. If each element needs to be able to, for example, know how to get to "next" and "previous", you can have each element store a single pointer to a structure containing all of your trees.

share|improve this answer
    
above assumes keys are independent right? –  gnat Sep 18 '12 at 16:01
1  
@gnat - Yes, assuming that the keys are fairly independent. If they are highly dependent you may be able to find a better strategy (but even a few bad outliers can ruin the performance of an alternate strategy). –  Rex Kerr Sep 18 '12 at 16:09
    
@RexKerr : when you say "Once you have an appropriate data structure selected for a single key, you just duplicate it as many times as you need for all the keys you want to sort on." do you mean if there are 4 keys i shall use 4 trees (incase i opt for trees ) –  jshah Sep 20 '12 at 10:17
    
@JitenShah - Yes, one tree for each key. If you have zero keys sorted and you want one sorted, use a tree (or whatever). Now, if you have another key...same deal, keep a tree sorted on that key. (You'll probably need some handy add/remove methods that take care of all the separate trees.) –  Rex Kerr Sep 20 '12 at 11:14
add comment

Keep your data in a hash table keyed by a UUID. Then keep four indexes, each with two fields: the search key, and the UUID of the data. You search the indexes to find the key, then use the key to get the data from the hash table. Retrieving the data from the hash table is O(1), searching the index depends on the implementation (O(log N) for a red-black tree, O(M) for a trie, O(1) for a hash table).

share|improve this answer
1  
What is the advantage to keeping the data in a hash table instead of having pointers to the data from each of the four trees? Even if your pointers are 64 bit and you use 32 bit keys, you end up with 4*8*N = 32*N bytes of pointer storage for N entries in the four-tree case and 4*4*N + (4+8)*N/lf, where lf is the average hash table load factor, which is usually 0.375 with a flat hash table, giving 48*N. Even shorts are not a win (34.67*N), and some platforms let you save pointer space (e.g. JVM compressed oops). With 64b pointer/32b int, 8 keys is the break-even point. –  Rex Kerr Sep 18 '12 at 16:23
    
Sorry, I've been playing with Big Data lately, so I was thinking about having indexes that scale across machines. Obviously, if you're running on a single machine, pointers or object references are the way to go. –  TMN Sep 18 '12 at 20:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.