Неупорядоченная карта занимает много места

Question

Я создал карту от unit64_t до uint64_t. Вот код, который я написал для оценки сложности пространства:

#include <bits/stdc++.h>
#include "sparsehash/internal/sparseconfig.h"
#include "sparsehash/sparse_hash_map"

using namespace std;

int main(int argc, char *argv[]){

    std::string input,reference;

    while (getline(cin,input)) {
    reference += input;
    input.clear();
    }

    cout<<"length of reference = "<<reference.length()<<endl;
    unordered_map<uint64_t, uint64_t> m;
    //google::sparse_hash_map<uint64_t, pair<short,long>> m;

    for (auto it = reference.begin(); it != reference.end(); it++) {
        m[it-reference.begin()]= it-reference.begin();
    }

    return 0;
}

Когда я запускаю это с /usr/bin/time, это вывод, полученный программой:

length of reference = 4641652
    Command being timed: "./a.out"
    User time (seconds): 2.97
    System time (seconds): 0.15
    Percent of CPU this job got: 99%
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.13
    Average shared text size (kbytes): 0
    Average unshared data size (kbytes): 0
    Average stack size (kbytes): 0
    Average total size (kbytes): 0
    Maximum resident set size (kbytes): 251816
    Average resident set size (kbytes): 0
    Major (requiring I/O) page faults: 0
    Minor (reclaiming a frame) page faults: 68259
    Voluntary context switches: 1
    Involuntary context switches: 104
    Swaps: 0
    File system inputs: 0
    File system outputs: 0
    Socket messages sent: 0
    Socket messages received: 0
    Signals delivered: 0
    Page size (bytes): 4096
    Exit status: 0

Кажется, что неупорядоченная карта занимает 250 МБ пространства. Это кажется необычно высоким. Почему это случилось? Тот же код с разреженным хешем Google занимает всего 89 МБ, что более разумно.

Я не понимаю, почему неупорядоченная карта C++ занимает так много места?

Answer 1

У тебя есть 4641652 записей. Таким образом, общий размер необработанных данных 4641652*2*8 byte ~= 74 MB,

Есть важный факт о хеш-таблицах. Быстрые хеш-таблицы имеют много хеш-блоков, а хеш-таблицы с небольшим количеством хеш-таблиц работают медленно.

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

Сейчас std::unordered_map по-мужски обозначается как быстрый хэш-стол, поэтому у него довольно много накладных расходов. Хэш-блоков гораздо больше, чем записей. В этом случае накладные расходы составляют около 250 / 74 ~= 3.3xчто вполне нормально.

Но sparsehash разработан так, чтобы иметь как можно меньше служебных данных (около 2 бит на запись). Но, конечно, это означает, что это намного медленнее.

Если вы используете хэш-карту, вы всегда должны думать о том, хотите ли вы скорость или вы хотите эффективно использовать память.