В продолжение с мой предыдущий вопрос по сериализации битов чтобы избежать повторного создания BIMAP для одних и тех же данных, сохраните BIMAP и при необходимости загрузите его.
Я выбрал boost::bimap
хранить данные (в битах) в <key,value>
пара из-за того, что он использует технику хеширования и нуждается в операции O (1) для поиска. bimap
может иметь 40 миллионов записей наборов битов и хочет выполнить следующее.
Вставьте наборы битов в bimap
в минимально возможное время. Ответ на мой предыдущий вопрос занимает больше времени (почти 5 секунд для .25 миллионов записей битов, что в 5 раз больше по сравнению с хэш-функцией, указанной в 2 ). По той же причине 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 занимает много времени (почти 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 или около того).
Вы сформулировали весь вопрос с точки зрения неупорядоченных карт с битами. Что Цель? Какие реальные жизненные проблемы вы моделируете с этим дизайном?
Насколько велики ваши биты? Какова разница в размере? Каково распределение в определенных подмножествах битов? Вы могли бы быть намного лучше с быстрым и грязным специальным хэшем, предполагающим некоторые вещи, чем этот универсальный подход (см. ¹ и ² ниже)
Вы захотите сократить распределение, загрузить «упакованные» данные в контейнер, не основанный на узле, контролировать, когда элементы сортируются (вместо того, чтобы нести этот инвариант все время).
Я добился отличных результатов, поместив такие контейнеры в файл сегмента общей памяти / сопоставленной памяти Boost Interprocess.
Я использовал следующий код для тестирования производительности / сохранения / загрузки данных.
Обратите внимание, что это не реализует ни одно из вышеупомянутых предложений, за исключением того, что оно отказывается от выбора хэш-таблицы. Отсутствие необходимости создания экземпляра архива каждый раз, когда вы вставляете или просматриваете ключ, очень поможет. Кроме того, помните, что хэш-таблицы перефразируют при достижении коэффициента загрузки. Настройка очень важна для того, чтобы они работали без сбоев.
#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 проблемы, даже если они чувствуют запах и пытаются вытянуть это. В конце концов, мы не экстрасенсы. Ничто не заменит совместной работы со старшими наставниками / коллегами, которые помогут вам на каждом этапе пути.
Других решений пока нет …