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 树通常不高，需要的空间不会很大。
 

生成数组
 
百万元素
 
import numpy as np

inputs = [ np.random.random() for _ in range(1000000)]
 
计时器
 
from functools import wraps
import time

def func_timer(function):
    @wraps(function)
    def function_timer(*args, **kwargs):
        print('[Function: {name} start]'.format(name = function.__name__))
        t0 = time.time()
        result = function(*args, **kwargs)
        t1 = time.time()
        print('[Function: {name} finished, spent time: {time:.2f}s]'.format(name = function.__name__,time = t1 - t0))
        return result
    return function_timer
 
算法
 
$O(Nklog(k))$
 
@func_timer
def topk(inputs, k):
    assert(len(inputs)>k and k>=0)
    
    output = []
    for number in inputs:
        if len(output) < k:
            output.append(number)
        else:
#             output = heapq.nsmallest(k, output)  # 2.18s
#             output = sorted(output)[:k]  # 1.70s
            output.sort()  # 用时：1.07s
            if number < output[0]:
                continue
            else:
                output[0] = number
    return output[::-1]

 
print(topk(inputs,100))
'''
[Function: topk start...]
[Function: topk finished, spent time: 1.07s]
[0.9999996850874242, 0.9999986732620001, 0.9999966250630344, 0.9999965512918702, 0.9999918270818978, 0.9999908482147212, 0.9999904061966568, 0.9999898873637068, 0.9999894591229037, 0.9999885915510304, 0.9999880191296788, 0.9999875751372768, 0.9999871692714755, 0.9999864191450215, 0.9999856657239012, 0.9999844443591834, 0.999983190441878, 0.9999820489498568, 0.9999810894337499, 0.9999798321198289, 0.9999786907049485, 0.9999783739745713, 0.9999778918753542, 0.9999776934842499, 0.9999766904951057, 0.9999763063439243, 0.9999721491854319, 0.9999718129550014, 0.9999690380974163, 0.9999667084475456, 0.9999655424378023, 0.9999652281775585, 0.9999627432692645, 0.9999609286879659, 0.9999595897335395, 0.9999577801424298, 0.9999577731076444, 0.9999577422439052, 0.9999573787572927, 0.9999545285610502, 0.9999536027375621, 0.9999517383688369, 0.9999505332989274, 0.9999467936557633, 0.9999462369888729, 0.9999434710302963, 0.9999428328375325, 0.9999415741653278, 0.9999395817201105, 0.9999383994805728, 0.9999372632501194, 0.9999353698560306, 0.9999347634017355, 0.9999342421914866, 0.9999333493394821, 0.9999327463812188, 0.9999326525157203, 0.9999323359413231, 0.9999319116353387, 0.9999318213132441, 0.9999311379877591, 0.9999278784463489, 0.999927795786208, 0.9999275307723007, 0.9999256814570631, 0.9999246819583866, 0.9999242658863041, 0.99992388656362, 0.9999218118780165, 0.9999214050287274, 0.9999213871879659, 0.9999212511033996, 0.9999200515736231, 0.9999186201014783, 0.9999177853796155, 0.9999141870066893, 0.9999122366576134, 0.9999109936676648, 0.9999096934306023, 0.9999096419907019, 0.9999089127419833, 0.99990882593983, 0.9999087135374473, 0.9999059676663873, 0.9999043718775731, 0.9999041573645822, 0.9999036853969006, 0.9999032218497446, 0.9999027069924663, 0.999901741000922, 0.9999016699195791, 0.9999009761556364, 0.9998998985072448, 0.9998987815252058, 0.9998975056695498, 0.9998950521471704, 0.9998944129310622, 0.9998942554330341, 0.9998936486586968, 0.9998927647795649]
'''
 
最强的还是 heapq
 
$O(Nlog(k))$
 
0.24s
 
import heapq
import random
 
import time
 
 
class TopkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []
 
    def Push(self, elem):
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            topk_small = self.data[0]
            if elem > topk_small:
                heapq.heapreplace(self.data, elem)
 
    def TopK(self):
        return [x for x in reversed([heapq.heappop(self.data) for _ in range(len(self.data))])]
 
 

