一面之猿网
让这个世界,因为我,有一点点的不一样
纯序员给你讲解topK算法的常用套路

大家好,我是不会写代码的纯序员。今天想跟大家讲一些topK问题常用的算法。

对于海量数据到处理经常会涉及到topK问题。在设计数据结构和算法的时候,主要需要考虑的,应该是当前算法(包括数据结构)跟给定情境(比如数据量级、数据类型)的适配程度,和当前问题最核心的瓶颈(如降低时间复杂度,还是降低空间复杂度)是什么。

首先,我们来举几个常见的topK问题的例子:

1,给定100个int数字,在其中找出最大的10个;
2,给定10亿个int数字,在其中找出最大的10个(这10个数字可以无序);
3,给定10亿个int数字,在其中找出最大的10个(这10个数字依次排序);
4,给定10亿个不重复的int数字,在其中找出最大的10个;
5,给定10个数组,每个数组中有1亿个int数字,在其中找出最大的10个;
6,给定10亿个string类型的数字,在其中找出最大的10个(仅需要查1次);
7,给定10亿个string类型的数字,在其中找出最大的k个(可以支持反复多次查询,其中k是一个随机数字)

上面这些问题看起来很相似,但是解决的方式却千差万别。稍有不慎,就可能使得topK问题成为系统的瓶颈。不过也不用太担心,接下来我会总结几种常见的解决思路,遇到问题的时候,大家把这些基础思路融会贯通并且杂糅组合,即可做到见招拆招。

堆排序法

这里说的是堆排序法,而不是快排或者希尔排序。虽然理论时间复杂度都是nlogn,但是堆排有一个优势,就是可以维护一个仅包含k个数字的小顶堆,当新加入的数字大于堆顶数字的时候,将堆顶元素剔除,并加入新的数字。

用C++来说明,堆在stl中是priority_queue(不是set)。

int main() {
    const int topK = 3;
    vector<int> vec = {4,1,5,8,7,2,3,0,6,9};
    priority_queue<int, vector<int>, greater<>> pq;    // 小顶堆
    for (const auto& x : vec) {
        pq.push(x);
        if (pq.size() > topK) {
            // 如果超出个数,则弹出堆顶(最小的)数据
            pq.pop();
        }
    }

    while (!pq.empty()) {
        cout << pq.top() << endl;    // 输出依次为7,8,9
        pq.pop();
    }
}

类似快排法

快排大家都知道,针对topK问题,可以对快排进行改进。仅对部分数据进行递归计算。比如,在100个数字中,找最大的10个,第一次循环的时候,povit被移动到了80的位置,则接下来仅需要在后面的20个数字中找最大的10个即可。

这样做的优势是,理论最优时间复杂度可以达到O(n),不过平均时间复杂度还是nlogn。需要说明的是,通过这种方式,找出来的最大的k个数字之间,是无序的。


int partition(vector<int>& arr, int begin, int end) {
    int left = begin;
    int right = end;
    int povit = arr[begin];

    while (left < right) {
        while (left < right && arr[right] >= povit) {right--;}
        while (left < right && arr[left] <= povit) {left++;}
        if (left < right) {swap(arr[left], arr[right]);}
    }

    swap(arr[begin], arr[left]);
    return left;
}

void partSort(vector<int>& arr, int begin, int end, int target) {
    if (begin >= end) {
        return;
    }

    int povit = partition(arr, begin, end);
    if (target < povit) {
        partSort(arr, begin, povit - 1, target);
    } else if (target > povit) {
        partSort(arr, povit + 1, end, target);
    }
}

vector<int> getMaxNumbers(vector<int>& arr, int k) {
    int size = (int)arr.size();
    // 把求最大的k个数,转换成求最小的size-k个数字
    int target = size - k;
    partSort(arr, 0, size - 1, target);
    vector<int> ret(arr.end() - k, arr.end());
    return ret;
}

int main() {
    vector<int> vec = {4,1,5,8,7,2,3,0,6,9};
    auto ret = getMaxNumbers(vec, 3);

    for (auto x : ret) {
        cout << x << endl;    // 输出7,8,9(理论上无序)
    }
}


