Подсчитайте вхождение каждого элемента в большой поток данных

У меня есть симуляция с N частицами, бегущими по T временным шагам. На каждом временном шаге каждая частица вычисляет некоторые данные о себе и других соседних частицах (в пределах радиуса), которые упакованы битами в c-строку длиной 4-22 байта (в зависимости от того, сколько существует соседних частиц). Я называю это государственной строкой.

Мне нужно посчитать, сколько раз встречается каждая строка состояния, чтобы сформировать гистограмму. Я пытался использовать Google Sparse Hash Map, но накладные расходы памяти сумасшедшие.

Я провел несколько сокращенных тестов (прилагается) более 100 000 временных шагов, для 500 частиц. В результате получается более 18,2 млн уникальных строк состояния из 50 млн возможных строк состояния, что соответствует фактической работе, которую необходимо выполнить.

В итоге используется 323 МБ свободного пространства для символа * и int для каждой уникальной записи, а также сама строка фактического состояния. Однако диспетчер задач сообщает об использовании 870M. Это 547 млн. Служебных данных, или ~ 251,87 бит / запись, по сравнению с тем, что Google рекламирует примерно в 4-5 битах.

Поэтому я полагаю, что я должен делать что-то не так. Но потом я нашел это сайт, который показал аналогичные результаты, однако, я не уверен, что его диаграммы показывают только размер хеш-таблицы, или включают в себя размер фактических данных. Кроме того, его код не освобождает какие-либо строки, вставляемые в уже существующую хеш-карту (то есть, если его диаграммы включают в себя размер фактических данных, он будет закончен).

Вот некоторый код, показывающий проблему с выводом:

#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 Sparse Hash Map v1.10 и v2.0.2.

Я делаю что-то не так при использовании хэш-карты. Или есть лучший способ приблизиться к этому, потому что с этими строками я почти так же хорошо бы просто сохранил список строк, отсортировал их, а затем посчитал последовательные записи.

Спасибо за любую помощь

Поскольку меня спросили, вот формат фактических данных:
Каждый компонент имеет размер 2 байта и разбит на две части. 12бит и 4 бита.

• Первые два байта (короткие): [id текущей частицы (12 бит) | угол
  текущая частица (4 бита)]
• Второй короткий: [количество взаимодействующих
  частицы (12 бит) (N) | предыдущий угол текущей частицы (4 бита)]
• Для следующих N шорт: [id частицы i (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 байта)

Дополнительная информация: Хеширующая функция и функция сравнения в моем фактическом коде используют размер, сохраненный в 12 старших значащих битах второго короткого замыкания, для выполнения обработки, поскольку в моих строках состояния могут появляться нетерминальные значения 0x0000. Это все работает отлично.