LSH hashcode生成器函数

Question

要用Python构建基于LSH的系统，我需要非常快地计算哈希代码。

这里我不需要解释LSH算法本身，但我需要帮助提高generate Code操作的性能：

给定大量的特性n(例如:5,000甚至50000)：

1. 用稀疏向量(nx1)将稠密矩阵(13 Nx1)相乘
2. 在得到的向量(13x1)中，如果为正，则改为1，否则为0。
3. 从结果中生成一个二进制数

我尝试了各种方法，并在这里放置了两种实现generateCode1和generateCode2，但这两种方法仍然太重。

generateCode1 takes 56 seconds for 100 call (avg: 0.56 s)
generateCode2 takes 20 seconds for 100 call (avg: 0.20 s)

我确信可以更快地做到这一点，但不确定如何做到。为了使您能够玩它，我正在编写一个完整的工作示例程序：

import time
import numpy as np
from scipy import sparse
from scipy import stats

def randomMatrix(rows, cols, density):
    rvs = stats.norm(loc=0).rvs  # scale=2,
    M = sparse.random(rows, cols, format='lil', density=density, data_rvs=rvs)
    return M

def generateCode1(matrix, vector):
    nonzeros = np.nonzero(vector)
    temp_hashcode = []

    for i in range(matrix.shape[0]):
        d = 0
        for j in nonzeros[1]:
            d += matrix[i, j] * vector[0, j]

        temp_hashcode.append('1' if d > 0 else '0')

    return ''.join(temp_hashcode)

def generateCode2(matrix, vector):
    m = matrix * vector.T
    m [m > 0] = 1
    m [m < 0] = 0
    txt = ''.join(m.A.ravel().astype('U1'))
    return txt

features = 50000
test_count = 100

matrix = randomMatrix(13, features, 1.0)
vector = randomMatrix(1, features, 0.01)
vector = abs(vector)


methods = [ generateCode1, generateCode2 ]

for func in methods:
    print ('run {0} times of method {1}:'.format( test_count, func ) )
    time1 = time.time()
    for i in range(test_count):
        code1 = func(matrix, vector)
    time1 = time.time() - time1

    print ('\tcode: {0} - run time: '.format(code1), end="" )
    print ('{0}(s) == {1}(m) [ avergae {2}(s) ]'.format(time1, time1/60, time1/test_count) )

注意:请不要使用并行和多处理，这将不适合我的整体应用程序(不幸)。

Answer 1

关于文章中的代码，有两件事我不明白。

1. 您真的致力于使用里尔 (列表)格式吗？文档非常清楚，LIL不适合计算矩阵产品，例如这里：要执行乘法或逆等操作，首先将矩阵转换为CSC或CSR格式。和这里：LIL格式...慢矩阵向量产品的缺点(考虑CSR或CSC)。我发现在matrix和vector中使用CSR代替LIL可以立即实现20×加速比。即使您有充分的理由在代码的某些部分中使用LIL格式，您仍然应该在计算产品之前转换为CSR，如文档中所建议的那样。
2. 既然matrix是密集的，为什么代码使用稀疏矩阵来表示它呢？这必然会导致使用普通np.matrix可以避免的一些开销。我发现，将matrix从CSR转换为np.matrix可以进一步提高1.5×加速比。

Answer 2

我曾尝试缩短所需的手术，例如：

def generateCode3(matrix, vector):
    m = matrix * vector.T
    n = (m.data > 0).astype(int)
    return ''.join(map(str,n))

或可读性较低，但更紧凑，没有任何进一步的变量m或n：

def generateCode4(matrix, vector):
    return ''.join(map(str,((matrix * vector.T).data > 0).astype(int)))

最后，使用这个问题的第二个答案：

def generateCode5(matrix, vector):
    return ''.join(np.char.mod('%d', (((matrix * vector.T).data > 0).astype(int))))

然而，由此产生的时间差微乎其微，因此没有真正的改善。使用您的时间比较，结果是：

run 100 times of method <function generateCode2 at 0x00000000159816A8>:
    code: 1000000011110 - run time: 7.869999885559082(s) == 0.13116666475931804(m) [ avergae 0.07869999885559081(s) ]
run 100 times of method <function generateCode3 at 0x00000000159810D0>:
    code: 1000000011110 - run time: 7.759999990463257(s) == 0.1293333331743876(m) [ avergae 0.07759999990463257(s) ]
run 100 times of method <function generateCode4 at 0x0000000015981158>:
    code: 1000000011110 - run time: 7.757499933242798(s) == 0.12929166555404664(m) [ avergae 0.07757499933242798(s) ]
run 100 times of method <function generateCode5 at 0x00000000159811E0>:
    code: 1000000011110 - run time: 7.75(s) == 0.12916666666666668(m) [ avergae 0.0775(s) ]