使用bitmap

有时候topK问题会遇到数据量过大,内存无法全部加载。这个时候,可以考虑将数据存放至bitmap中,方便查询。

比如,给出10个int类型的数据,分别是【13,12,11,1,2,3,4,5,6,7】,int类型的数据每个占据4个字节,那这个数组就占据了40个字节。现在,把它们放到一个16个长度bool的bitmap中,结果就是【0,1,1,1,1,1,1,1,0,0,0,1,1,1,0,0】,在将空间占用降低至4字节的同时,也可以很方便的看出,最大的3个数字,分别是11,12和13。

需要说明的是,bitmap结合跳表一起使用往往有奇效。比如以上数据还可以记录成:从第1位开始,有连续7个1;从第11位开始,有连续3个1。这样做,空间复杂度又得到了进一步的降低。

这种做法的优势,当然是降低了空间复杂度。不过需要注意一点,bitmap比较适合不重复且有范围(比如,数据均在0~10亿之间)的数据的查询。至于有重复数据的情况,可以考虑与hash等结构的混用。

使用hash

如果遇到了查询string类型数据的大小,可以考虑hash方法。举个例子,10个string数字【"1001","23","1002","3003","2001","1111","65","834","5","987"】找最大的3个。我们先通过长度进行hash,得到长度最大为4,且有5个长度为4的string。接下来再通过最高位值做hash,发现有1个最高位为"3"的,1个为"2"的,3个为"1"的。接下来,可以通过再设计hash函数,或者是循环的方式,在3个最高位为"1"的string中找到最大的一个,即可找到3个最值大的数据。

这种方法比较适合网址或者电话号码的查询。缺点就是如果需要多次查询的话,需要多次计算hash,并且需要根据实际情况设计多个hash函数。

字典树

字典树的具体结构和查询方式,不在这里赘述了,自行百度一下就有很多。这里主要说一下优缺点。

image.png

字典树的思想,还是通过前期建立索引信息,后期可以反复多次查询,并且后期增删数据也很方便。比较适合于需要反复多次查询的情况。比如,反复多次查询字符序(例如:z>y>...>b>a)最大的k个url这种,使用字典树把数据存储一遍,就非常适合。即减少了空间复杂度,也加速了查询效率。

混合查询

以上几种方法,都是比较独立的方法。其实,在实际工作中,遇到更多的问题还是混合问题,这就需要我们对相关的内容,融浑贯通并且做到活学活用。

我举个例子:我们的分布式服务跑在10台不同机器上,每台机器上部署的服务均被请求10000次,并且记录了个这10000次请求的耗时(耗时值为int数据),找出这10*10000次请求中,从高到低的找出耗时最大的50个。看看这个问题,很现实吧。我们试着用上面介绍的方法,组合一下来求解。

  • 【方法一】
    首先,对每台机器上的10000个做类似快排,找出每台机器上top50的耗时信息。此时,单机上的这50条数据是无序的。

    然后,再将10台机器上的50条数据(共500条)放到一起,再做一次类似快排,找到最大的50个(此时应该这50个应该是无序的)。

    最后,对这50个数据做快排,从而得到最终结果。

  • 【方法二】
    首先通过堆排,分别找出10台机器上耗时(ts值)最高的50个数据,此时的这50个数据,已经是从大到小有序的了。

    然后,我们依次取出10台机器中,耗时最高的5条放入小顶堆中。

    最后,遍历10台机器上的数据,每台机器从第6个数据开始往下循环,如果这个值比堆顶的数据大,则抛掉堆顶数据并且把它加入,继续用下一个值进行同样比较。如果这个值比堆顶的值小,则结束当前循环,并且在下一台机器上做同样操作。

我介绍了两种方法,并不是为了说明哪种方法更好,或者时间复杂度更低。而是想说同样的事情有多种不同的解决方法,而且随着数据量的增加,可能会需要更多组合形式。没有最好的方法,只有合适的方法。

在这个领域,数据决定了数据结构,数据结构决定了算法。适合自己的,才会是最好的。嗯,你可以找到更好的!!!