-
2021-07-28 14:25:17
PyTorch中的topk方法以及分类Top-K准确率的实现
Top-K 准确率
在分类任务中的类别数很多时(如ImageNet中1000类),通常任务是比较困难的,有时模型虽然不能准确地将ground truth作为最高概率预测出来,但通过学习,至少groud truth的准确率能够在所有类中处于很靠前的位置,这在现实生活中也是有一定应用意义的,因此除了常规的Top-1 Acc,放宽要求的Tok-K Acc也是某些分类任务的重要指标之一。
Tok-K准确率:即指在模型的预测结果中,前K个最高概率的类中有groud truth,就认为在Tok-K准确率的要求下,模型分类成功了。
PyTorch中的topk方法
PyTorch中并没有直接提供计算模型Top-K分类准确率的接口,但是提供了一个topk方法,用来获得某tensor某维度中最高或最低的K个值。
函数接口
torch.topk(input, k, dim=None, largest=True, sorted=True, *, out=None) -> (Tensor, LongTensor)
同样有tensor.topk的使用方式,参数及返回值类似。
参数说明
input:输入张量
dim:指定在哪个维度取topk
k:前k大或前k小值
largest:取最大(True)或最小(False)
sorted:返回值是否有序
返回值说明
返回两个张量:values和indices,分别对应前k大/小值的数值和索引,注意返回值的各维度的意义,不要搞反了,后面实验会说。
实验
我们在这里模拟常见的分类任务的情况,设置batch size为4,类别数为10,这样模型输出应为形状为(10,4)的张量。
output = torch.rand(4, 10) print(output) print('*'*100) values, indices = torch.topk(output, k=2, dim=1, largest=True, sorted=True) print("values: ", values) print("indices: ", indices) print('*'*100) print(output.topk(k=2, dim=1, largest=True, sorted=False)) # tensor.topk的用法
输出:
tensor([[0.7082, 0.5335, 0.9494, 0.7792, 0.3288, 0.6303, 0.0335, 0.6918, 0.0778, 0.6404], [0.3881, 0.8676, 0.7700, 0.6266, 0.8843, 0.8902, 0.4336, 0.5385, 0.8372, 0.1204], [0.9717, 0.2727, 0.9086, 0.7797, 0.1216, 0.4793, 0.1149, 0.1544, 0.7292, 0.0459], [0.0424, 0.0809, 0.1597, 0.4177, 0.4798, 0.7107, 0.9683, 0.7502, 0.1536, 0.3994]]) **************************************************************************************************** values: tensor([[0.9494, 0.7792], [0.8902, 0.8843], [0.9717, 0.9086], [0.9683, 0.7502]]) indices: tensor([[2, 3], [5, 4], [0, 2], [6, 7]]) **************************************************************************************************** torch.return_types.topk( values=tensor([[0.9494, 0.7792], [0.8902, 0.8843], [0.9717, 0.9086], [0.9683, 0.7502]]), indices=tensor([[2, 3], [5, 4], [0, 2], [6, 7]]))
注意输出的行是用户指定的dim的k个最大/小值(实验中sorted=True,所以是有序返回的),列是其他未指定的维度,不要搞反了。
分类Top-K准确率的实现
实现
借助刚刚介绍的PyTorch中的topk方法实现的分类任务的Top-K准确率计算方法。
def accuracy(output, target, topk=(1, )): # output.shape (bs, num_classes), target.shape (bs, ) """Computes the accuracy over the k top predictions for the specified values of k""" with torch.no_grad(): maxk = max(topk) batch_size = target.size(0) _, pred = output.topk(maxk, 1, True, True) pred = pred.t() correct = pred.eq(target.view(1, -1).expand_as(pred)) res = [] for k in topk: correct_k = correct[:k].reshape(-1).float().sum(0, keepdim=True) res.append(correct_k.mul_(100.0 / batch_size)) return res
实验
我们同样拿上面的分类任务做实验,batch size为4,类别数为10,给定label:2,1,8,5,为了方便观察,计算Top-1,2准确率(ImageNet-1K中通常计算Top-1,5准确率)。
测试代码:
output = torch.rand(4, 10) label = torch.Tensor([2, 1, 8, 5]).unsqueeze(dim=1) print(output) print('*'*100) values, indices = torch.topk(output, k=2, dim=1, largest=True, sorted=True) print("values: ", values) print("indices: ", indices) print('*'*100) print(accuracy(output, label, topk=(1, 2)))
输出:
tensor([[0.8721, 0.7391, 0.1365, 0.3017, 0.2840, 0.2400, 0.6473, 0.3965, 0.5449, 0.7518], [0.7120, 0.8533, 0.2809, 0.9515, 0.2971, 0.8182, 0.5498, 0.0797, 0.8027, 0.6916], [0.4540, 0.8468, 0.9022, 0.5144, 0.2007, 0.7292, 0.5559, 0.0290, 0.6664, 0.2076], [0.1793, 0.0205, 0.7322, 0.4918, 0.6194, 0.9179, 0.1639, 0.6346, 0.8829, 0.3573]]) **************************************************************************************************** values: tensor([[0.8721, 0.7518], [0.9515, 0.8533], [0.9022, 0.8468], [0.9179, 0.8829]]) indices: tensor([[0, 9], [3, 1], [2, 1], [5, 8]]) [tensor([25.]), tensor([50.])]
可以看到在top1准确率时只有最后一个样本与标签对应,故Top-1准确率为1 / 4 =25%,而在top2准确率时样本2,4预测成功了,Top-2准确率为50%,符合我们的预期。
有疑惑或异议欢迎留言讨论。
Ref:https://pytorch.org/docs/master/generated/torch.topk.html#torch-topk
更多相关内容 -
CS130A-research-topK:链表实现的top-K空间节省算法
2021-03-09 12:38:03Tom Zu-search-topK-节省空间 链表实现的Top-K空间节省算法 2021/3 / 4-2021 / 3/5期间完成的工作 论文“数据流中频繁和Top-k元素的有效计算”中提出的算法 链接: : 运行程序 将所有数据放入名称为fname的.txt... -
C/C++ 通过最大堆求topk
2021-04-09 10:53:13通过最大堆求topk -
TopK优化思路
2018-09-20 20:00:18TopK,不难;其思路优化过程,不简单: • 全局排序,O(n*lg(n)) • 局部排序,只排序TopK个数,O(n*k) • 堆,TopK个数也不排序了,O(n*lg(k)) • 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n)) • 减... -
topK 问题的5种解决方案
2018-09-26 15:46:14topk 问题,就是从一个数组或者列表中获取最大的K个数,求3个积分,因为我需要3个积分下载东西,但是,我的里面的topK 解决方案肯定是比较全的,如果有什么看不懂的,请联系我,绝对负责给你讲清楚 -
topk问题python k堆实现。。。。
2019-05-18 21:41:34topk问题的Python实现,k-堆实现 -
在属性级不确定数据上优化U-Topk查询
2021-04-30 06:25:32U-Topk是基于不确定性数据可能世界模型而提出的一种查询语义.随着不确定性数据集的增大,可能世界的实例数量指数增长,这为U-Topk查询处理提出了重大挑战.针对属性级不确定性的U-Topk查询处理算法展开研究,提出了U-Top... -
topK
2019-04-19 17:24:42topK 1. 问题描述 TopK Elements 问题用于找出一组数中最大的 K 个的数。 此外还有一种叫 Kth Element 问题,用于找出一组数中第 K 大的数。 如果要找的 TopK Elements 是最小的 K 个数,那么可以将问题转换成求解...topK
1. 问题描述
TopK Elements 问题用于找出一组数中最大的 K 个的数。
此外还有一种叫 Kth Element 问题,用于找出一组数中第 K 大的数。
如果要找的 TopK Elements 是最小的 K 个数,那么可以将问题转换成求解 TopK Elements,因为找到 Kth Element 之后,再遍历一遍,小于等于 Kth Element 的数都是 TopK Elements。2. 一般解法
以 Leetcode : 215. Kth Largest Element in an Array 为例,这是一道的 Kth Element 问题,不过这道题要找的是从后往前第 K 个元素,而不是从前往后。为了能和传统的 Kth Element 问题一样求解,可以先执行
k = nums.length - k;
Input: [3,2,1,5,6,4] and k = 2 Output: 5
2.1 快速选择
快速排序的 partition() 方法,对于数组 nums 的 [l, h] 区间,会返回一个整数 k 使得 nums[l…k-1] 小于等于 nums[k],且 nums[k+1…h] 大于等于 nums[k],此时 nums[k] 就是数组的第 k 大元素。可以利用这个特性找出数组的 Kth Element,这种找 Kth Element 的算法称为快速选择算法。
- 时间复杂度 O(N)、空间复杂度 O(1)
- 只有当允许修改数组元素时才可以使用
public int findKthElement(int[] nums, int k) { k = nums.length - k; int l = 0, h = nums.length - 1; while (l < h) { int j = partition(nums, l, h); if (j == k) { break; } else if (j < k) { l = j + 1; } else { h = j - 1; } } return nums[k]; } private int partition(int[] a, int l, int h) { int i = l, j = h + 1; while (true) { while (a[++i] < a[l] && i < h) ; while (a[--j] > a[l] && j > l) ; if (i >= j) { break; } swap(a, i, j); } swap(a, l, j); return j; } private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
2.2 堆
维护一个大小为 K 的最小堆,堆顶元素就是 Kth Element。
使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素。
维护一个大小为 K 的最小堆过程如下:在添加一个元素之后,如果大顶堆的大小大于 K,那么需要将大顶堆的堆顶元素去除。
- 时间复杂度 O(NlogK) 、空间复杂度 O(K)
- 特别适合处理海量数据
在下面的实现中,令
k = nums.length - k + 1;
,这是因为此时 k 不是从零开始,和上面的快速选择解法有所不同。public int findKthLargest(int[] nums, int k) { k = nums.length - k + 1; PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); // 大顶堆 for (int val : nums) { pq.add(val); if (pq.size() > k) // 维护堆的大小为 K pq.poll(); } return pq.peek(); }
3. 海量数据
在这种场景下,单机通常不能存放下所有数据。
- 拆分,可以按照哈希取模方式拆分到多台机器上,并在每个机器上维护最大堆;
- 整合,将每台机器得到的最大堆合并成最终的最大堆。
4. 频率统计
Heavy Hitters 问题要求找出一个数据流的最频繁出现的 K 个数,比如热门搜索词汇等。
4.1 HashMap
使用 HashMap 进行频率统计,然后使用快速选择或者堆的方式找出频率 TopK。在海量数据场景下,也是使用先拆分再整合的方式来解决空间问题。
4.2 Count-Min Sketch
维护 d*w 大小的二维统计数组,其中 d 是哈希函数的个数,w 根据情况而定。
- 在一个数到来时,计算 d 个哈希值,然后分别将哈希值对 w 取模,把对应统计数组上的值加 1;
- 要得到一个数的频率,也是要计算 d 个哈希值并取模,得到 d 个频率,取其中最小值。
该算法的思想和布隆过滤器类似,具有一定的误差,特别是当 w 很小时。但是它能够在单机环境下解决海量数据的频率统计问题。
public class CountMinSketch { private int d; private int w; private long estimators[][]; public CountMinSketch(int d, int w) { this.d = d; this.w = w; } public void add(int value) { for (int i = 0; i < d; i++) estimators[i][hash(value, i)]++; } public long estimateFrequency(int value) { long minimum = Integer.MAX_VALUE; for (int i = 0; i < d; i++) { minimum = Math.min(minimum, estimators[i][hash(value, i)]); } return minimum; } private int hash(int value, int i) { return 0; // use ith hash function } }
4.3 Trie
Trie 树可以用于解决词频统计问题,只要在词汇对应节点保存出现的频率。它很好地适应海量数据场景,因为 Trie 树通常不高,需要的空间不会很大。
-
Topk问题的三种求解方法
2021-09-02 16:40:52Topk问题的三种求解方法什么是Topk问题方法一:堆排序法方法二:把N个数建堆,取出前k个方法三:建一个k个数的堆 什么是Topk问题 其实顾名思义,这个问题也就是在N个数中找出前k个最值。在我们的日常生活中,很多...Topk问题的三种求解方法
什么是Topk问题
其实顾名思义,这个问题也就是在N个数中找出前k个最值。在我们的日常生活中,很多地方都有Topk问题的影子,例如我们在点外卖时,总会说这家店是某某市的多少名,其实这些都是用Topk问题的解决方法得出来的。
方法一:堆排序法
这也是最容易想到的一种方法:我们可以将N个数排成有序的,然后输出前k个最值,而在我们已学过的排序算法中,堆排序的时间复杂度又是最快的(O(n*logn)),因此我们选择了堆排序。
//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //堆的向下调整(小堆) void AdjustDown(int* a, int n, int parent) { //child记录左右孩子中值较小的孩子的下标 int child = 2 * parent + 1;//先默认其左孩子的值较小 while (child < n) { if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小 { child++;//较小的孩子改为右孩子 } if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小 { //将父结点与较小的子结点交换 Swap(&a[child], &a[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1; } else//已成堆 { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { *returnSize = k; int i = 0; //建小堆 for (i = (arrSize - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } //排降序 int end = arrSize - 1; while (end > 0) { Swap(&arr[0], &arr[end]); AdjustDown(arr, end, 0); end--; } //将最大的k个数存入数组 int* retArr = (int*)malloc(sizeof(int)*k); for (i = 0; i < k; i++) { retArr[i] = arr[i]; } return retArr;//返回最大的k个数 }
时间复杂度:O(N+NlogN) 空间复杂度:O(N),能否将其再优化了?肯定是可以的,下面看方法二。
方法二:把N个数建堆,取出前k个
这种方法其实也不难想到,我们利用了堆的性质:堆的0号位一定是最值,小堆则为最小值,大堆则为最大值。
注意点:
1.取出数据后要让其与最后的元素替换,因为你已经取出这个元素了,所以不需要它了,这时让它去堆尾,不让它算入堆的个数中就行了。为什么要这样做了,因为这样既保证了堆的结构,也相当于把这个取出来的数删除了
。
2. 如果在取到堆顶数据后直接删除数据,那么就要重新建堆了。正确的做法应该是上面所说的方法,因为那样只要进行一次向下调整,就可以保证堆的结构了。要知道建堆的复杂度为O(N),而一次向下调整的复杂度仅为O(logn)
,这样大大提升了效率。//交换函数 void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //堆的向下调整(大堆) void AdjustDown(int* a, int n, int parent) { //child记录左右孩子中值较大的孩子的下标 int child = 2 * parent + 1;//先默认其左孩子的值较大 while (child < n) { if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大 { child++;//较大的孩子改为右孩子 } if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大 { //将父结点与较大的子结点交换 Swap(&a[child], &a[parent]); //继续向下进行调整 parent = child; child = 2 * parent + 1; } else//已成堆 { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize) { *returnSize = k; int i = 0; //建大堆 for (i = (arrSize - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } //将最大的k个数存入数组 int* retArr = (int*)malloc(sizeof(int)*k); int end = arrSize - 1; for (i = 0; i < k; i++) { retArr[i] = arr[0];//取堆顶数据 Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据 //进行一次向下调整,不把最后一个数据看作待调整的数据,所以待调整数据为end=arrSize-1 AdjustDown(arr, end, 0); end--;//最后一个数据的下标改变 } return retArr;//返回最大的k个数 }
时间复杂度:O(n+k*logn),空间复杂度:O(n),那么问题来了,万一n是一个特别大的数字了,那效率依旧不是很高,有没有更快的方法了?下面我们来看看方法三。
方法三:建一个k个数的堆
我们以找出最大的k个数为例,该方法为:先建一个k个数的小堆,然后将数组中n-k个元素依次与堆顶的元素比较,若比堆顶元素大,则将堆顶元素删除,然后将这个数插入到堆中,这儿要注意:插入这个数到堆中的时候,要使用向上排序算法保证堆的结构不被破坏。到最后,堆里面的k个数就是最大的k个数了。
那么问题来了,上面的例子中为什么不用大堆了,不是选最大的k个数吗?其实这很容易理解,我们假设一下,如果建一个大堆,万一堆顶的数据就是n个数中最大的那个,那么不论怎么比较,你后面的n-k个元素都没法进堆,因此要用小堆来解决这个问题。
void PrintTopK(int* a, int n, int k) { Hp hp; HpInit(&hp, a, k); int i = k; for (i = k; i < n; i++) { if (a[i]>HpTop(hp)) { HpPop(&hp); HpPush(&hp, a[i]); } } //你此时数据改变之后是在堆里面的,你打印a没用啊 //for (i = 0; i < k; i++) //{ // printf("%d ", a[i]); //} for (i = 0; i < k; i++) { printf("%d ", HpTop(hp)); HpPop(&hp); } printf("\n"); }
时间复杂度:O(k+n*logk) 空间复杂度:O(n) 与之前两种方法对比,这种方法大大提高了效率。
-
TopK问题三种方法总结
2020-02-07 17:34:35TopK问题三种方法总结 文章目录TopK问题三种方法总结what's topK?堆解题步骤具体实现summaryquickSelect解题步骤具体实现summary二分法解题步骤具体实现summaryleetcode-719-找出第 k 小的距离对leetcode-378-有序...TopK问题三种方法总结
文章目录
references:快速选择排序 Quick select 解决Top K 问题
what’s topK?
topK问题是实际应用中涉及面较广的一个抽象问题,譬如:从20亿个数字的文本中,找出最大的前100个。
堆
具体可以参考我的另一篇文章:数据结构javascript描述中对于
heap
的总结。解题步骤
- 首先把数组中的前k个值用来建一个小根堆(不是大根堆)。
- 之后的其他数拿到之后进行判断,如果遇到比小顶堆的堆顶的值大的,将堆顶元素删除,将该元素放入堆中
- 最终的堆会是数组中最大的K个数组成的结构,小根堆的顶部又是结构中的最小数,因此把堆顶的值弹出即可得到Top-K。
具体实现
// 注意如果求的不是topK而是lowK则是用 大根堆 import Heap from './algorithm/Heap/MinHeap'; const topK=(arr,k)=>{ let h=new Heap(); for(let i=0;i<k;i++){ h.insert(arr[i]); } for(let i=k;i<arr.length;i++){ if (arr[i]>h.data[0]){ h.deleting(); h.insert(arr[i]); } } return h.data[0]; };
summary
- 时间复杂度:
O(NlogK)
其中N
为数组全部长度,K
即为要求的K
(因为堆中元素的数目永远是K
)
quickSelect
解题步骤
- swap函数交换元素位置
- partition 按照快排的分割思想,pivot左边是比pivot小的所有数,返回pivot所在位置
- 核查pivot-left+1和k大小比较
- 如果大于k那么topK就在pivot左侧的这些数里面
- 如果等于k那么topK就是pivot所在位置的值
- 如果小于k那么寻找pivot右侧的top
k-(pivot-left+1)
即可
具体实现
const swap=(arr,a,b)=>{ let temp=arr[a]; arr[a]=arr[b]; arr[b]=temp; }; const partition=(arr,k,left,right)=>{ let pivot=left,lessThan=left; if(left===right) return left; for(let i=left;i<=right;i++){ if(arr[i]<arr[pivot]){ lessThan++; swap(arr,lessThan,i); } } swap(arr,lessThan,pivot); return lessThan; }; const quickSelect=(arr,k,left,right)=>{ let idx=partition(arr,k,left,right); // 一定要注意:idx已经被检查过所以不能再将其加入重新进行检查 if(right-idx+1>k){ return quickSelect(arr,k,idx+1,right); }else if(right-idx+1===k){ return arr[idx]; }else{ return quickSelect(arr,k-(right-idx+1),left,idx-1); } }; const topK=(arr,k)=>{ return quickSelect(arr,k,0,arr.length-1); };
summary
quickSelect
方法 与Quick sort不同的是,Quick select只考虑所寻找的目标所在的那一部分子数组,而非像Quick sort一样分别再对两边进行分 割。正是因为如此,Quick select将平均时间复杂度从O(nlogn)
降到了O(n)
,但与此同时,QuickSelect与QuickSort一样,是一个不稳定的算法;pivot选取直接影响了算法的好坏,worst case下的时间复杂度达到了O(n^2)
- 时间复杂度最大为:O(n^2)
- 时间复杂度最小为:O(n)
- 空间复杂度:O(1)
二分法
关于二分查找法的详解可以参考我的另一篇文章:详解二分查找法
解题步骤
- 找到最大值max和最小值min
- 计算mid值开始循环查找
- 注意我们的max可以等于min,因为max min均为数组中的值
- 如果比mid大的数目大于等于k,那么mid过小,min变成mid+1
- 为什么要把等于k的情况加入呢,因为等于k的情况下,选取的mid是小于等于目标值的
- 如果比mid大的数目小于k,那么mid过大,max变成mid-1
- 返回max值即为我们想要的
具体实现
const topK2=(arr,k)=>{ let low=Number.MAX_SAFE_INTEGER,high=-Number.MAX_SAFE_INTEGER; for(let i=0;i<arr.length;i++){ if(arr[i]<low){ low=arr[i]; } if(arr[i]>high){ high=arr[i]; } } // count用来计算从大于mid小于high的数字的个数 let cn; while(low<=high){ let mid=Math.floor((low+high)/2); cn=count(arr,mid); // console.info('===>',{low,high},cn,mid); if(cn>=k){ // mid is too small low=mid+1; }else{ // mid is too big high=mid-1; } } return high; }; // =========>扩展 /** * 如何改造成求最小的第k个值呢 * @param arr * @param k * @returns {number} */ const topK3=(arr,k)=>{ const count1=(arr,target)=>{ let count=0; for(let i=0;i<arr.length;i++){ if(arr[i]<=target){ count++; } } return count; }; let low=Number.MAX_SAFE_INTEGER,high=-Number.MAX_SAFE_INTEGER; for(let i=0;i<arr.length;i++){ if(arr[i]<low){ low=arr[i]; } if(arr[i]>high){ high=arr[i]; } } // count用来计算从大于mid小于high的数字的个数 let cn; while(low<=high){ let mid=Math.floor((low+high)/2); cn=count1(arr,mid); // console.info('===>',{low,high},cn,mid); if(cn>=k){ // mid is too big high=mid-1; }else{ // mid is too small low=mid+1; } } return low; };
summary
- 时间复杂度:O(nlog(max-min)) (不确定)
- 空间复杂度:O(1)
leetcode-719-找出第 k 小的距离对
首先这个题就是典型的topk问题,但是用构建最大堆的方式并不能通过,因此这边可以考虑用二分法的方式解决,既然采用二分法套用上面模板即可,但是难点在于如何遍历所有找出来小于mid的所有距离对的个数呢?(遍历所有显然不现实)
此处查找count数目用到了双指针:
- 维护一个right 递增
- 查找一个最小的left满足
arr[right]-arr[left]<=mid
- 叠加
right-left
的值即为小于mid的所有距离对个数。(至于为何是right-left
可以通过自己举例验证比如1到4之间有多少距离对:3+2+1
)
const count=(arr,target)=>{ let res=0,left=0; for(let right=0;right<arr.length;right++){ while(arr[right]-arr[left]>target)left++; res+=right-left; } return res; }; const smallestDistancePair1=(arr,k)=>{ arr.sort((a,b)=>a-b); let min=0,max=arr[arr.length-1]-arr[0]; while(min<=max){ let mid=Math.floor((min+max)/2); let cn=count(arr,mid); if(cn>=k){ // mid过大,===k的情况时有可能取的mid也是一个大于目标值的数 max=mid-1; }else{ min=mid+1; } } return min; };
leetcode-378-有序矩阵中第K小的元素
解题思路可以参考我的题解二分法解决or最小堆解决(此处不赘述)
-
Top K算法分析
2018-10-04 20:35:33TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 问题描述: 从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。 栗子: 从arr[1... -
【PyTorch】torch.topk() 函数详解
2021-10-05 10:49:00torch.topk 函数详解1. 作用2. 使用方法3. 实例演示 1. 作用 取一个tensor的topk元素(降序后的前k个大小的元素值及索引) 2. 使用方法 dim=0表示按照列求 topn dim=1表示按照行求 topn 默认情况下,dim=1 3. 实例... -
【数据结构】TopK问题
2021-11-08 23:00:45TopK问题 gitee上有更详尽的代码:堆 + TopK代码 文章目录TopK问题一、问题分析1. 方法一2. 方法二3. 方法三二、TopK实现1. 前k个数的小堆2. n-k个数和根去比较3. 打印堆三、测试 topk问题就是取n个数据中,找... -
关于topk accuracy
2020-04-06 23:34:57这就是top1,topk啥意思呢? 最大值的索引可能与标签没有对应上,只要最大值索引排序中前k个有对应的正确标签就说明预测对了,举个例子: softmax后y_scores为: [0.2,0.3,0.4,0.1] [0.15,0.3,0.05,0.5] 求arg... -
大数据量获取TopK的几种方案
2018-09-30 14:27:03生活中经常会遇到求TopK的问题,在小数据量的情况下可以先将所有数据排序,最后进行遍历。但是在大数据量情况下,这种的时间复杂度最低的也就是O(NlogN)此处的N可能为10亿这么大的数字,时间复杂度过高,那么什么... -
top k 算法
2013-10-15 20:37:56top k 算法实现 ,以及算法的具体描述 -
面试超爱问的TopK问题,这篇彻底搞明白
2021-12-16 11:46:01topK问题,就是找出序列中前k大(或小)的数,topK问题和第K大(或小)的解题思路其实大致一致的。 TopK问题是一个非常经典的问题,在笔试和面试中出现的频率都非常非常高(从不说假话)。下面,从小小白的出发点,认为to -
TopK问题算法详解
2019-08-09 14:22:26面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 画外音:除非校招,我在面试过程中从不问TopK这个问题,默认大家都知道。 问题描述:... -
TopK问题的三种解法
2021-03-19 14:12:31TopK问题是指从n个数据中取前K个数据,在生活中的应用也有很多,如游戏中xxx的排行榜前10名等。在这篇博客中我将主要利用堆去解决TopK问题。 堆排序 首先我们需要建一个堆,然后我们再进行堆排序,排好序后直接取... -
torch.topk() 函数详解
2022-03-22 10:57:14print(m.topk(3)) torch.return_types.topk( values=tensor([9, 8, 7]), indices=tensor([9, 8, 7])) 例子2:pred = torch.tensor([[-0.5816, -0.3873, -1.0215, -1.0145, 0.4053], [ 0.7265, 1.4164, 1.... -
排序——堆排序和TopK
2019-04-02 10:56:54堆排序与TopK的问题,面试中还是经常问的,索性也整理一下。下面是徒手写的,供参考. 堆排序 public void heapSort(int[] array) { // 先构造一个大顶堆 int N = array.length - 1; for (int i = (N - 1) / 2; i ... -
torch.topk()函数快速理解
2021-08-23 22:05:22该函数的作用即按字面意思理解,topk:取数组的前k个元素进行排序。 通常该函数返回2个值,第一个值为排序的数组,第二个值为该数组中获取到的元素在原数组中的位置标号。 举个栗子: import numpy as np import ... -
MapReduce实现TopK算法(实战)
2019-10-24 10:29:06MapReduce实现TopK算法(实战) 项目介绍 数据集下载 程序下载 代码讲解 运行结果示例 -
pytorch实现topk剪枝
2020-12-25 11:47:54pytorch框架下实现top-k剪枝 这篇博客,以MNIST数据集为例,对LSTM的权重矩阵实现top-k剪枝(7,2),介绍了如何在pytorch框架下实现top-k剪枝。 文章目录pytorch框架下实现top-k剪枝一、top-k剪枝二、生成掩模... -
numpy实现torch的topk方法
2020-07-28 10:57:23torch中提供了topk方法用来返回矩阵中对应维度中最大的K个元素以及在对应维度中的index,但是numpy并没有提供和torch一样的topk方法,所以在这里通过numpy的argpartition实现torch中的topk方法。 直接给出代码: def... -
topk函数的详细解释
2021-01-15 16:32:20本文主要是torch_geometric库中的topk函数的代码进行解释,该函数的在库中的路径为 torch_geometric.nn.pool,topk_pool.topk。在torch_geometric的文档中并没有有关于该函数的任何记录,可能是因为该函数属于比较... -
leetcode之TopK算法
2020-09-10 16:22:40leetcode之TopK(快排/堆排序) 快排思想 并不需要把全部都排序好,只用分组快排,快排其实是把小于基准数的所有数放在左边,大于的数都放在右边,只要找到这个基准数在快排后的下标,若下标<k-1,则将左边那组... -
TopK推荐的评价指标
2020-11-03 11:12:44在TopK推荐中,HR是一种常用的衡量召回率的指标,计算公式为: 分子:每个用户TopK列表中属于测试集的个数 的总和。 分母: 用户在测试集中的物品总个数。 例如:三个用户在测试集中的商品个数分别是10,12,8,... -
Top K 问题的解决方案
2019-01-10 16:39:23Top K是很常见的一种问题,是指在N个数的无序序列中找出最大的K个数,而其中的N往往都特别大,对于这种问题,最容易想到的办法当然就是先对其进行排序,然后直接取出最大的K的元素就行了,但是... -
【Prometheus + Grafana】 使用 topk 在 grafana 绘制 前 n 个时间序列
2021-03-05 11:11:27在grafana 中使用 topk(10, bps) 语句,结果得到如图信息,并且可以看到曲线有断层,不连贯。 期望是仅展示前10条,并且曲线是连贯的。 原因分析: 从Grafana 5.3.0开始,有一个功能允许在一段时间内正确绘制前N...