Создание, доступ, хранение и загрузка boost :: bimap эффективным способом

В продолжение с мой предыдущий вопрос по сериализации битов чтобы избежать повторного создания BIMAP для одних и тех же данных, сохраните BIMAP и при необходимости загрузите его.

Я выбрал boost::bimap хранить данные (в битах) в <key,value> пара из-за того, что он использует технику хеширования и нуждается в операции O (1) для поиска. bimap может иметь 40 миллионов записей наборов битов и хочет выполнить следующее.

  1. Вставьте наборы битов в bimap в минимально возможное время. Ответ на мой предыдущий вопрос занимает больше времени (почти 5 секунд для .25 миллионов записей битов, что в 5 раз больше по сравнению с хэш-функцией, указанной в 2 ). По той же причине unordered_set_of а также unordered_multiset_of используется.

  2. я хочу 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);
    }
    };
    }
    
  3. O (1) поиск ключа / значения.

  4. Загрузите BIMAP в короткие сроки. Опять же, загрузка BIMAP занимает много времени (почти 20 секунд для разметки .25 миллионов записей, размер 12 МБ).

Поэтому я хочу достичь 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 или около того).

1

Решение

Вы сформулировали весь вопрос с точки зрения неупорядоченных карт с битами. Что Цель? Какие реальные жизненные проблемы вы моделируете с этим дизайном?

Насколько велики ваши биты? Какова разница в размере? Каково распределение в определенных подмножествах битов? Вы могли бы быть намного лучше с быстрым и грязным специальным хэшем, предполагающим некоторые вещи, чем этот универсальный подход (см. ¹ и ² ниже)

Вы захотите сократить распределение, загрузить «упакованные» данные в контейнер, не основанный на узле, контролировать, когда элементы сортируются (вместо того, чтобы нести этот инвариант все время).

Я добился отличных результатов, поместив такие контейнеры в файл сегмента общей памяти / сопоставленной памяти 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 and, и следующие сроки:

 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

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

² Я заметил, что более старая немасштабирующая реализация хэша была написана Ричардом Ходжесом в старом ответе. Вы видите, что происходит? Вы спрашиваете X, давая слишком мало информации, чтобы люди действительно знали вашу проблему, поэтому вы получаете ответ на X. Но это не оптимально. Ваша настоящая проблема в другом.

StackOverflow может быть заполнен лучшими программистами, но они не будут волшебным образом видеть ваш X / Y проблемы, даже если они чувствуют запах и пытаются вытянуть это. В конце концов, мы не экстрасенсы. Ничто не заменит совместной работы со старшими наставниками / коллегами, которые помогут вам на каждом этапе пути.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector