On 09/02/2010 04:06 AM, Andrej van der Zee wrote:

Hi,

I have a question that I hope can be answered by using Boost. I have the following datastructure:

struct ip_info { const u_int8_t _ifile_index; const unsigned long _src_ip; const unsigned long _dst_ip; const u_int16_t _id; const u_int16_t _length; const u_int16_t _src_port; const u_int16_t _dst_port; const u_int32_t _seq; const u_int32_t _ack_seq; };

The object is identified by all its members. Now I want to count duplicates. But I have MANY of these objects, I mean billions. I have to reduce the memory footprint of my program, because it soon grows over 4GB and boom! So I rather not keep all the objects in memory and why would I, because I do not need them. I just need to count duplicates.

My, what a clear statement of a classic problem. Hmm, are you sure this isn't homework? :-)

My idea was to hash such objects to a smaller values and use that hash value as key_type in a map.

Usually you'd want to base it on std::vector and call it a hashtable.

The value_type of the map would be an integer. This something like std::map or something.

Then I though maybe use Boost.Functional/Hash, but are there any guarantees that the hash value is unique?

You said:

The object is identified by all its members.

This strongly implies that there are no "forbidden" combinations of values. Which means that any guaranteed-unique hash value would have to be at least as long as the object itself. Really the whole benefit to using a hash value derives from your willingness to tolerate multiple objects hashing to the same value.

How unique are they?

Probably plenty good enough for data structure purposes.

Are there better alternatives?

Probably not :-) If you only have to do this once and it's only a few GB, try doing it with an industrial strength database like PostgreSQL. This is not exactly an elegant C++ solution, but it may very well get the job done quicker. Also, there may be an open source large file sort utility that could preprocess the file in a reasonable time and thus make the counting step a breeze. Otherwise, if this will be an ongoing need and you want to write it in C++: 1. Allocate the largest possible std::bitset that can fit into memory. This is where a 64-bit CPU and OS (even with the same amount of RAM) really helps. 2. Make a pass over the data, indexing the bitset by the object's computed hash value modulo the count of bits. Set the indexed bit. Keep the bitset and pass over the data again, but this time for any bit that's already set, write that object to a 'potential dups' file. 3. Repeat (2) with a different hash function (perhaps just prefix each object with some constant) using the previous 'potential dups' file as input. Do this a few times until the file size stops shrinking. The size of the resulting file gives an upper bound for the number of duplicate values. If there aren't many dups, you may have a small data set now. 4a. If the upper bound suggests its practical, just make a conventional hashtable for mapping the values and their counts. Note that you do need to keep one of each unique value for comparison, because you said "The object is identified by all its members". 4b. If the upper bound is too large to to fit all at once in memory, then make N > 1 passes. Calculate a hash value using yet another variant of the hash function. On the first pass, process as in (4a) but only for elements where hash(prefix + object)%N == 0. On the next pass do those == 1, and so on through N - 1. After each pass, append the objects with counts > 1 to a results file. 5. Pick selected results and confirm them with an additional pass over the data. 6. Use boost in your implementation somewhere. 7. Light fuse and get away? - Marsh