用 cpp_int 建立巨大的提升 unordered_map
Building a large boost unordered_map with cpp_int
我正在用 C++ 编写一些代码,用于 class 需要使用多精度库(例如 boost)的作业。基本上,我需要用一些大整数构建一个散列 table,然后在 table.
中查找某个值
当我使用被注释掉的 h、g、p 时 - 代码 运行 很好而且很快。一旦我切换到那些未被注释掉的那些,它就会在以下行抛出内存异常:hash_str>::iterator got = mp.find(lkp);
我刚开始使用 C++,并且很确定有些事情已经发生了,因为这应该 运行 相当快,即使有很大的数字。
#include <boost/unordered_map.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/math/special_functions/pow.hpp>
using namespace std;
using namespace boost::multiprecision;
template <typename T>
struct hash_str
{
size_t operator()( const T& t ) const
{
return std::hash<std::string>()
( t.str() );
}
};
int main()
{
boost::unordered_map<cpp_int, cpp_int, hash_str<cpp_int>> mp;
//boost::unordered_map<hash_str<cpp_int>, cpp_int, hash_str<cpp_int>> mp;
cpp_int k;
cpp_int h( "3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333" );
cpp_int g( "11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568" );
//cpp_int g = 1010343267;
//cpp_int h = 857348958;
//cpp_int p = 1073676287;
cpp_int p( "13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171" );
int b = pow( 2, 20 );
cpp_int denom;
cpp_int inv = powm( g, p - 2, p );
//building a hash table of all values h/g^x1
for ( cpp_int x = 1; x < b; ++x )
{
// go through all 2^20 values up to b, calculate the function h/g^x1,
// then hash it to put into table
denom = powm( inv, x, p );
k = ( h *denom ) % p;
mp.insert( std::make_pair( k, x ) );
}
cpp_int lkp;
for ( int v = 1; v < b; ++v )
{
//cpp_int gb = pow(g, b);
lkp = powm( g, v*b, p );
//looking for a match for g^b^x0 in map mp; when found we need to find x
//which is x1 and then calc 'x'
boost::unordered::unordered_map<cpp_int, cpp_int, hash_str<cpp_int>>::iterator got = mp.find( lkp );
// Check if iterator points to end of map or if we found our value
if ( got != mp.end() )
{
std::cout << "Element Found - ";
//std::cout << got->first << "::" << got->second << std::endl;
}
/*else
{
std::cout << "Element Not Found" << std::endl;
}*/
}
return 0;
}
以防万一,这是我得到的异常:
MiM.exe 中 0x768F2F71 处的未处理异常:Microsoft C++ 异常:boost::exception_detail::clone_impl > 在内存位置 0x0109EF5C。
散列函数非常糟糕,因为它分配一个临时字符串只是为了对其进行散列。该字符串的长度为 log(bits)/log(10) 字节。
散列的要点在于它是一种相对比较数字的快速方法。对于如此昂贵的散列,您最好使用常规的 Tree 容器(std::map<> 例如)。
- 我没有检查你的公式(尤其是在
h/g^x1
附近,因为我什至不确定 x
代表 x1
)。除了那个问题,
- 我认为
v * b
溢出 int 容量存在正确性问题,至少如果您使用的是 32 位整数编译器。
我稍微清理了一下,它运行了
#include <boost/math/special_functions/pow.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/unordered_map.hpp>
#include <chrono>
namespace bmp = boost::multiprecision;
using namespace std::chrono_literals;
using Clock = std::chrono::high_resolution_clock;
template <typename T> struct hash_str {
size_t operator()(const T &t) const { return std::hash<std::string>()(t.str()); }
};
template <typename T> struct hash_bin {
size_t operator()(const T &t) const {
return boost::hash_range(t.backend().limbs(), t.backend().limbs()+t.backend().size());
}
};
int main() {
using bmp::cpp_int;
boost::unordered_map<cpp_int, cpp_int, hash_bin<cpp_int> > mp;
#if 1
cpp_int const h("32394751040504504435652643787280657886490975209524495278347924529719819761432925580738569379585531805328"
"78928001494706097394108577585732452307673444020333");
cpp_int const g("11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928"
"594829675428279466566527115212748467589894601965568");
cpp_int const p("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690"
"031858186486050853753882811946569946433649006084171");
#else
cpp_int const g = 1010343267;
cpp_int const h = 857348958;
cpp_int const p = 1073676287;
#endif
int constexpr b = 1 << 20;
cpp_int const inv = powm(g, p - 2, p);
{
auto s = Clock::now();
// building a hash table of all values h/g^x1
for (cpp_int x = 1; x < b; ++x) {
// go through [1, b), calculate the function h/g^x1,
// then hash it to put into table
cpp_int denom = powm(inv, x, p);
cpp_int k = (h * denom) % p;
mp.emplace(std::move(k), x);
}
std::cout << "Built map in " << (Clock::now() - s)/1.0s << "s\n";
}
{
auto s = Clock::now();
for (cpp_int v = 1; v < b; ++v) {
//std::cout << "v=" << v << " b=" << b << "\n";
// cpp_int gb = pow(g, b);
cpp_int const lkp = powm(g, v * b, p);
// looking for a match for g^b^x0 in map mp; when found we need to find x
// which is x1 and then calc 'x'
auto got = mp.find(lkp);
// Check if iterator points to end of map or if we found our value
if (got != mp.end()) {
std::cout << "Element Found - ";
//std::cout << got->first << " :: " << got->second << "\n";
}
}
std::cout << "Completed queries in " << (Clock::now() - s)/1.0s << "s\n";
}
}
它对我来说是 1 分钟 4 秒。
Built map in 24.3809s
Element Found - Completed queries in 39.2463s
...
使用 hash_str
而不是 hash_bin
需要 1 分 13 秒:
Built map in 30.3923s
Element Found - Completed queries in 42.488s
我正在用 C++ 编写一些代码,用于 class 需要使用多精度库(例如 boost)的作业。基本上,我需要用一些大整数构建一个散列 table,然后在 table.
中查找某个值当我使用被注释掉的 h、g、p 时 - 代码 运行 很好而且很快。一旦我切换到那些未被注释掉的那些,它就会在以下行抛出内存异常:hash_str>::iterator got = mp.find(lkp); 我刚开始使用 C++,并且很确定有些事情已经发生了,因为这应该 运行 相当快,即使有很大的数字。
#include <boost/unordered_map.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/math/special_functions/pow.hpp>
using namespace std;
using namespace boost::multiprecision;
template <typename T>
struct hash_str
{
size_t operator()( const T& t ) const
{
return std::hash<std::string>()
( t.str() );
}
};
int main()
{
boost::unordered_map<cpp_int, cpp_int, hash_str<cpp_int>> mp;
//boost::unordered_map<hash_str<cpp_int>, cpp_int, hash_str<cpp_int>> mp;
cpp_int k;
cpp_int h( "3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333" );
cpp_int g( "11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568" );
//cpp_int g = 1010343267;
//cpp_int h = 857348958;
//cpp_int p = 1073676287;
cpp_int p( "13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171" );
int b = pow( 2, 20 );
cpp_int denom;
cpp_int inv = powm( g, p - 2, p );
//building a hash table of all values h/g^x1
for ( cpp_int x = 1; x < b; ++x )
{
// go through all 2^20 values up to b, calculate the function h/g^x1,
// then hash it to put into table
denom = powm( inv, x, p );
k = ( h *denom ) % p;
mp.insert( std::make_pair( k, x ) );
}
cpp_int lkp;
for ( int v = 1; v < b; ++v )
{
//cpp_int gb = pow(g, b);
lkp = powm( g, v*b, p );
//looking for a match for g^b^x0 in map mp; when found we need to find x
//which is x1 and then calc 'x'
boost::unordered::unordered_map<cpp_int, cpp_int, hash_str<cpp_int>>::iterator got = mp.find( lkp );
// Check if iterator points to end of map or if we found our value
if ( got != mp.end() )
{
std::cout << "Element Found - ";
//std::cout << got->first << "::" << got->second << std::endl;
}
/*else
{
std::cout << "Element Not Found" << std::endl;
}*/
}
return 0;
}
以防万一,这是我得到的异常: MiM.exe 中 0x768F2F71 处的未处理异常:Microsoft C++ 异常:boost::exception_detail::clone_impl > 在内存位置 0x0109EF5C。
散列函数非常糟糕,因为它分配一个临时字符串只是为了对其进行散列。该字符串的长度为 log(bits)/log(10) 字节。
散列的要点在于它是一种相对比较数字的快速方法。对于如此昂贵的散列,您最好使用常规的 Tree 容器(std::map<> 例如)。
- 我没有检查你的公式(尤其是在
h/g^x1
附近,因为我什至不确定x
代表x1
)。除了那个问题, - 我认为
v * b
溢出 int 容量存在正确性问题,至少如果您使用的是 32 位整数编译器。
我稍微清理了一下,它运行了
#include <boost/math/special_functions/pow.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/unordered_map.hpp>
#include <chrono>
namespace bmp = boost::multiprecision;
using namespace std::chrono_literals;
using Clock = std::chrono::high_resolution_clock;
template <typename T> struct hash_str {
size_t operator()(const T &t) const { return std::hash<std::string>()(t.str()); }
};
template <typename T> struct hash_bin {
size_t operator()(const T &t) const {
return boost::hash_range(t.backend().limbs(), t.backend().limbs()+t.backend().size());
}
};
int main() {
using bmp::cpp_int;
boost::unordered_map<cpp_int, cpp_int, hash_bin<cpp_int> > mp;
#if 1
cpp_int const h("32394751040504504435652643787280657886490975209524495278347924529719819761432925580738569379585531805328"
"78928001494706097394108577585732452307673444020333");
cpp_int const g("11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928"
"594829675428279466566527115212748467589894601965568");
cpp_int const p("13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690"
"031858186486050853753882811946569946433649006084171");
#else
cpp_int const g = 1010343267;
cpp_int const h = 857348958;
cpp_int const p = 1073676287;
#endif
int constexpr b = 1 << 20;
cpp_int const inv = powm(g, p - 2, p);
{
auto s = Clock::now();
// building a hash table of all values h/g^x1
for (cpp_int x = 1; x < b; ++x) {
// go through [1, b), calculate the function h/g^x1,
// then hash it to put into table
cpp_int denom = powm(inv, x, p);
cpp_int k = (h * denom) % p;
mp.emplace(std::move(k), x);
}
std::cout << "Built map in " << (Clock::now() - s)/1.0s << "s\n";
}
{
auto s = Clock::now();
for (cpp_int v = 1; v < b; ++v) {
//std::cout << "v=" << v << " b=" << b << "\n";
// cpp_int gb = pow(g, b);
cpp_int const lkp = powm(g, v * b, p);
// looking for a match for g^b^x0 in map mp; when found we need to find x
// which is x1 and then calc 'x'
auto got = mp.find(lkp);
// Check if iterator points to end of map or if we found our value
if (got != mp.end()) {
std::cout << "Element Found - ";
//std::cout << got->first << " :: " << got->second << "\n";
}
}
std::cout << "Completed queries in " << (Clock::now() - s)/1.0s << "s\n";
}
}
它对我来说是 1 分钟 4 秒。
Built map in 24.3809s
Element Found - Completed queries in 39.2463s
...
使用 hash_str
而不是 hash_bin
需要 1 分 13 秒:
Built map in 30.3923s
Element Found - Completed queries in 42.488s