精华内容
下载资源
问答
  • topK
    千次阅读
    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

    更多相关内容
  • Tom 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:18
    TopK,不难;其思路优化过程,不简单: • 全局排序,O(n*lg(n)) • 局部排序,只排序TopK个数,O(n*k) • 堆,TopK个数也不排序了,O(n*lg(k)) • 分治法,每个分支“都要”递归,例如:快速排序,O(n*lg(n)) • 减...
  • topk 问题,就是从一个数组或者列表中获取最大的K个数,求3个积分,因为我需要3个积分下载东西,但是,我的里面的topK 解决方案肯定是比较全的,如果有什么看不懂的,请联系我,绝对负责给你讲清楚
  • topk问题的Python实现,k-堆实现
  • U-Topk是基于不确定性数据可能世界模型而提出的一种查询语义.随着不确定性数据集的增大,可能世界的实例数量指数增长,这为U-Topk查询处理提出了重大挑战.针对属性级不确定性的U-Topk查询处理算法展开研究,提出了U-Top...
  • topK

    千次阅读 2019-04-19 17:24:42
    topK 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:52
    Topk问题的三种求解方法什么是Topk问题方法一:堆排序法方法二:把N个数建堆,取出前k个方法三:建一个k个数的堆 什么是Topk问题 其实顾名思义,这个问题也就是在N个数中找出前k个最值。在我们的日常生活中,很多...

    什么是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:35
    TopK问题三种方法总结 文章目录TopK问题三种方法总结what's topK?堆解题步骤具体实现summaryquickSelect解题步骤具体实现summary二分法解题步骤具体实现summaryleetcode-719-找出第 k 小的距离对leetcode-378-有序...

    TopK问题三种方法总结


    references:

    Top K问题的两种解决思路

    TOP-K问题的几种解法

    Top-K问题的几种求解方法

    快速选择排序 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右侧的topk-(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:33
    TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 问题描述: 从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。 栗子: 从arr[1...
  • 【PyTorch】torch.topk() 函数详解

    千次阅读 2021-10-05 10:49:00
    torch.topk 函数详解1. 作用2. 使用方法3. 实例演示 1. 作用 取一个tensor的topk元素(降序后的前k个大小的元素值及索引) 2. 使用方法 dim=0表示按照列求 topn dim=1表示按照行求 topn 默认情况下,dim=1 3. 实例...
  • 【数据结构】TopK问题

    千次阅读 多人点赞 2021-11-08 23:00:45
    TopK问题 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:56
    top k 算法实现 ,以及算法的具体描述
  • topK问题,就是找出序列中前k大(或小)的数,topK问题和第K大(或小)的解题思路其实大致一致的。 TopK问题是一个非常经典的问题,在笔试和面试中出现的频率都非常非常高(从不说假话)。下面,从小小白的出发点,认为to
  • TopK问题算法详解

    千次阅读 2019-08-09 14:22:26
    面试中,TopK,是问得比较多的几个问题之一,到底有几种方法,这些方案里蕴含的优化思路究竟是怎么样的,今天和大家聊一聊。 画外音:除非校招,我在面试过程中从不问TopK这个问题,默认大家都知道。 问题描述:...
  • TopK问题的三种解法

    千次阅读 2021-03-19 14:12:31
    TopK问题是指从n个数据中取前K个数据,在生活中的应用也有很多,如游戏中xxx的排行榜前10名等。在这篇博客中我将主要利用堆去解决TopK问题。 堆排序 首先我们需要建一个堆,然后我们再进行堆排序,排好序后直接取...
  • torch.topk() 函数详解

    千次阅读 2022-03-22 10:57:14
    print(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:06
    MapReduce实现TopK算法(实战) 项目介绍 数据集下载 程序下载 代码讲解 运行结果示例
  • pytorch实现topk剪枝

    千次阅读 热门讨论 2020-12-25 11:47:54
    pytorch框架下实现top-k剪枝 这篇博客,以MNIST数据集为例,对LSTM的权重矩阵实现top-k剪枝(7,2),介绍了如何在pytorch框架下实现top-k剪枝。 文章目录pytorch框架下实现top-k剪枝一、top-k剪枝二、生成掩模...
  • numpy实现torch的topk方法

    千次阅读 2020-07-28 10:57:23
    torch中提供了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:40
    leetcode之TopK(快排/堆排序) 快排思想 并不需要把全部都排序好,只用分组快排,快排其实是把小于基准数的所有数放在左边,大于的数都放在右边,只要找到这个基准数在快排后的下标,若下标<k-1,则将左边那组...
  • TopK推荐的评价指标

    千次阅读 2020-11-03 11:12:44
    TopK推荐中,HR是一种常用的衡量召回率的指标,计算公式为: 分子:每个用户TopK列表中属于测试集的个数 的总和。 分母: 用户在测试集中的物品总个数。 例如:三个用户在测试集中的商品个数分别是10,12,8,...
  • Top K 问题的解决方案

    万次阅读 多人点赞 2019-01-10 16:39:23
    Top K是很常见的一种问题,是指在N个数的无序序列中找出最大的K个数,而其中的N往往都特别大,对于这种问题,最容易想到的办法当然就是先对其进行排序,然后直接取出最大的K的元素就行了,但是...
  • 在grafana 中使用 topk(10, bps) 语句,结果得到如图信息,并且可以看到曲线有断层,不连贯。 期望是仅展示前10条,并且曲线是连贯的。 原因分析: 从Grafana 5.3.0开始,有一个功能允许在一段时间内正确绘制前N...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 410,384
精华内容 164,153
关键字:

topK