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

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/время, это выход производится по программе:

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 В настоящее время std::unordered_map мужественный desiged как быстрый хеш-стол, поэтому он имеет довольно много накладных расходов. Есть гораздо больше хэш-ведер, чем записи. В этом случае накладные расходы составляют около 250/74 ~= 3.3x, что кажется вполне нормальным.

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

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