start=time.time()
th = TopkHeap(100)
for i in inputs:
    th.Push(i)
print(th.TopK())
print("cost time",time.time()-start)
'''
[0.9999996850874242, 0.9999986732620001, 0.9999966250630344, 0.9999965512918702, 0.9999918270818978, 0.9999908482147212, 0.9999904061966568, 0.9999898873637068, 0.9999894591229037, 0.9999885915510304, 0.9999880191296788, 0.9999875751372768, 0.9999871692714755, 0.9999864191450215, 0.9999856657239012, 0.9999844443591834, 0.999983190441878, 0.9999820489498568, 0.9999810894337499, 0.9999798321198289, 0.9999786907049485, 0.9999783739745713, 0.9999778918753542, 0.9999776934842499, 0.9999766904951057, 0.9999763063439243, 0.9999721491854319, 0.9999718129550014, 0.9999690380974163, 0.9999667084475456, 0.9999655424378023, 0.9999652281775585, 0.9999627432692645, 0.9999609286879659, 0.9999595897335395, 0.9999577801424298, 0.9999577731076444, 0.9999577422439052, 0.9999573787572927, 0.9999545285610502, 0.9999536027375621, 0.9999517383688369, 0.9999505332989274, 0.9999467936557633, 0.9999462369888729, 0.9999434710302963, 0.9999428328375325, 0.9999415741653278, 0.9999395817201105, 0.9999383994805728, 0.9999372632501194, 0.9999353698560306, 0.9999347634017355, 0.9999342421914866, 0.9999333493394821, 0.9999327463812188, 0.9999326525157203, 0.9999323359413231, 0.9999319116353387, 0.9999318213132441, 0.9999311379877591, 0.9999278784463489, 0.999927795786208, 0.9999275307723007, 0.9999256814570631, 0.9999246819583866, 0.9999242658863041, 0.99992388656362, 0.9999218118780165, 0.9999214050287274, 0.9999213871879659, 0.9999212511033996, 0.9999200515736231, 0.9999186201014783, 0.9999177853796155, 0.9999141870066893, 0.9999122366576134, 0.9999109936676648, 0.9999096934306023, 0.9999096419907019, 0.9999089127419833, 0.99990882593983, 0.9999087135374473, 0.9999059676663873, 0.9999043718775731, 0.9999041573645822, 0.9999036853969006, 0.9999032218497446, 0.9999027069924663, 0.999901741000922, 0.9999016699195791, 0.9999009761556364, 0.9998998985072448, 0.9998987815252058, 0.9998975056695498, 0.9998950521471704, 0.9998944129310622, 0.9998942554330341, 0.9998936486586968, 0.9998927647795649]
cost time 0.24733829498291016
'''

torch.topk(input, k, dim=None, largest=True, sorted=True, out=None) -> (Tensor, LongTensor)
 
 pytorch中文官网文档：http://www.mamicode.com/info-detail-2217311.html
 
沿给定dim维度返回输入张量input中 k 个最大值。
 如果不指定dim，则默认为input的最后一维。
 如果为largest为 False ，则返回最小的 k 个值。
 
返回一个元组 (values,indices)，其中indices是原始输入张量input中测元素下标。
 如果设定布尔值sorted 为_True_，将会确保返回的 k 个值被排序。
 
参数:
 
input (Tensor) – 输入张量
k (int) – “top-k”中的k
dim (int, optional) – 排序的维
largest (bool, optional) – 布尔值，控制返回最大或最小值
sorted (bool, optional) – 布尔值，控制返回值是否排序
out (tuple, optional) – 可选输出张量 (Tensor, LongTensor) output buffer
--------------------------实例--------------------
 
假设神经网络的输出如下，为二分类。batch_size=4
 
import torch

output = torch.tensor([[-5.4783, 0.2298],
                           [-4.2573, -0.4794],
                           [-0.1070, -5.1511],
                           [-0.1785, -4.3339]])
 
得到其top1值操作如下：
 
maxk = max((1,))  # 取top1准确率，若取top1和top5准确率改为max((1,5))
_, pred = output.topk(maxk, 1, True, True)
 
topk参数中，maxk取得是top1准确率，dim=1是按行取值， largest=1是取最大值
 
结果如下，
 
