c++ 大向量双精度数的哈希值快速计算

3hvapo4f 于 2023-05-08 发布在其他

关注(0)|答案(1)|浏览(178)

我需要计算一个大向量的哈希值。目前，我使用for-loop和boost：：hash_合并来实现，如下所示，但它太慢了-对于500000大小的向量，它需要接近10 ms的时间，但理想情况下，我希望将其降低到1 ms或更少。有没有一种方法可以更快地计算哈希值（也许是一次性的？））来获取像向量这样的连续内存块中的内容，而不必使用for循环来解析整个向量？

#include <random>
#include <algorithm>
#include <functional> // bind
#include <iterator>
#include <iostream>
#include <vector>
#include <chrono>
#include <boost/functional/hash.hpp>

using namespace std;

int main () 
{

    vector<double> myContainer(500000, 0.0);
    
    uniform_real_distribution<double> unif(0.0,1.0);
    mt19937 re(std::random_device{}());
    auto generator = std::bind(unif, std::ref(re));
    generate(begin(myContainer), end(myContainer), generator);
    
    cout << "myContainer[0] = " << myContainer[0] << ", myContainer[L-1] = " << myContainer[myContainer.size()-1] << std::endl;
    
    size_t      hashValBoost(0);     // type supported by boost::hash_combine
    uint64_t startTime_us = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
    for(size_t i=0; i<myContainer.size(); ++i)
    {
        boost::hash_combine(hashValBoost, myContainer[i]);
    }
    uint64_t endTime_us = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();

    cout << "ContainerSize = " << myContainer.size() <<"; Container hash = " << hashValBoost << ", TimeToComputeHash(ms) = " << (endTime_us - startTime_us)/1000.0 << "ms" << std::endl;
    return 0;
}

编辑：我不得不在没有打开优化和C++11或更老的编译器的情况下构建。
在此处运行代码：https://wandbox.org/permlink/gxVxZ8QE53DhtZde

c++

来源：https://stackoverflow.com/questions/76158702/faster-computation-of-hash-value-for-a-large-vector-of-doubles

1条答案

按热度按时间

pftdvrlh1#

如果你的vector不包含NaN s或负零，你可以利用更优化的字节数组哈希算法：

std::size_t hash_bytes(std::span<const std::byte> sp) {
    std::string_view sv(reinterpret_cast<const char*>(sp.data()), sp.size())
    return std::hash<std::string_view>{}(sv);
    
    // Or some other byte based hashing algorithm, like
    
    // boost::hash_range is optimized for std::byte and unsigned char
    return boost::hash_range(sp.begin(), sp.end());
}

// Usage: hashVal = hash_bytes(std::as_bytes(std::span(myContainer)))

Boost也有boost::hash_value(const std::vector<T>&)或boost::hash_range(It, It)，它们在内部执行hash_combine循环。它大约慢4倍，但如果你有负0/NaN s，它仍然可以工作。

赞(0）回复(0）举报 2023-05-08

我来回答

c++ 大向量双精度数的哈希值快速计算

1条答案

相关问题

热门标签

最新问答