Gene, can you please explain by giving an example of 2-3 integers? An example will really help the group here a lot.
On Jul 14, 10:43 pm, Gene <gene.ress...@gmail.com> wrote: > On Jul 13, 3:46 am, Tech Id <tech.login....@gmail.com> wrote: > > > Wont a bitwise trie be too memory intensive? > > Storing an integer would need32nodes space and each node would need > > 3-integers space (data, left and right). > > So, if there are a million integers, we will need32*3 = 96 million > > integers! > > Great point. But it may be okay if you're tricky about how you store > things. First, you dont' have to store the values in the nodes, so > you're down to 2 integers. (An integer is in the tree only if a full > corresponding32-node path exists.) Especially, if you don't have to > change the trie after it's created, you can use cdr-coding. This > means that you store all (say) left-child descendents of every subtree > root as an array of right child pointers. In this manner, you need > zero bytes for left child pointers. (You do need a way to mark the end > of each array. One common technique is to set the lowest-order bit of > the last right child pointer to 1; since most systems align ints on 4- > byte boundaries, the low 2 bits of every pointer are normallly zero). > So now you are down to 1 word of32bits per node. So your 1 million > integers are representable in 4 million bytes, which is the same as a > simple array of integers. You can play further tricks to get it even > lower, but I'll let you think about that... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
