继续我之前的问题以序列化位集以避免在相同数据上重复创建 bimap，因此请保存 bimap 并在需要时加载。
我选择成对boost::bimap存储数据（在位集中），<key,value>因为它使用散列技术并且需要 O(1) 操作来搜索。bimap可能有 4000 万个位集条目，并希望执行以下操作。
bimap在尽可能短的时间内插入位集。回答我之前的问题需要更多时间（与2下给出的哈希函数相比，25 万个位集条目需要将近 5 秒，是 5 倍）。出于同样的原因unordered_set_of并被unordered_multiset_of使用。与下面的哈希函数不同，我想
bimap尽可能少地消耗内存并避免复制。namespace std { template <typename Block, typename Alloc> struct hash<boost::dynamic_bitset<Block, Alloc> > { using bitset_type = boost::dynamic_bitset<Block, Alloc>; using block_type = typename bitset_type::block_type ; size_t operator()(boost::dynamic_bitset<Block, Alloc> const& bs) const { thread_local static std::vector<block_type> block_data; auto blocks = bs.num_blocks(); block_data.assign(blocks, 0); to_block_range(bs, block_data.begin()); return boost::hash<std::vector<block_type>>()(block_data); } }; }O(1) 搜索键/值。
在短时间内加载bimap。同样，加载 bimap 需要很长时间（对于 25 万个条目、大小为 12 MB 的 bimap 大约需要 20 秒）。
因此，我想针对我已经提出的问题实现 1、2、3 和 4 ，其答案代码@sehe如下所示。
#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/bimap.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/dynamic_bitset/serialization.hpp>
#include <fstream>
#include <iostream>
#include <string>
#include <boost/iostreams/device/back_inserter.hpp>
#include <boost/iostreams/stream_buffer.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/functional/hash.hpp>
namespace serial_hashing { // see https://stackoverflow.com/questions/30097385/hash-an-arbitrary-precision-value-boostmultiprecisioncpp-int
namespace io = boost::iostreams;
struct hash_sink {
hash_sink(size_t& seed_ref) : _ptr(&seed_ref) {}
typedef char char_type;
typedef io::sink_tag category;
std::streamsize write(const char* s, std::streamsize n) {
boost::hash_combine(*_ptr, boost::hash_range(s, s+n));
return n;
}
private:
size_t* _ptr;
};
template <typename T> struct hash_impl {
size_t operator()(T const& v) const {
using namespace boost;
size_t seed = 0;
{
iostreams::stream<hash_sink> os(seed);
archive::binary_oarchive oa(os, archive::no_header | archive::no_codecvt);
oa << v;
}
return seed;
}
};
}
namespace std {
template <typename Block, typename Alloc> struct hash<boost::dynamic_bitset<Block, Alloc> >
: serial_hashing::hash_impl<boost::dynamic_bitset<Block, Alloc> >
{};
} // namespace std
namespace bimaps = boost::bimaps;
using Bitset = boost::dynamic_bitset<>;
typedef boost::bimap<
bimaps::unordered_set_of<Bitset, std::hash<Bitset> >,
bimaps::unordered_multiset_of<Bitset, std::hash<Bitset> > > Index;
int main() {
using namespace std::string_literals;
{
std::cout << "# Writing binary file ... " << std::endl;
Index index;
index.insert({Bitset("10010"s), Bitset("1010110110101010101"s)});
std::ofstream ofs("binaryfile", std::ios::binary);
boost::archive::binary_oarchive oa(ofs);
oa << index;
}
{
std::cout << "# Loading binary file ... " << std::endl;
std::ifstream ifs("binaryfile", std::ios::binary); // name of loading file
boost::archive::binary_iarchive ia(ifs);
Index index;
ia >> index;
}
}
编辑
AIM
我有一个真实的例子，我有一个大字符串，例如 2000 或更多百万个字符，例如 40-1 亿个长度为 200 或更多字符的短字符串。我的目标是在大字符串中搜索这些短字符串。我想bimap为大字符串创建位集，然后在 bimap 中搜索短字符串。我还想用它unordered来非常快地获得插入和搜索，不像ordered.
密钥位集长度约为 3-40（一次所有组合）。
值位集长度在 100-2000 左右（一次只有一个，例如如果它是 100，那么所有值条目将在 90-110 左右）。