更快地从/向文件读取/写入std :: unordered_map的方法

Question

我正在处理一些非常大std::unordered_map的(数亿条目),需要将它们保存到文件中并从文件中加载它们.我目前这样做的方法是迭代地图并一次读取/写入每个键和值对:

std::unordered_map<unsigned long long int, char> map;

void save(){
    std::unordered_map<unsigned long long int, char>::iterator iter;
    FILE *f = fopen("map", "wb");
    for(iter=map.begin(); iter!=map.end(); iter++){
        fwrite(&(iter->first), 8, 1, f);
        fwrite(&(iter->second), 1, 1, f);
    }
    fclose(f);
}

void load(){
    FILE *f = fopen("map", "rb");
    unsigned long long int key;
    char val;
    while(fread(&key, 8, 1, f)){
        fread(&val, 1, 1, f);
        map[key] = val;
    }
    fclose(f);
}

但是有大约6.24亿条记录,从文件中读取地图需要9分钟.写入文件速度更快但仍需要几分钟.有更快的方法吗？

Answer 1

C++ unordered_map实现必须全部使用链接.您可能希望为通用哈希表执行此操作有很多非常好的理由,这将在此处讨论.

这对性能有很大的影响.最重要的是,这意味着哈希表的条目可能以一种方式分散在整个内存中,这使得访问每个条目的数量级(或左右)效率较低,如果它们可以以某种方式串行访问的话.

幸运的是,您可以构建哈希表,这些哈希表几乎已满,可以对相邻元素进行近似顺序访问.这是使用开放寻址完成的.

由于您的哈希表不是通用的,您可以试试这个.

下面,我构建了一个带有开放寻址和线性探测的简单哈希表容器.它假设了一些事情:

1. 你的密钥已经以某种方式随机分布.这消除了对散列函数的需要(尽管很好的散列函数构建相当简单,即使难以实现很好的散列函数).

2. 您只需要向哈希表添加元素,不要删除它们.如果不是这种情况下,你需要改变used矢量到的东西,可容纳三种状态:USED,UNUSED,和TOMBSTONE那里TOMBSTONE是一个表示删除的元素的和用于继续线性搜索探头或暂停直线插入探头.

3. 您提前知道哈希表的大小,因此您不需要调整大小/重新散列它.

4. 您不需要以任何特定顺序遍历元素.

当然,可能存在各种在线开放寻址哈希表的优秀实现,它们解决了上述许多问题.然而,我桌子的简洁性让我能够传达重要的观点.

重要的是:我的设计允许将所有哈希表的信息存储在三个向量中.那就是:记忆是连续的.

连续内存分配速度快,读取速度快,写入速度快.这种影响是深远的.

使用与我之前的答案相同的测试设置,我得到以下时间:

Save. Save time = 82.9345 ms
Load. Load time = 115.111 ms

节省时间减少95%(快22倍),加载时间减少98%(快62倍).

码:

#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

const int TEST_TABLE_SIZE = 10000000;



template<class K, class V>
class SimpleHash {
 public:
  int usedslots = 0;

  std::vector<K> keys;
  std::vector<V> vals;
  std::vector<uint8_t> used;

  //size0 should be a prime and about 30% larger than the maximum number needed
  SimpleHash(int size0){
    vals.resize(size0);
    keys.resize(size0);
    used.resize(size0/8+1,0);
  }

  //If the key values are already uniformly distributed, using a hash gains us
  //nothing
  uint64_t hash(const K key){
    return key;
  }

  bool isUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    return used[used_loc]&used_bit;    
  }

  void setUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    used[used_loc] |= used_bit;
  }

  void insert(const K key, const V val){
    uint64_t loc = hash(key)%keys.size();

    //Use linear probing. Can create infinite loops if table too full.
    while(isUsed(loc)){ loc = (loc+1)%keys.size(); }

    setUsed(loc);
    keys[loc] = key;
    vals[loc] = val;
  }

  V& get(const K key) {
    uint64_t loc = hash(key)%keys.size();

    while(true){
      if(!isUsed(loc))
        throw std::runtime_error("Item not present!");
      if(keys[loc]==key)
        return vals[loc];

      loc = (loc+1)%keys.size();
    }
  }

  uint64_t usedSize() const {
    return usedslots;
  }

  uint64_t size() const {
    return keys.size();
  }
};

typedef SimpleHash<uint64_t, char> table_t;

void SaveSimpleHash(const table_t &map){
  std::cout<<"Save. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "wb");
  uint64_t size = map.size();
  fwrite(&size, 8, 1, f);
  fwrite(map.keys.data(), 8, size, f);
  fwrite(map.vals.data(), 1, size, f);
  fwrite(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

table_t LoadSimpleHash(){
  std::cout<<"Load. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");

  uint64_t size;
  fread(&size, 8, 1, f);

  table_t map(size);
  fread(map.keys.data(), 8, size, f);
  fread(map.vals.data(), 1, size, f);
  fread(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;

  return map;
}

int main(){
  //Perfectly horrendous way of seeding a PRNG, but we'll do it here for brevity
  auto generator = std::mt19937(12345); //Combination of my luggage
  //Generate values within the specified closed intervals
  auto key_rand  = std::bind(std::uniform_int_distribution<uint64_t>(0,std::numeric_limits<uint64_t>::max()), generator);
  auto val_rand  = std::bind(std::uniform_int_distribution<int>(std::numeric_limits<char>::lowest(),std::numeric_limits<char>::max()), generator);

  table_t map(1.3*TEST_TABLE_SIZE);
  std::cout<<"Created table of size "<<map.size()<<std::endl;

  std::cout<<"Generating test data..."<<std::endl;
  for(int i=0;i<TEST_TABLE_SIZE;i++)
    map.insert(key_rand(),(char)val_rand()); //Low chance of collisions, so we get quite close to the desired size

  map.insert(23,42);
  assert(map.get(23)==42);

  SaveSimpleHash(map);
  auto newmap = LoadSimpleHash();

  //Ensure that the load worked
  for(int i=0;i<map.keys.size();i++)
    assert(map.keys.at(i)==newmap.keys.at(i));
  for(int i=0;i<map.vals.size();i++)
    assert(map.vals.at(i)==newmap.vals.at(i));  
  for(int i=0;i<map.used.size();i++)
    assert(map.used.at(i)==newmap.used.at(i));    
}

Answer 2

我假设您需要地图来写入文件中订购的值。最好只加载一次容器中的值，可能 astd::deque会更好，因为数量很大，并且使用std::sort一次，然后迭代std::deque写入值。您将获得缓存性能，并且运行时复杂度为std::sortN*Log(N)，这比平衡映射约 6.24 亿次或在无序映射中支付缓存未命中要好。