使用numpy实现topk函数操作(并排序)
np.argpartition 难以解决topK
topK是常用的一个功能，在python中，numpy等计算库使用了丰富的底层优化，对于矩阵计算的效率远高于python的for-loop实现。因此，我们希望尽量用一些numpy函数的组合实现topK。
pytorch 库提供了topk函数，可以将高维数组沿某一维度（该维度共N项），选出最大（最小）的K项并排序。返回排序结果和index信息。奇怪的是，更轻量级的numpy库并没有直接提供 topK 函数。numpy只提供了argpartition 和 partition，可以将最大（最小）的K项排到前K位。以argpartition为例，最小的3项排到了前3位：
>>> x = np.array([3, 5, 6, 4, 2, 7, 1]) >>> x[np.argpartition(x, 3)] array([2, 1, 3, 4, 5, 7, 6])
注意，argpartition实现的是 partial sorting，如上例，前3项和其余项被分开，但是两部分各自都是不排序的！而我们可能更想要topK的几项排好序（其余项则不作要求）。因此，下面提供一种基于argpartition的topK方法。
一个naive方法
最简单的方法自然是全排序，然后取前K项。缺点在于，要把topK之外的数据也进行排序，当K << N时较为浪费时间，复杂度为O ( n log n ) O(n \log n)O(nlogn):
def naive_arg_topK(matrix, K, axis=0): """ perform topK based on np.argsort :param matrix: to be sorted :param K: select and sort the top K items :param axis: dimension to be sorted. :return: """ full_sort = np.argsort(matrix, axis=axis) return full_sort.take(np.arange(K), axis=axis) # Example >>> dists = np.random.permutation(np.arange(30)).reshape(6, 5) array([[17, 28, 1, 24, 23, 8], [ 9, 21, 3, 22, 4, 5], [19, 12, 26, 11, 13, 27], [10, 15, 18, 14, 7, 16], [ 0, 25, 29, 2, 6, 20]]) >>> naive_arg_topK(dists, 2, axis=0) array([[4, 2, 0, 4, 1, 1], [1, 3, 1, 2, 4, 0]]) >>> naive_arg_topK(dists, 2, axis=1) array([[2, 5], [2, 4], [3, 1], [4, 0], [0, 3]])
基于partition的方法
对于 np.argpartition 函数，复杂度可能下降到 O ( n log K ) O(n \log K)O(nlogK)，很多情况下，K << N，此时naive方法有优化的空间。
以下方法首先选出 topK 项，然后仅对前topK项进行排序（matrix仅限2d-array）。
def partition_arg_topK(matrix, K, axis=0): """ perform topK based on np.argpartition :param matrix: to be sorted :param K: select and sort the top K items :param axis: 0 or 1. dimension to be sorted. :return: """ a_part = np.argpartition(matrix, K, axis=axis) if axis == 0: row_index = np.arange(matrix.shape[1 - axis]) a_sec_argsort_K = np.argsort(matrix[a_part[0:K, :], row_index], axis=axis) return a_part[0:K, :][a_sec_argsort_K, row_index] else: column_index = np.arange(matrix.shape[1 - axis])[:, None] a_sec_argsort_K = np.argsort(matrix[column_index, a_part[:, 0:K]], axis=axis) return a_part[:, 0:K][column_index, a_sec_argsort_K] # Example >>> dists = np.random.permutation(np.arange(30)).reshape(6, 5) array([[17, 28, 1, 24, 23, 8], [ 9, 21, 3, 22, 4, 5], [19, 12, 26, 11, 13, 27], [10, 15, 18, 14, 7, 16], [ 0, 25, 29, 2, 6, 20]]) >>> partition_arg_topK(dists, 2, axis=0) array([[4, 2, 0, 4, 1, 1], [1, 3, 1, 2, 4, 0]]) >>> partition_arg_topK(dists, 2, axis=1) array([[2, 5], [2, 4], [3, 1], [4, 0], [0, 3]])
大数据量测试
对shape(5000, 100000)的矩阵进行topK排序，测试时间为：
| K | partition(s) | naive(s) |
|---|---|---|
| 10 | 8.884 | 22.604 |
| 100 | 9.012 | 22.458 |
| 1000 | 8.904 | 22.506 |
| 5000 | 11.305 | 22.844 |
补充：python堆排序实现TOPK问题
# 构建小顶堆跳转def sift(li, low, higt): tmp = li[low] i = low j = 2 * i + 1 while j <= higt: # 情况2：i已经是最后一层 if j + 1 <= higt and li[j + 1] < li[j]: # 右孩子存在并且小于左孩子 j += 1 if tmp > li[j]: li[i] = li[j] i = j j = 2 * i + 1 else: break # 情况1：j位置比tmp小 li[i] = tmp def top_k(li, k): heap = li[0:k] # 建堆 for i in range(k // 2 - 1, -1, -1): sift(heap, i, k - 1) for i in range(k, len(li)): if li[i] > heap[0]: heap[0] = li[i] sift(heap, 0, k - 1) # 挨个输出 for i in range(k - 1, -1, -1): heap[0], heap[i] = heap[i], heap[0] sift(heap, 0, i - 1) return heap li = [0, 8, 6, 2, 4, 9, 1, 4, 6] print(top_k(li, 3))
以上为个人经验，希望能给大家一个参考，也希望大家多多支持本站。
版权声明：本站文章来源标注为YINGSOO的内容版权均为本站所有，欢迎引用、转载，请保持原文完整并注明来源及原文链接。禁止复制或仿造本网站，禁止在非www.yingsoo.com所属的服务器上建立镜像，否则将依法追究法律责任。本站部分内容来源于网友推荐、互联网收集整理而来，仅供学习参考，不代表本站立场，如有内容涉嫌侵权，请联系alex-e#qq.com处理。
关注官方微信