June 16th, 2003, 10:57 AM
Best algorithm to search through list of array of integers
I have an algorithm that calls some function "generate" multilple times. The generate function returns a pointer to a LIST OF ARRAYS of integers. Each array of integers represents an encoding for a set. For eg, if the array has one integer=3, then this means that objects 0 and 1 are in the set (since 3 in binary corresponds to bits 0 and 1 being turned on). Therefore, there are a possible 2^32 combinations for ONE integer in the array. If the array has between 32 and 63 objects, then the size of the array will increase to 2., and so on.
The point of my algorithm is to go through EACH list returned from EACH run of generate and figure out how many times each encoding occurs, over all the lists. So this is where I need help. I am trying to figure out the best possible way to count the frequency of each set. Right now, I can only think of a linear search. Making some structure that can hold ALL possible combinations would require too much memory. If I had 64 objects, then I would have a 2-dim array, the first dim would be 2^32, and each of these indices in turn would have 2^32 combintaions too. For my system, there could more than 300 objects, so it would require lots of memory.
Does anyone have any ideas for making my search/sort faster than linear?
I CANNOT change the generate algorithm in any way, neither can I change the way each set is represented (ie, each integer corresponding to 2^32 combinations of objects). I would appreciate any input whatsoever!!
THank you very much!