_
tensor([[ 0.2298],
        [-0.4794],
        [-0.1070],
        [-0.1785]])
 
pred
tensor([[1],
        [1],
        [0],
        [0]])
 
 
 
_是top1的值，pred是最大值的索引（size=4*1），一般会进行转置处理同真实值对比
 
 
 
 
 
 
 
 
 
 
 
 
 
 

个人博客请访问 http://www.x0100.top 
 
TopK，是问得比较多的几个问题之一，到底有几种方法，这些方案里蕴含的优化思路究竟是怎么样的，今天和大家聊一聊。
 
问题描述：
 
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
 
栗子：
 
从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中，找出最大的k=5个。
 
 
 
一、排序
 
 
排序是最容易想到的方法，将n个数排序之后，取出最大的k个，即为所得。
 
 
 
伪代码：
 
sort(arr, 1, n);
 
return arr[1, k];
 
 
 
时间复杂度：O(n*lg(n))
  
 
分析：明明只需要TopK，却将全局都排序了，这也是这个方法复杂度非常高的原因。那能不能不全局排序，而只局部排序呢？这就引出了第二个优化方法。
 
 
 
二、局部排序
 
不再全局排序，只对最大的k个排序。
 
 
冒泡是一个很常见的排序方法，每冒一个泡，找出最大值，冒k个泡，就得到TopK。
 
 
 
伪代码：
 
for(i=1 to k){
 
         bubble_find_max(arr,i);
 
}
 
return arr[1, k];
 
 
 
时间复杂度：O(n*k)
 
 
 
分析：冒泡，将全局排序优化为了局部排序，非TopK的元素是不需要排序的，节省了计算资源。不少朋友会想到，需求是TopK，是不是这最大的k个元素也不需要排序呢？这就引出了第三个优化方法。
 
 
 
三、堆
 
思路：只找到TopK，不排序TopK。
 
 
先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。
 
 
 
 
接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。
 
 
 
 
直到，扫描完所有n-k个元素，最终堆中的k个元素，就是猥琐求的TopK。
 
 
 
伪代码：
 
heap[k] = make_heap(arr[1, k]);
 
for(i=k+1 to n){
 
         adjust_heap(heep[k],arr[i]);
 
}
 
return heap[k];
 
 
 
时间复杂度：O(n*lg(k))
 
画外音：n个元素扫一遍，假设运气很差，每次都入堆调整，调整时间复杂度为堆的高度，即lg(k)，故整体时间复杂度是n*lg(k)。
 
 
 
分析：堆，将冒泡的TopK排序优化为了TopK不排序，节省了计算资源。堆，是求TopK的经典算法，那还有没有更快的方案呢？
 
 
 
四、随机选择
 
随机选择算在是《算法导论》中一个经典的算法，其时间复杂度为O(n)，是一个线性复杂度的方法。
 
 
 
这个方法并不是所有同学都知道，为了将算法讲透，先聊一些前序知识，一个所有程序员都应该烂熟于胸的经典算法：快速排序。
 
画外音：
 
（1）如果有朋友说，“不知道快速排序，也不妨碍我写业务代码呀”…额...
 
（2）除非校招，我在面试过程中从不问快速排序，默认所有工程师都知道；
 
 
 
其伪代码是：
 
void quick_sort(int[]arr, int low, inthigh){
 
         if(low== high) return;
 
         int i = partition(arr, low, high);
 
         quick_sort(arr, low, i-1);
 
         quick_sort(arr, i+1, high);
 
}
 
 
 
其核心算法思想是，分治法。
 
 
 
分治法（Divide&Conquer），把一个大的问题，转化为若干个子问题（Divide），每个子问题“都”解决，大的问题便随之解决（Conquer）。这里的关键词是“都”。从伪代码里可以看到，快速排序递归时，先通过partition把数组分隔为两个部分，两个部分“都”要再次递归。
 
 
 
分治法有一个特例，叫减治法。
 
 
 
减治法（Reduce&Conquer），把一个大的问题，转化为若干个子问题（Reduce），这些子问题中“只”解决一个，大的问题便随之解决（Conquer）。这里的关键词是“只”。
 
 
 
