3

https://github.com/joeyrobert/bloomfilter使用 Random 类作为哈希函数，这是一个性能杀手。
我想要做的是用 byte[]s 而不是通用参数（T）输入类并摆脱 

    private int Hash(T item) {
        return item.GetHashCode();
    }

我知道有巨大的性能优势，但我不知道如何在_random.Next(_bitSize)这里替换：

#region Public Methods
/// <summary>
/// Adds an item to the bloom filter.
/// </summary>
/// <param name="item">Item to be added</param>
public void Add(T item)
{
    _random = new Random(Hash(item));

    for (int i = 0; i < _numberOfHashes; i++)
        _bitArray[_random.Next(_bitSize)] = true;
}

使用一些非延迟的代码行，每一位都不需要数千个 CPU 周期。

我知道代码还有很多其他问题可以使它更快/更安全。我已经（大部分）修复了它们，只是在推动我的更改之前卡在了最后一个问题上。
非常感谢任何帮助。

4

2 回答 2

2

我不明白您为什么要在这里使用随机数生成器……但是，我可以帮助您加快速度。

布隆过滤器基本上是一个位向量，您可以在其中设置位。如果你想知道一个项目是否存在，如果项目可能存在，布隆过滤器会给你一个 true ，如果这个项目肯定不存在，它会给你一个false 。

（我在一个简单的文本编辑器中执行此操作，因此代码中可能存在一些错误）

我将假设您的哈希空间可以使用 32 位整数计算；如果您有一个非常大的布隆表，您可能希望使用 64 位整数。

因此，布隆过滤器最简单（可能也是最快）的实现是：

byte[] bloomFilter = new byte[MyBloomFilterSize];

foreach (var item in myItems) 
{
    int hash = Hash(item) & 0x7FFFFFFF;
    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    bloomFilter[hash % MyBloomFilterSize] |= bit;
}

您可以尝试将 更改byte[]为 auint[]或 a ulong[]; 我不确定这是否会有所不同。

如果你想检查一个项目是否存在，你计算相同的索引和位，并得到结果。

public bool PossiblyExists(MyItem item)
{
    int hash = Hash(item) & 0x7FFFFFFF;

    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    return (bloomFilter[hash % MyBloomFilterSize] & bit) != 0;
}

唯一剩下的就是计算哈希的速度。如果您使用的是整数，我会简单地将它与一个大素数相乘；如果您使用的是 SHA256 固定长度字节 []（您似乎正在这样做），则需要将其设为整数（或长整数）。

我在这里使用 Buffer.BlockCopy 的一个小技巧来转换类型。为了安全起见，我更喜欢使用数据中的几个字节，但由于 SHA256 应该已经是随机的，所以一个简单BitConverter.ToInt32(data, [0..28])的也应该可以解决问题。

public int CalculateHash(byte[] data) 
{
    // Data = >128 bits = >16 bytes -- which is the same as >4 integers

    int[] tmp = new int[4];
    Buffer.BlockCopy(data, 0, tmp, 0, data.Length);
    return tmp[0] ^ tmp[1] ^ tmp[2] ^ tmp[3];
}

那应该这样做。

于 2014-04-30T07:43:12.020 回答
1

例如，一个有效的实现如下。如果您有一个返回 64 位的哈希函数，那么最好使用它而不是 murmur3_64。警告：我没有测试它。

void Add(string item) {
    ulong hash = murmur3_64((ulong) item.GetHashCode());
    uint a = (uint) (hash >> 32);
    uint b = (uint) hash;
    for (int i = 0; i < k; i++) {
        _bitArray[reduce(a, _bitSize)] = true;
        // "Less Hashing, Same Performance: Building a Better Bloom Filter"
        a += b;
    }
}

ulong murmur3_64(ulong x) {
    x = (x ^ (x >> 33)) * 0xff51afd7ed558ccdL;
    x = (x ^ (x >> 23)) * 0xc4ceb9fe1a85ec53L;
    x = x ^ (x >> 33);
    return x;
}

uint reduce(uint hash, uint n) {
    // http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
    return (hash * n) >> 32;
}
于 2018-11-14T07:23:33.373 回答