BiMap

BiMap

关注
发信
关注(28)粉丝(399)

c++ - 有效创建，访问，存储和加载boost::bimap

继续使用my earlier question to serialize bitsets可以避免在相同数据上重复创建bimap，因此请保存bimap并在需要时加载。

我之所以选择boost::bimap将数据(按位集)存储在<key,value>对中，是因为它使用哈希技术并且需要O(1)操作进行搜索。 bimap可能具有4000万个位集条目，并想要执行以下操作。

  • 在尽可能短的时间内在bimap中插入位集。 Answer to my earlier question takes more time(大约0.25万个位集条目的时间为5秒，与 2 下给出的哈希函数相比，是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。 Again, loading bimap takes much time(对于25万个条目的双图，将近20秒，大小为12 MB)。

    • 所以我想实现my already asked question的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-100亿个长度为200个或更多个字符的短字符串。我的目的是在大字符串中搜索这些短字符串。我想为大字符串创建位集的bimap，然后在bimap中搜索短字符串。我还认为与unordered不同，使用ordered可以非常快速地进行插入和搜索。

    密钥位长度在3到40之间(一次全部组合)。

    值位集长度在100-2000左右(例如一次只有一个，如果是100，则所有值条目将在90-110左右)。

    最佳答案

    您用带位集的无序映射来构图整个问题。目标是什么？您在使用此设计建模时遇到哪些现实问题？

    您的比特集有多大？大小有何差异？某些位子集的分布是什么？与某些通用方法相比，使用快速脏的临时哈希假设某些事情可能会更好(请参见下面的¹和²)

    您将需要减少分配，将“打包的”数据加载到基于非节点的容器中，控制对元素进行排序的时间(而不是始终保持不变)。

    将此类容器放入Boost Interprocess共享内存段/内存映射文件中，我取得了优异的成绩。

    基准测试

    我使用以下代码对生成/保存/加载数据进行基准测试。



    Live On Wandbox 

    #include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/dynamic_bitset/serialization.hpp>
#include <fstream>
#include <vector>
#include <random>
#include <chrono>
#include <iostream>

namespace bimaps = boost::bimaps;
using Block = uint32_t;
using Bitset = boost::dynamic_bitset<Block>;

typedef boost::bimap<bimaps::set_of<Bitset>, bimaps::multiset_of<Bitset>> Index;

template <typename Caption, typename F>
auto timed(Caption const& task, F&& f) {
    using namespace std::chrono;
    using namespace std::chrono_literals;
    struct _ {
        high_resolution_clock::time_point s;
        Caption const& task;
        ~_() { std::cout << " -- (" << task << " completed in " << (high_resolution_clock::now() - s) / 1.0s << "s)\n"; }
    } timing { high_resolution_clock::now(), task };

    return f();
}

int main(int argc, char**) {
    using namespace std::string_literals;

    auto gen_bitset = [
        data=std::vector<Block>(64), // max 2048 bits
        prng=std::mt19937{42} // { std::random_device{}() }
    ]() mutable {
        auto length_gen = std::uniform_int_distribution<size_t>(data.size()/2, data.size());
        auto block_gen = std::uniform_int_distribution<Block>{};

        size_t n = length_gen(prng);
        std::generate_n(data.begin(), n, [&]{ return block_gen(prng); });

        return Bitset(data.begin(), data.begin()+n);
    };

    if (argc>1) {
        std::cout << "# Creating ... " << std::endl;
        Index index;

        timed("Generating data set", [&] {
            for (size_t i = 0; i < 52<<19; ++i) {
                index.insert({gen_bitset(), gen_bitset()});
            }
        });

        timed("Writing binary file", [&] {
            std::ofstream ofs("binaryfile", std::ios::binary);
            boost::archive::binary_oarchive oa(ofs);
            oa << index;
        });
        std::cout << "Written " << index.size() << " key/value pairs\n";
    } else {
        std::cout << "# Loading ... " << std::endl;
        Index index;

        timed("Loading binary file", [&] {
            std::ifstream ifs("binaryfile", std::ios::binary); // name of loading file
            boost::archive::binary_iarchive ia(ifs);
            ia >> index;
        });

        std::cout << "Roundtripped " << index.size() << " key/value pairs\n";
    }
}

    这将创建一个11G文件，其中包含27262976个键/值对。所有键和值都是统一的随机比特集，其长度均匀地分布在1024..2048位之间。
     rm binaryfile
 time ./sotest 1
     -- (Generating data set completed in 228.499s)
     -- (Writing binary file completed in 106.083s)
    Written 27262976 key/value pairs

    real    5m48.362s
    user    5m32.876s
    sys     0m14.704s
 ls -ltrah binaryfile
    -rw-rw-r-- 1 sehe sehe 11G dec 14 01:16 binaryfile
 time ./sotest
    # Loading binary file ...
     -- (Loading binary file completed in 135.167s)
    Roundtripped 27262976 key/value pairs

    real    2m19.397s
    user    2m11.624s
    sys     0m7.764s

    将数据集减少到25万个条目时，我得到的文件为106MiB¹，其计时如下:
     rm binaryfile
 time ./sotest 1
    # Creating ...
     -- (Generating data set completed in 1.13267s)
     -- (Writing binary file completed in 0.586325s)
    Written 262144 key/value pairs

    real    0m1.825s
    user    0m1.676s
    sys     0m0.140s
 ls -ltrah binaryfile
    -rw-rw-r-- 1 sehe sehe 106M dec 14 01:44 binaryfile
 time ./sotest
    # Loading ...
     -- (Loading binary file completed in 0.776928s)
    Roundtripped 262144 key/value pairs

    real    0m0.823s
    user    0m0.764s
    sys     0m0.056s

    ¹这基本上告诉我您的位集要小得多-我认为这可能会强烈支持其他数据结构选择

    ²我注意到较早的非缩放哈希实现是由Richard Hodges in an older answer编写的。你看到发生了什么事吗？您要求提供X，却给人们提供的信息太少，使他们无法真正了解您的问题，因此您无法获得X的答案。但这并不是最佳选择。您真正的问题是其他问题。

    最好的程序员可能会使用StackOverflow进行填充，但是即使他们闻到了气味并试图将其绘制出来，他们也不会神奇地看到X/Y problems。最后，我们不是通灵主义者。与高级导师/同事合作无可替代，可以为您提供指导。

    关于c++ - 有效创建，访问，存储和加载boost::bimap，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47798781/

    10-11 00:32
    Powered by LMLPHP ©2024 BiMap 0.026775