二分查找binary_search，BS，是一个典型的运用减治法思想的算法，其伪代码是：
 
int BS(int[]arr, int low, inthigh, int target){
 
         if(low> high) return -1;
 
         mid= (low+high)/2;
 
         if(arr[mid]== target) return mid;
 
         if(arr[mid]> target)
 
                   return BS(arr, low, mid-1, target);
 
         else
 
                   return BS(arr, mid+1, high, target);
 
}
 
 
 
从伪代码可以看到，二分查找，一个大的问题，可以用一个mid元素，分成左半区，右半区两个子问题。而左右两个子问题，只需要解决其中一个，递归一次，就能够解决二分查找全局的问题。
 
 
 
通过分治法与减治法的描述，可以发现，分治法的复杂度一般来说是大于减治法的：
 
快速排序：O(n*lg(n))
 
二分查找：O(lg(n))
 
 
 
话题收回来，快速排序的核心是：
 
i = partition(arr, low, high);
 
 
 
这个partition是干嘛的呢？
 
顾名思义，partition会把整体分为两个部分。
 
更具体的，会用数组arr中的一个元素（默认是第一个元素t=arr[low]）为划分依据，将数据arr[low, high]划分成左右两个子数组：
 
 
左半部分，都比t大
 
 
右半部分，都比t小
 
 
中间位置i是划分元素
 
 
以上述TopK的数组为例，先用第一个元素t=arr[low]为划分依据，扫描一遍数组，把数组分成了两个半区：
 
 
左半区比t大
 
 
右半区比t小
 
 
中间是t
 
partition返回的是t最终的位置i。
 
 
 
很容易知道，partition的时间复杂度是O(n)。
 
画外音：把整个数组扫一遍，比t大的放左边，比t小的放右边，最后t放在中间N[i]。
 
 
 
partition和TopK问题有什么关系呢？
 
TopK是希望求出arr[1,n]中最大的k个数，那如果找到了第k大的数，做一次partition，不就一次性找到最大的k个数了么？
 
画外音：即partition后左半区的k个数。
 
 
 
问题变成了arr[1, n]中找到第k大的数。
 
 
 
再回过头来看看第一次partition，划分之后：
 
i = partition(arr, 1, n);
 
 
如果i大于k，则说明arr[i]左边的元素都大于k，于是只递归arr[1, i-1]里第k大的元素即可；
 
 
如果i小于k，则说明说明第k大的元素在arr[i]的右边，于是只递归arr[i+1, n]里第k-i大的元素即可；
 
画外音：这一段非常重要，多读几遍。
 
 
 
这就是随机选择算法randomized_select，RS，其伪代码如下：
 
int RS(arr, low, high, k){
 
  if(low== high) return arr[low];
 
  i= partition(arr, low, high);
 
  temp= i-low; //数组前半部分元素个数
 
  if(temp>=k)
 
      return RS(arr, low, i-1, k); //求前半部分第k大
 
  else
 
      return RS(arr, i+1, high, k-i); //求后半部分第k-i大
 
}
 
 
 
 
这是一个典型的减治算法，递归内的两个分支，最终只会执行一个，它的时间复杂度是O(n)。
 
 
 
再次强调一下：
 
 
分治法，大问题分解为小问题，小问题都要递归各个分支，例如：快速排序
 
 
减治法，大问题分解为小问题，小问题只要递归一个分支，例如：二分查找，随机选择
 
 
 
通过随机选择（randomized_select），找到arr[1, n]中第k大的数，再进行一次partition，就能得到TopK的结果。
 
 
 
五、总结
 
TopK，不难；其思路优化过程，不简单：
 
 
全局排序，O(n*lg(n))
 
 
局部排序，只排序TopK个数，O(n*k)
 
 
堆，TopK个数也不排序了，O(n*lg(k))
 
 
分治法，每个分支“都要”递归，例如：快速排序，O(n*lg(n))
 
 
减治法，“只要”递归一个分支，例如：二分查找O(lg(n))，随机选择O(n)
 
 
TopK的另一个解法：随机选择+partition
 
 
 
知其然，知其所以然。
 
思路比结论重要。
 
更多精彩内容扫描下方二维码进入网站。。。。。
 
 
关注微信公众号。。。。。