我们能以多快的速度近似设置 Jaccard 分数？

问题描述 投票：0回答：1

我正在尝试在笔记本电脑上计算大约 1 万亿个不同的成对杰卡德分数。我也不是很有耐心。

每组往往包含大约 200-800 个唯一的伪随机 32 位哈希值。我已经最小化了每组的大小。

是否有一种方法可以让我以牺牲精度来换取更快的性能？我大概可以容忍 +/- 0.15 的错误率。

需要明确的是，我并不希望通过将相同的方程转换为类似 numba 的方程来获得边际性能提升。我正在寻找一种替代方法（也许是矩阵数学？），它可以将性能提高至少一个数量级，最好是更多。

这是一个计算无错误的 Jaccard 分数的示例：

def jaccard(hash_set_1, hash_set_2) -> float:
    if 0 == min(len(hash_set_1), len(hash_set_2)):
        return 0.0
    intersect = len(hash_set_1 & hash_set_2)
    union = len(hash_set_1) + len(hash_set_2) - intersect
    return intersect / union
performance approximation set-intersection set-union
1个回答
0
投票

这个答案提供了一个可能的解决方案，可以显着加速整个算法（而不仅仅是提供的函数）。

主要思想是用简化的 

布隆过滤器 替换 CPython 的 set 数据结构（类似于包含对 CPython 对象的引用的哈希表数据结构，请参阅此处）。布隆过滤器是一种非常紧凑的概率数据结构。它们可用于检查某个数字是否不在 100% 准确度的集合中，或者是否在可能存在错误的集合中。出现错误的概率取决于滤波器的大小。每个整数都可以编码为大位集中的单个位。整数的位置基于整数的散列。如果整数已经是均匀分布的数字（例如已经是散列），则不需要对其进行散列。使用 
hash(number) % filter_size
 可以找到要检查/设置的位的位置。如果 
filter_size
 是 2 的幂，则可以用非常快速的 AND 指令来替换模数。


两个布隆过滤器的交集在于计算两个内存块的 AND，假设两个过滤器具有完全相同的大小并使用相同的哈希函数。位集的数量（由于专用 CPU 指令，可以非常有效地计算）是两个集合交集中项目数量的近似值。然而，使用这个解决方案，过滤器需要相当大，以避免碰撞问题，从而导致最终结果非常不准确（参见生日问题）。大（稀疏）过滤器的旅行费用往往相当昂贵。


另一种解决方案是转换大型布隆过滤器中的最大集合，然后迭代最小集合，以检查是否在布隆过滤器中找到每个项目。该解决方案避免了许多冲突并减轻了一些生日问题。只要布隆过滤器适合 L1 CPU 缓存，它的成本也更便宜。将集合转换为布隆过滤器可能非常昂贵，但布隆过滤器可以重复用于许多对比较，因此此操作最终花费的时间可以忽略不计。


请注意，该近似是（无界）过度近似。如果数字小于表大小并且哈希函数是完美哈希函数（例如身份），则保证结果是准确的。然而，过滤器的大小对于 32 位随机整数来说太大而无法高效（即每个过滤器 512 MiB RAM）。您可以使用多个哈希函数来提高方法的精度（但代价是执行速度变慢——天下没有免费的午餐）。此策略可以帮助您确定输出的准确性（基于从具有不同哈希函数的多个过滤器检索到的结果数字的方差）。


这是一个（低效的）示例，说明了事情是如何工作的：


# The two input sets
a = np.unique(np.random.randint(0, 1_000_000, 800))
b = np.unique(np.append(np.random.randint(0, 1_000_000, 300), np.random.choice(a, 10)))

print('Exact count: ', len(set(a) & set(b)))

# Build a simple bloom filters based on `a`
# Numpy takes 1 byte per item, but it should take 32 KiB in 
# practice with 1 bit per item. 
# This fits in the L1 cache of nearly all mainstream CPU.
# The L1 cache is very fast.
table = np.zeros(256*1024, dtype=np.bool_)
table[a % table.size] = True

# Count matching items (over-approximation)
count = 0
for item in b:
    count += table[item % table.size]
print('Estimation: ', count)



在实践中，出于性能考虑，计算应使用 Numba 或 Cython（或使用本机语言）进行计算。该集合应存储为 Numpy 数组，因为在 Numba/Cython 中迭代 CPython 集合的成本更高。布隆过滤器应尽可能重复使用。布隆过滤器的大小必须是“编译时常数”（对于避免非常慢的模数至关重要），并且哈希函数应该很快（例如恒等、异或移位）。布隆过滤器的数组应尽可能回收以避免分配。 循环展开和耕耘也应该可以提高性能。
可以使用
多线程
（禁用 GIL 的本机线程）并行计算这些对。事实上，布隆过滤器方法也是GPU友好的，并且 GPU 对于此类计算的速度可以显着加快。布隆过滤器必须存储在 GPU 共享内存 中才能保证操作速度。这种内存的大小非常有限（例如 Nvidia 设备上每个 SM 0-200 KiB），但它应该足够大以满足您的实际需求。
相关文章：
最有效的方法，而不是使用
np.setdiff1d和
np.in1d
，删除具有唯一值的一维数组的公共值

    


      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.