c – 计算大数据流中每个元素的出现次数

我有一个N粒子的模拟,在T时间步长运行.在每个时间步长,每个粒子计算一些关于自身和附近其他粒子(半径内)的数据,这些粒子被打包成4到22个字节长的c-串(取决于附近有多少粒子).我称之为状态字符串.

我需要计算每个状态字符串出现的次数,以形成直方图.我尝试过使用Google的Sparse Hash Map,但是内存开销很疯狂.

我已经运行了一些减少的测试(附加)超过100,000个时间步,500粒子.这导致50mil可能的状态字符串中仅有超过18.2mil的唯一状态字符串,这与需要完成的实际工作一致.

它最终在空间中使用323 MB作为每个唯一条目的char *和int以及实际的状态字符串本身.但是,任务管理器报告使用了870M.这是547M的开销,或大约251.87比特/条目,超过谷歌宣传的大约4-5比特.

所以我认为我必须做错事.但后来我发现了site,它显示了类似的结果,但是,我不确定他的图表是仅显示哈希表大小,还是包括实际数据的大小.此外,他的代码不会释放任何已插入到已存在的散列图中的字符串(意味着如果他的图表确实包含实际数据的大小,它将会结束).

以下是一些显示输出问题的代码：

#include <google/sparse_hash_map>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

//String equality
struct eqstrc
{
    bool operator()(const char* s1,const char* s2) const
    {
        return (s1 == s2) || (s1 && s2 && !strcmp(s1,s2));
    }   
};

//Hashing function
template <class T>
class fnv1Hash
{
public:
    size_t operator()(const T& c) const {
            unsigned int hash = 2166136261;
            const unsigned char *key = (const unsigned char*)(c);
            size_t L = strlen((const char*)c);
            size_t i = 0;
            for(const unsigned char *s = key; i < L; ++s,++i)
                hash = (16777619 * hash) ^ (*s);
            return (size_t)hash;
    }
};

//Function to form new string
char * new_string_from_integer(int num)
{
    int ndigits = num == 0 ? 1 : (int)log10((float)num) + 1;
    char * str = (char *)malloc(ndigits + 1);
    sprintf(str,"%d",num);
    return str;
}

typedef google::sparse_hash_map<const char*,int,fnv1Hash<const char*>,eqstrc> HashCharMap;


int main()
{
    HashCharMap hashMapChar;
    int N = 500;
    int T = 100000;

    //Fill hash table with strings
    for(int k = 0; k < T; ++k)
    {
        for(int i = 0; i < N; ++i)
        {
            char * newString = new_string_from_integer(i*k);
            std::pair<HashCharMap::iterator,bool> res =  hashMapChar.insert(HashCharMap::value_type(newString,HashCharMap::data_type()));
            (res.first)->second++;

            if(res.second == false) //If the string already in hash map,don't need this memory
                free(newString);
        }
    }

    //Count memory used by key 
    size_t dataCount = 0;
    for(HashCharMap::iterator hashCharItr = hashMapChar.begin(); hashCharItr != hashMapChar.end(); ++hashCharItr)
    {
        dataCount += sizeof(char*) + sizeof(unsigned int); //Size of data to store entries
        dataCount += (((strlen(hashCharItr->first) + 1) + 3) & ~0x03); //Size of entries,padded to 4 byte boundaries
    }
    printf("Hash Map Size: %lun",(unsigned long)hashMapChar.size());
    printf("Bytes written: %lun",(unsigned long)dataCount);

    system("pause");
}

产量

Hash Map Size: 18218975
Bytes written: 339018772
Peak Working Set (Reported by TaskManager): 891,228 K
Overhead: 560,155 K,or 251.87 bits/entry

我已经尝试了Google Sparse Hash Map v1.10和v2.0.2.

我在使用哈希映射时做错了什么.或者有更好的方法来解决这个问题,因为使用这些字符串,我几乎可以只存储字符串列表,排序,然后计算连续的条目.

谢谢你的帮助

编辑

因为我被问到,这里是实际数据的格式：
每个组件是2个字节,分为两个子部分. 12位,4位.

>前两个字节(短)：[当前粒子的id(12位)|的角度
当前粒子(4位)]
>第二短：[相互作用的数量
粒子(12位)(N)|以前的当前粒子角度(4位)]
>对于下一个N短裤：[粒子i的id(12位)|粒子的前一个角度i(4位)]

角度近似(除以16),以4位存储.

这有点罗嗦,所以我会写一个例子：

0x120A 0x001B 0x136F =粒子288(0x120),角度为10(0xA).在前一个时间步长有11(0xB)角.与1(0x001)其他粒子交互.这个其他粒子是粒子310(0x136)并且在之前的时间步长中具有角度15(0xF).

粒子与0到9个其他粒子相互作用,因此我上面提到的4-22个字节(尽管很少,可以与多达12个或更多的其他粒子相互作用.没有限制.如果所有500个粒子都在半径范围内,那么该字符串将是1004字节长)

附加信息：哈希函数和比较函数在我的实际代码中使用存储在第二个short的最重要的12位中的大小来进行处理,因为非终端0x0000可以出现在我的状态字符串中.一切正常.