bfptr-algorithm

bfptr-algorithm

Charles Lv7
  2023-01-13 09:50:39 2023-01-13 09:50:39 Created   2023-08-15 18:52:30 2023-08-15 18:52:30 Updated      2.4k Words  10 Mins  

bfptr-algorithm

bfptr算法

定义

BFPTR算法，又称为中位数的中位数算法，是由Blum、Floyed、Pratt、Tarjan、Rivest这五位牛人一起提出来的，其特点在于可以以最坏复杂度为$O(n)$地求解$top−k$问题。所谓$top−k$问题就是从一个序列中求解其第k大的问题。

补充——“第(前)k大数问题”常见解决方案

  • 解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为$O(nlogn + k)$。
  • 解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为$O(nk)$
  • 解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
    (1). Sa中元素的个数小于k，则Sb中的第$k-|Sa|$个元素即为第k大数；
    (2). Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为$O(n)$
  • 解法4： 二分$[S_{min},S_{max}]$查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为$O(nlogn)$
  • 解法5：用$O(4n)$的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为$O(4n + klogn)$
  • 解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度$O(nlogk)$
  • 解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度$O(n)$

​ 附注：
​ (1). STL中可以用nth_element求得类似的第n大的数（由谓词决定），使用的是解法3中的思想，还可以用partial_sort对区间进行部分排序，得到类似前k大的数（由谓词决定），它采用的是解法5的思想。

算法思想

宏观来看，BFPTR算法是快速排序思想的一种应用：
(1).每次我们找到枢纽元素，然后按照枢纽元素将数组划分为两部分，就可以得到左边x个元素都是比枢纽元素小的，右边y个元素都是比枢纽元素大的
(2).然后根据我们想要查找的k决定到哪边进行递归查找。假设我们想要查找第k小，如果x==y，则枢纽元素就是需要查找的元素，如果x>k，则到左边继续查找，如果x<k，则去右边的区间查找第k-x个元素

典型的分治思想。问题的关键在于如何查找枢纽以及如何划分，如果这两步做的不够好那么将会导致子问题的规模不能够很快的缩小，从而使复杂度退化为$ O(n^2)$
关于如何划分，主要就是快速排序的划分思想，而BFPTR算法的精髓就在于如何选择枢纽以保证复杂度不会退化。

具体实现

在BFPTR算法中，每次选择五分中位数的中位数作为pivot，这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。算法整体步骤如下：

  1. 将输入数组的 n 个元素划分为 n/5 组，每组5个元素，且至多只有一个组由剩下的 n%5 个元素组成。
  2. 寻找 n/5 个组中每一个组的中位数，首先对每组的元素进行插入排序，然后从排序过的序列中选出中位数。
  3. 对于（2）中找出的 n/5 个中位数，递归进行步骤（1）和（2），直到只剩下一个数即为这 n/5 个元素的中位数，找到中位数后并找到对应的下标 P。
  4. 进行Partion划分过程，Partion划分中的pivot元素下标为 P。
  5. 进行高低区判断即可。

选择枢纽

  1. 将数组五个五个划分为$┌n/5┐$个小块，求出每个块的中位数
  2. 递归求出这些中位数的中位数，将这个数当做枢纽，如何做到这点呢？我们BFPTR不就是求第k大吗？我们递归地调用BFPTR就可以了。

