计算大数据流中每个元素的出现情况。

Question

我有一个模拟，有N个粒子，运行在T个时间步骤上。在每个时间步骤中，每个粒子计算关于自己和附近(半径内)的其他粒子的一些数据，这些数据被压缩成4-22字节长的c-字符串(取决于附近粒子的数量)。我把这叫做国家线。

我需要计算每个状态字符串发生多少次，以形成一个直方图。我试过使用Google的稀疏哈希地图，但是内存开销太大了。

我已经对500个粒子进行了超过100,000次的测试(附加)。这导致了50000个可能的状态字符串中的1820万个唯一状态字符串，这与实际需要完成的工作是一致的。

它在空间中对char*和int对每个唯一条目以及实际状态字符串本身使用323 MB。然而，任务管理器正在报告使用了870 M。这是5.47亿的开销，或251.87位/项，远远超过谷歌广告的4-5位。

所以我想我肯定做错了什么。但是，我发现了这个站点，它显示了类似的结果，但是，我不确定他的图表是否只显示了哈希表大小，或者包括实际数据的大小。此外，他的代码没有释放任何插入到已经存在的hashmap中的字符串(这意味着如果他的图表中包含了实际数据的大小，它就会结束)。

下面是一些代码，显示了输出的问题：

#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: %lu\n", (unsigned long)hashMapChar.size());
    printf("Bytes written: %lu\n", (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稀疏哈希地图v1.10和v2.0.2。

我在使用散列图时做错了什么吗？或者有更好的方法来解决这个问题，因为有了这些字符串，我几乎可以只存储字符串列表，排序，然后计数连续的条目。

谢谢你的帮助

编辑

因为我是被问到的，这里是实际数据的格式:每个组件是两个字节，并分成两个子部分。12位，4位。

• 前两个字节(短)：当前粒子的id (12位)当前粒子的角(4位)
• 第二小段:相互作用粒子数(12位)(N)x当前粒子的前角(4位)
• 下一个N个短片:I粒子的id (12位)x粒子的前角(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字节长)

附加信息:在我的实际代码中，哈希函数和比较函数使用存储在第二个短的12位中最重要的大小来进行处理，因为非终端0x0000s可以出现在我的状态字符串中。一切都很好。

Answer 1

这些数据来自于gcc在Linux上的实验。分配4-22字节的短块需要16字节的长度(从1-12字节)、24个字节(13-20字节)和32个字节(其余字节)。

这意味着您对18218975字符串(“0”.“50000000”)的实验需要堆上291503600字节，其长度之和(加上尾随0)为156681483。

因此，仅仅由于malloc，您就有135 to的开销。

(这个峰值工作装置的大小是可靠的吗？)