更快地实施LSH（和或）

Question

我有一个大小为（1600003200）的数据集，其中所有元素要么为零，要么为一。我想找到类似的候选人。我已经使用Minhash使用one for loop将它哈希到（160000200），它花了大约两分钟，我对此很满意。我已经实现了局部敏感散列（LSH），使用从第3章“海量数据集挖掘”中学习到的AND-OR模式，在for循环中使用for循环来查找候选对，但是花了30分钟。我想减少这个时间。有没有更快的办法？在

Here is how I have done LSH - Minhash signature length (n) = 200, sub-signature length (r) = 5, number of bands (b) = 40.

bucket-of-ids = 'empty list of dictionaries of 
                 length 40'
for each-user in 160000:
  for each-band in 40:
    r_signature = string(jth 5 elements)
    if r_signature in bucket-of-ids[band]:
       'add id of user to dictionary of band 
        using r_signature as key'
    else :
       'create r_signature as new key and then 
        add user id to it as list of values'

大小为（160000200）的Minhash签名矩阵是一个numpy数组。我的想法是，如果我能便宜地把它转换成（160000,40）数组，其中每个新数组的元素都是由minhash数组的5个元素组成的，那么也许我可以使用纽比。独一无二（）为每个列获取唯一的r\u签名，作为候选id字典的键。我对python和编码都是新手。我想不出一个方法来优化它，使它运行得更快。在

以下是代码和数据的链接： https://colab.research.google.com/drive/1HetBrWFRYqwUxn0v7wIwS7COBaNmusfD

注意：我观察到Minhash部分所花费的时间随着数据呈线性增加(编号而对于LSH部分，它是非线性增长的（前6.25%需要20.15秒，最后6.25%需要132.3秒）。我认为有必要对这一部分进行优化，如果可能的话，可以根据数据适当调整比例。我相信检查这个键是否已经存在于字典中是代码的一部分。在

更新：我通过避免检查dict中键的存在来解决这个问题，尽管我最后在for循环中使用了for循环两次。现在，16万名候选人需要310秒，所用时间随着数据呈线性增长。我已经在googlecolab笔记本中更新了相应的代码。在

Answer 1

你试过使用datasketch library吗？它实现了Minhash和LSH算法。在