主体部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int BFPTR(T* a, int l, int r, int k) {
    if (r - l == 1)
        return l;  // 返回找到的数字
    // 五个一组的中位数的中位数的位置
    int idx = GetPovit(a, l, r);
    T povit = a[idx];
    swap(a[l], a[idx]);
    int i = l, j = r;
    while (i < j) {
        do
            ++i;
        while (i + 1 < r && a[i] < povit);
        do
            --j;
        while (a[j] > povit);
        if (i < j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    int num = j - l + 1;  // povit在当前序列中排第几
    if (k == num)
        return j;
    else if (num > k)
        return BFPTR(a, l, j, k);
    else
        return BFPTR(a, j + 1, r, k - num);
}

这里我将枢纽放在了中间，因为这样我们有可能直接返回枢纽而不必一定要将区间划分为1才返回。我认为可以一定程度上降低复杂度。
这里我返回的是需要查找的数在数组中的位置，觉得位置包含了更多的信息，我们知道位置以后可以直接得到查询的数字，可是返回查询的数字无法直接得到位置。

获取枢纽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void InsertSort(T* a, int l, int r) {  // 插入排序
    int mid = (l + r) >> 1;            // 获得中位数就足够了
    for (int i = l + 1; i <= mid; ++i) {
        T x = a[i];
        int j = i - 1;
        while (j >= l && a[j] > x) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = x;
    }
}
int BFPTR(T* a, int l, int r, int k);
T GetPovit(T* a, int l, int r) {
    int x;        // 将区间分割为[x,x+5)
    int cnt = 0;  // 有多少个中位数
    for (x = l; x + 5 < r; x += 5) {
        InsertSort(a, x, x + 5);
        swap(a[l + cnt], a[x + 2]);  // 将当前区间的中位数放在最前面
        ++cnt;
    }
    if (x < r) {
        InsertSort(a, x, r);
        swap(a[l + cnt], a[(x + r) >> 1]);
        ++cnt;
    }
    if (1 == cnt)
        return l;
    return BFPTR(a, l, l + cnt, cnt / 2);
}

其中上面是一个简单的插入排序，下面是将数组划分为五个五个的小段，求取中位数以后放在数组的前面，然后再调用BFPTR函数得到中位数的中位数。之所以放在数组前面是因为这样可以原地操作而不用占用其他的空间。

后言

虽然这个算法的复杂度为$O(n)$的，但是我将按自己思路实现的代码和按网上思路实现的代码都对规模为$1e8$规模的数据进行了测试，发现BFPTR算法不是很快。原因可能是BFPTR算法的常数比较大，而网上的思路作为一种模拟的随机性快速选择算法常数比较小。但是我认为如果要使用随机性算法的话直接使用随机数常数会更小。

bfptr完整代码

folding code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <ctime>
#include <fstream>
#include <iostream>
using namespace std;
typedef double T;
T* CreatList(int& n) {
    ifstream in("TestFile");
    in >> n;
    T* ret = new T[n];
    for (int i = 0; i < n; ++i) {
        in >> ret[i];
    }
    in.close();
    return ret;
}
void Show(T* a, int n) {
    for (int i = 0; i < n; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}
void InsertSort(T* a, int l, int r) {  // 插入排序
    int mid = (l + r) >> 1;            // 获得中位数就足够了
    for (int i = l + 1; i <= mid; ++i) {
        T x = a[i];
        int j = i - 1;
        while (j >= l && a[j] > x) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = x;
    }
}
int BFPTR(T* a, int l, int r, int k);
T GetPovit(T* a, int l, int r) {
    int x;        // 将区间分割为[x,x+5)
    int cnt = 0;  // 有多少个中位数
    for (x = l; x + 5 < r; x += 5) {
        InsertSort(a, x, x + 5);
        swap(a[l + cnt], a[x + 2]);  // 将当前区间的中位数放在最前面
        ++cnt;
    }
    if (x < r) {
        InsertSort(a, x, r);
        swap(a[l + cnt], a[(x + r) >> 1]);
        ++cnt;
    }
    if (1 == cnt)
        return l;
    return BFPTR(a, l, l + cnt, cnt / 2);
}
int BFPTR(T* a, int l, int r, int k) {
    if (r - l == 1)
        return l;  // 返回找到的数字
    // 五个一组递归求取中位数
    int idx = GetPovit(a, l, r);
    T povit = a[idx];
    swap(a[l], a[idx]);
    int i = l, j = r;
    while (i < j) {
        do
            ++i;
        while (i + 1 < r && a[i] < povit);
        do
            --j;
        while (a[j] > povit);
        if (i < j)
            swap(a[i], a[j]);
    }
    swap(a[l], a[j]);
    int num = j - l + 1;  // povit在当前序列中排第几
    if (k == num)
        return j;
    else if (num > k)
        return BFPTR(a, l, j, k);
    else
        return BFPTR(a, j + 1, r, k - num);
}
void Query(T* a, int n) {
    int k;
    while (true) {
        cout << "请输入k:";
        cin >> k;
        if (cin.fail() == true)
            break;
        if (k > n || k < 1) {  // 检查输入的有效性
            cout << "请输入1~" << n << "之间的数字" << endl;
            continue;
        }
        clock_t S, E;
        S = clock();
        int idx = BFPTR(a, 0, n, k);
        E = clock();
        cout << "区间第" << k << "大的数字为:" << a[idx] << endl;
        cout << "这次查询花费时间" << (double)(E - S) / CLOCKS_PER_SEC << "s"
             << endl;
    }
    cin.clear();
    cin.ignore();
}
int main() {
    int n;
    T* a = CreatList(n);
    Query(a, n);
    delete[] a;
    return 0;
}
  • Title: bfptr-algorithm
  • Author: Charles
  • Created at : 2023-01-13 09:50:39
  • Updated at : 2023-08-15 18:52:30
  • Link: https://charles2530.github.io/2023/01/13/bfptr-algorithm/
  • License: This work is licensed under CC BY-NC-SA 4.0.
recommend_articles
queuing-theory queuing-theory Ajax-note-3 Ajax-note-3 Ajax-note-4 Ajax-note-4
recommend_articles
queuing-theory queuing-theory Ajax-note-3 Ajax-note-3
Comments
On this page
bfptr-algorithm
  1. bfptr-algorithm
    1. bfptr算法
      1. 定义
        1. 补充——“第(前)k大数问题”常见解决方案
      2. 算法思想
      3. 具体实现
        1. 选择枢纽
        2. 主体部分
        3. 获取枢纽
      4. 后言
        1. bfptr完整代码