以前の質問の続きとして、ビットセットをシリアル化して、同じデータに対して bimap を繰り返し作成しないようにするため、必要に応じて bimap を保存してロードします。
ハッシュ技術を使用し、検索に O(1) 操作が必要なため、データ (ビットセット) をペアでboost::bimap格納することにしました。<key,value>にはbimap4,000 万のビットセット エントリがあり、次の操作を実行する場合があります。
最小限の時間でビットセットを挿入し
bimapます。私の以前の質問への回答には、より多くの時間がかかります( 2で指定されたハッシュ関数と比較すると、5 倍の 2500 万ビットセット エントリで約 5 秒)。同じ理由unordered_set_ofで andunordered_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 のロードにはかなりの時間がかかります(25 万エントリの bimap、サイズ 12 MB の場合、約 20 秒)。
したがって、回答コード@seheが以下に示されている、すでに尋ねられた質問に対して1、2、3、および4を達成したいと考えています。
#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万文字以上の大きな文字列と、長さ200文字以上の4000万から1億文字の短い文字列がある実際の例を持っています。私の目的は、これらの短い文字列を大きな文字列で検索することです。大きな文字列のビットセットを作成してからbimap、バイマップで短い文字列を検索することを考えました。unorderedとは異なり、挿入と検索を非常に高速に行うために使用することも考えましたordered。
キー ビットセットの長さは 3 ～ 40 程度です (一度にすべての組み合わせ)。
値のビットセットの長さは約 100 ～ 2000 です (たとえば、100 の場合は一度に 1 つだけです。すべての値のエントリは約 90 ～ 110 程度になります)。