python - 将 python 程序转换为 cython 以加快速度的问题

Question

我正在尝试在 Cython 中编写一个快速算法。该算法相当简单，并在此处进行了描述（https://arxiv.org/pdf/1411.4357.pdf - 第 17 页上的定理 8 之前的段落）。这个想法相对简单：假设数据是稀疏的，它可以作为具有 n 行和 d 列(i,j,A_ij)的矩阵的形式的输入。A现在为了利用稀疏性，我们需要两个函数h，将 n 行随机均匀地映射到 s 个桶中（这是算法的一个参数）和一个符号函数s，它只有 ±1 的概率。然后对于每个三元组(i,j,A_ij)，算法必须输出(h(i),j, s(h(i))*A_ij)并将它们作为数组返回，作为另一个稀疏的输入。

问题是我无法获得加速。这应该运行得非常快，并且优于实现 S 并乘以 A 的矩阵乘法，如上述参考中所示。

Python 方法（大约 11 毫秒）：

    import numpy as np
    import numpy.random as npr
    from scipy.sparse import coo_matrix
    def countSketch_faster(input_matrix, sketch_size, seed=None):
        '''
        input_matrix: sparse - coo_matrix type
        sketch_size: int
        seed=None : random seed
        '''
        observed_rows = set([])
        sign_hashes = []
        hash_table = {}
        sketched_data = []
        hashed_rows = []


        for row_id, col_id, Aij in zip(input_matrix.row, input_matrix.col, input_matrix.data):
            if row_id in observed_rows:
                sketched_data.append(hash_table[row_id][1]*Aij)
                hashed_rows.append(hash_row_val)
            else:
                hash_row_val, sign_val = np.random.choice(sketch_size), np.random.choice([-1.0,1.0])
                hash_table[row_id] = (hash_row_val, sign_val) #hash-sign pair
                sketched_data.append(sign_val*Aij)
                hashed_rows.append(hash_row_val)
                observed_rows.add(row_id)


    hashed_rows = np.asarray(hashed_rows)
    sketched_data = np.asarray(sketched_data)
    row_hashes = np.asarray(row_hashes)

    S = coo_matrix((sketched_data, (hashed_rows, input_matrix.col))).tocsr()
    return S

转换为 Cython：分析带注释的输出突出显示，python 最繁重的行是那些调用 numpy 的行。我尝试了cdef所有变量并指定dtype任何对 numpy 的调用。此外，我删除了该zip命令并尝试使循环更简单且更像 C。尽管如此，所有这些实际上都产生了不利影响，而且运行速度非常慢，我不太确定为什么。这似乎是一个非常简单的算法，因此如果有人可以帮助我将运行时间降低到非常小的程度，我将非常感激。

%%cython --annotate
cimport cython
import numpy.random as npr
import numpy as np
from scipy.sparse import coo_matrix

 def countSketch_cython(input_matrix, sketch_size, seed=None):
    '''
    input_matrix: sparse - coo_matrix type
    sketch_size: int
    seed=None : random seed
    '''

    cdef Py_ssize_t idx
    cdef int row_id
    cdef float data_id
    cdef float sketch_data_val
    cdef int hash_row_value
    cdef float sign_value



    hash_table = {}
    sketched_data = np.zeros_like(input_matrix.data,dtype=np.float64)
    hashed_rows = np.zeros_like(sketched_data,dtype=np.float64)
    observed_rows = set([])

    for idx in range(input_matrix.row.shape[0]):
        row_id = input_matrix.row[idx]
        data_id = input_matrix.data[idx]

        if row_id in observed_rows:
            hash_row_value = hash_table[row_id][0]
            sign_value = hash_table[row_id][1]
            sketched_data[row_id] = sign_value*data_id
            hashed_rows[idx] = hash_row_value
        else:
            hash_row_val = np.random.randint(low=0,high=sketch_size+1)
            sign_val = np.random.choice([-1.0,1.0])
            hash_table[row_id] = (hash_row_val, sign_val) #hash-sign pair
            sketched_data[idx] = sign_val*data_id
            hashed_rows[idx] = hash_row_value
            observed_rows.add(row_id)


    S = coo_matrix((sketched_data, (hashed_rows, input_matrix.col)))
return S`

更新：我已经设法通过删除一些较慢的行来加速代码。这些是 C 随机数生成器更快的调用，np.random在输入中给出长度，因此不需要计算，并且在返回之前不转换为稀疏矩阵（出于本实验的目的，我对如何可以快速完成转换，而不是围绕转换为下游使用的细节）。

%%cython --annotate cimport cython import numpy.random as npr import numpy as np from libc.stdlib cimport rand

#@cython.boundscheck(False)  # these don't contribute much in this 

示例 #@cython.wraparound(False)
def countSketch(input_matrix, input_matrix_length, sketch_size, seed=None): ''' input_matrix: sparse - coo_matrix 类型 input_matrix_length - 输入矩阵中的行数 sketch_size: int seed=None : random seed ' ''

    cdef Py_ssize_t idx
    cdef int row_id
    cdef float data_id
    cdef float sketch_data_val
    cdef int hash_row_value
    cdef float sign_value
    cdef int arr_lengths = input_matrix_length

    # These two lines are still annotated most boldly
    cdef double[:,:] sketched_data = 
np.zeros((arr_lengths,1),dtype=np.float64)
    cdef double[:,:] hashed_rows = np.zeros((arr_lengths,1))

    hash_table = {}

    observed_rows = set([])

    for idx in range(arr_lengths):
        row_id = input_matrix.row[idx]
        data_id = input_matrix.data[idx]

        if row_id in observed_rows:
            hash_row_value = hash_table[row_id][0]
            sign_value = hash_table[row_id][1]
            sketched_data[row_id] = sign_value*data_id
            hashed_rows[idx] = hash_row_value
        else:
            hash_row_val = rand()%(sketch_size) 
            #np.random.randint(low=0,high=sketch_size+1)
            sign_val = 2*rand()%(2) - 1
            #np.random.choice([-1.0,1.0])
            hash_table[row_id] = (hash_row_val, sign_val) #hash-sign pair
            sketched_data[idx] = sign_val*data_id
            hashed_rows[idx] = hash_row_value
            observed_rows.add(row_id)


    #S = coo_matrix((sketched_data, (hashed_rows, input_matrix.col)), dtype=np.float64) 
return hashed_rows, sketched_data

在随机稀疏矩阵上A = scipy.sparse.random(1000, 50, density=0.1)，现在508 µs ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)使用%timeit countSketch(A, A.shape[0],100). 我应该想象还有一些收获，因为我不知道我是否以最好的方式设置了数组。

标签： pythonarraysalgorithmcythonsparse-matrix