Happy Birthday

Happy Birthday

Happy Birthday to myself!

Hope the goal will finally be achieved!

New Theme

更新了Blog的Theme为Icarus:

FIRST AK

纪念一下人生第一次AK:

image-20200516233222811

后续题解会尽快补充

“Kry hkbwx ubogo xqpqd jlhvvd qcuucx xmwohi qvzegb qsvqskq llwzeug ipwbapd cqwfypww dyphntfz tuqppyipb dkvhhgecd wfwnphmxoa sbdfmnyeim hrsaebveez aszqnvruhr mlghuuwvec xpefyglstj”

Topological-Sort

拓扑排序

近日实现了一下拓扑排序,在这里记录一下拓扑排序的思想,并附上一个具体的题目

这里使用bfs实现

思想

对一个有向无环图(DAG-Directed Acyclic Graph)G进行拓扑排序,将G中的所有顶点拍成一个线性序列,使得图中任何一对顶点u和v,若(u, v) 属于 E(G),则u在线性序列中出现在v之前。

也就是说,由某集合上的偏序得到这个集合的全序

步骤

  1. 计算所有节点的入度(in-degree)
  2. 将所有入度为0的节点加入一个队列
  3. 然后出队,得到一个元素
  4. 将该元素指向的所有节点的入度都减1
  5. 在减的过程中,如果其减后为0则将该元素也加入队列
  6. 继续进行步骤3,直到队列为空

运用

除了以上提到的用途,还可以判断有向图中是否有环:

根据出队元素的个数,若出队元素的个数等于图中节点的个数,则该图无环;否则该有向图存在环

例题

hdu-1285

题目大意就是进行拓扑排序,来获得比赛的名次,但是名次的排列要按照最小的字典序–即同等排名的元素,编号小的放在前面,这里使用了两种方式

  • 使用priority_queue代替queue

    保证每次出队的元素都是最小的那个,具体AC代码如下:

    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
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    using namespace std;

    int n, m;

    vector<int> topSort(vector<vector<int> >& G){
    vector<int> result;
    // 记录每个节点的入度
    vector<int> in(n + 1, 0);
    for (int i = 1; i < G.size(); i++) {
    for (int j = 0; j < G[i].size(); j++) {
    in[G[i][j]]++;
    }
    }
    // 使用优先队列,保证每次出队的元素最小
    priority_queue<int, vector<int>, greater<int > > queue;
    // 第一次入队,所有in-degree为0的节点
    for (int i = 1; i < in.size();i ++) {
    if (in[i] == 0) {
    queue.push(i);
    }
    }
    while (!queue.empty()) {
    int current = queue.top();
    queue.pop();
    // 出队元素存到排序结果中
    result.push_back(current);
    // 将所有current指向的节点的in-degree全部-1
    for (int i = 0; i < G[current].size(); i++) {
    in[G[current][i]]--;
    // 如果减到0则入队
    if (in[G[current][i]] == 0) {
    queue.push(G[current][i]);
    }
    }
    }
    return result;
    }

    int main() {
    while (cin >> n >> m) {
    vector<vector<int> > G(n + 1);
    int a, b;
    for (int i = 0; i < m; i++) {
    cin >> a >> b;
    G[a].push_back(b);
    }
    vector<int> result = topSort(G);
    for (int i = 0; i < result.size(); i++) {
    cout << result[i] << ((i == result.size() - 1) ? "" : " ");
    }
    cout << endl;
    }
    }
  • 对于in-degree,每次从头开始寻找in-degree为0的节点,所以每次找到的都是当前编号最小的节点

    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
    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;

    int n, m;
    // 存放结果
    int ans[505];

    void topSort(vector<vector<int>>& G) {
    vector<int> in(n + 1);
    for (int i = 0; i < G.size(); i++) {
    for (int j = 0; j < G[i].size(); j++) {
    in[G[i][j]]++;
    }
    }
    for (int i = 1; i <= n; i++) {
    // 每次从in数组的头部开始查找,那么每次找到的都是当前编号最小的节点
    int k = 1;
    while (in[k] != 0){
    k++;
    }
    ans[i] = k;
    // 将in[k]赋值为-1来表示删除节点
    in[k] = -1;
    // 将k连接的所有节点的in-degree都-1
    for (int j = 0; j < G[k].size(); j++) {
    in[G[k][j]]--;
    }
    }
    }

    int main() {
    while (cin >> n >> m) {
    memset(ans, 0, sizeof(ans));
    int a, b;
    vector<vector<int> > G(n + 1);
    for (int i = 0; i < m; i++) {
    cin >> a >> b;
    G[a].push_back(b);
    }
    topSort(G);
    for (int i = 1; i <= n; i++) {
    cout << ans[i] << ((i == n ) ? "" : " ");
    }
    cout << endl;
    }
    return 0;
    }

Java-Map

Java-Map

受到上篇C++ STL中map的排序方式的启发,这次又来探究一下Java中对于map的不同排序方式

依然分为两种排序

  • Sort By Key
  • Sort By Value

打印map

打印map的元素使用以下的show()方法:

1
2
3
4
5
6
7
public static void show(Map<String, Integer> map) {
for (Map.Entry<String, Integer> entry: map.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("=======================");
System.out.println();
}

Sort By Value

升序

Java中对于Map的value进行排序依然需要借助其他容器,这里使用ArrayList

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
   /**
* 获取按照value升序排序后的map
* @param map 需要排序的map
* @return 排好序的map
*/
public static Map<String, Integer> sortByValueAsc(Map<String, Integer> map) {
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// 升序
Collections.sort(list, (e1, e2) -> e1.getValue().compareTo(e2.getValue()));
Map<String, Integer> sortedMap = new LinkedHashMap<>();
for (Map.Entry<String, Integer> entry: list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("boss", 2);
map.put("abuse", 1);
map.put("unit", 3);
map.put("duty", 4);

// 根据Value升序排序
System.out.println("🚀 SORT BY VALUE ASC:");
Map<String, Integer> sortedMapAsc = sortByValueAsc(map);
show(sortedMapAsc);
}

这里将Map中的entry都放到了一个List中,然后使用自定义Comparator的方式对entry进行排序;

同时也使用了一种新的MapLinkedHashMap

LinkedHashMap是有序的,它会按照元素的插入顺序对元素进行排序

结果如下:

1
2
3
4
5
6
🚀 SORT BY VALUE ASC:
abuse 1
boss 2
unit 3
duty 4
=======================

降序

同理,只是更换一下Comparator

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
/**
* 获取按照value降序排序后的map
* @param map 需要排序的map
* @return 排好序的map
*/
public static Map<String, Integer> sortByValueDesc(Map<String, Integer> map) {
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// 降序
Collections.sort(list, (e1, e2) -> e2.getValue().compareTo(e1.getValue()));
Map<String, Integer> sortedMap = new LinkedHashMap<>();
for (Map.Entry<String, Integer> entry: list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("boss", 2);
map.put("abuse", 1);
map.put("unit", 3);
map.put("duty", 4);

// 根据Value降序排序
System.out.println("🚀 SORT BY VALUE DESC");
Map<String, Integer> sortedMapDesc = sortByValueDesc(map);
show(sortedMapDesc);
}

结果如下:

1
2
3
4
5
6
🚀 SORT BY VALUE DESC
duty 4
unit 3
boss 2
abuse 1
=======================

Sort By Key

升序

对于key的排序也可以按照对value的排序一样,借助ArrayListLinkedHashMap,但这里采用另一种方式,借助TreeMap进行排序

TreeMap是另一种Map,会对Map中的元素按照key大小进行排序

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
  /**
* 通过TreeMap的方式对key按照升序排序
* @param map 要排序的map
* @return 按照key升序排好序的map
*/
public static Map<String, Integer> sortByKeyByTreeMapAsc(Map<String, Integer> map) {
/*
The naturalOrder() method of Comparator Interface in Java
returns a comparator that use to compare Comparable objects in natural order.
*/
Map<String, Integer> sortedMap = new TreeMap<>(Comparator.naturalOrder());
sortedMap.putAll(map);
return sortedMap;
}

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("boss", 2);
map.put("abuse", 1);
map.put("unit", 3);
map.put("duty", 4);


// 根据Key升序排序,使用TreeMap方式
System.out.println("🚀 SORT BY KEY ASC");
Map<String, Integer> sortedByKeyAsc = sortByKeyByTreeMapAsc(map);
show(sortedByKeyAsc);
}

Comparable对象的升序排序可以使用Comparator.naturalOrder()返回的Comparator来指定

执行的结果如下:

1
2
3
4
5
6
🚀 SORT BY KEY ASC
abuse 1
boss 2
duty 4
unit 3
=======================

降序

同理,只是需要更改Comparator

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
/**
* 通过TreeMap的方式对key按照将序排序
* @param map 要排序的map
* @return 按照key降序排好序的map
*/
public static Map<String, Integer> sortByKeyByTreeMapDesc(Map<String, Integer> map) {
/*
The reverseOrder() Returns a comparator that imposes the reverse of the natural ordering.
*/
Map<String, Integer> sortedMap = new TreeMap<>(Comparator.reverseOrder());
sortedMap.putAll(map);
return sortedMap;
}

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("boss", 2);
map.put("abuse", 1);
map.put("unit", 3);
map.put("duty", 4);

// 根据Key降序排序,使用TreeMap方式
System.out.println("🚀 SORT BY KEY DESC");
Map<String, Integer> sortedByKeyDesc = sortByKeyByTreeMapDesc(map);
show(sortedByKeyDesc);

}

Comparable对象的降序排序可以使用Comparator.reverseOrder()返回的Comparator来指定

结果如下:

1
2
3
4
5
6
🚀 SORT BY KEY DESC
unit 3
duty 4
boss 2
abuse 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
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
108
109
import java.util.*;

/**
* @author HavenTong
* @date 2020/3/5 5:34 下午
*/
public class MapUtil {

public static void show(Map<String, Integer> map) {
for (Map.Entry<String, Integer> entry: map.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("=======================");
System.out.println();
}

/**
* 获取按照value升序排序后的map
* @param map 需要排序的map
* @return 排好序的map
*/
public static Map<String, Integer> sortByValueAsc(Map<String, Integer> map) {
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// 升序
Collections.sort(list, (e1, e2) -> e1.getValue().compareTo(e2.getValue()));
Map<String, Integer> sortedMap = new LinkedHashMap<>();
for (Map.Entry<String, Integer> entry: list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}

/**
* 获取按照value降序排序后的map
* @param map 需要排序的map
* @return 排好序的map
*/
public static Map<String, Integer> sortByValueDesc(Map<String, Integer> map) {
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// 降序
Collections.sort(list, (e1, e2) -> e2.getValue().compareTo(e1.getValue()));
Map<String, Integer> sortedMap = new LinkedHashMap<>();
for (Map.Entry<String, Integer> entry: list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}


/**
* 通过TreeMap的方式对key按照升序排序
* @param map 要排序的map
* @return 按照key升序排好序的map
*/
public static Map<String, Integer> sortByKeyByTreeMapAsc(Map<String, Integer> map) {
/*
The naturalOrder() method of Comparator Interface in Java
returns a comparator that use to compare Comparable objects in natural order.
*/
Map<String, Integer> sortedMap = new TreeMap<>(Comparator.naturalOrder());
sortedMap.putAll(map);
return sortedMap;
}

/**
* 通过TreeMap的方式对key按照将序排序
* @param map 要排序的map
* @return 按照key降序排好序的map
*/
public static Map<String, Integer> sortByKeyByTreeMapDesc(Map<String, Integer> map) {
/*
The reverseOrder() Returns a comparator that imposes the reverse of the natural ordering.
*/
Map<String, Integer> sortedMap = new TreeMap<>(Comparator.reverseOrder());
sortedMap.putAll(map);
return sortedMap;
}



public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("boss", 2);
map.put("abuse", 1);
map.put("unit", 3);
map.put("duty", 4);

// 根据Value升序排序
System.out.println("🚀 SORT BY VALUE ASC:");
Map<String, Integer> sortedMapAsc = sortByValueAsc(map);
show(sortedMapAsc);

// 根据Value降序排序
System.out.println("🚀 SORT BY VALUE DESC");
Map<String, Integer> sortedMapDesc = sortByValueDesc(map);
show(sortedMapDesc);

// 根据Key升序排序,使用TreeMap方式
System.out.println("🚀 SORT BY KEY ASC");
Map<String, Integer> sortedByKeyAsc = sortByKeyByTreeMapAsc(map);
show(sortedByKeyAsc);

// 根据Key降序排序,使用TreeMap方式
System.out.println("🚀 SORT BY KEY DESC");
Map<String, Integer> sortedByKeyDesc = sortByKeyByTreeMapDesc(map);
show(sortedByKeyDesc);

}
}

STL-map

STL-map

近日做题用到了C++中STL的map容器,在涉及map的排序过程时,通常有两种方式进行排序

  • Sort by key
  • Sort by value

为了加深这两种排序方式的写法,我又写了一个demo来梳理两种排序方式的写法

map的参数

1
2
3
4
5
template < class Key,                                     // map::关键字类型
class T, // map::值类型
class Compare = less<Key>, // map::关键字比较函数
class Alloc = allocator<pair<const Key,T> > // map::allocator类
> class map;

Sort by key

升序

默认情况下,map按照key的大小升序排序,即less<Key>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void show(map<string, int>& map) {
for (auto it = map.begin(); it != map.end(); it++) {
cout << it -> first << " " << it -> second << endl;
}
cout << "================================" << endl;
cout << endl;
}

map<string, int> asc_map;
asc_map["boss"] = 2;
asc_map["abuse"] = 1;
asc_map["unit"] = 3;
asc_map["duty"] = 4;
// map默认按照key的大小升序排列, 即第三个参数为less<string>
cout << "🚀 DEFAULT: " << endl;
show(asc_map);

所以打印结果如下:

1
2
3
4
5
6
🚀 DEFAULT: 
abuse 1
boss 2
duty 4
unit 3
================================

降序

我们可以通过修改map的第三个参数来改变排序规则,使map按照Key的降序排列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void show(map<string, int, greater<string>>& map) {
for (auto it = map.begin(); it != map.end(); it++) {
cout << it -> first << " " << it -> second << endl;
}
cout << "================================" << endl;
cout << endl;
}

// map可以指定按照key的大小升序或降序排列
map<string, int, greater<string>> desc_map;
desc_map["boss"] = 2;
desc_map["abuse"] = 1;
desc_map["unit"] = 3;
desc_map["duty"] = 4;
cout << "🚀 DESC:" << endl;
show(desc_map);

打印结果为:

1
2
3
4
5
6
🚀 DESC:
unit 3
duty 4
boss 2
abuse 1
================================

Sort by value

对map的value进行排序需要借助别的容器,比如vector,将每一个map中的entry放到一个新的vector中,然后使用sort()函数加上自定义比较规则cmp即可对map中的元素按照value进行排序:

demo中使用的比较函数将按照value升序排序:

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
// 升序排列
bool cmp(const pair<string, int>& p1, const pair<string, int>& p2) {
return p1.second < p2.second;
}

void sortByValue(map<string, int>& map) {
vector<pair<string, int> > data;
for (auto it = map.begin(); it != map.end(); it++) {
data.push_back(make_pair(it -> first, it -> second));
}
sort(data.begin(), data.end(), cmp);
for (pair<string, int> p : data) {
cout << p.first << " " << p.second << endl;
}
cout << "================================" << endl;
cout << endl;
}

// 对map的value进行排序
map<string, int> value_sort_map;
value_sort_map["boss"] = 2;
value_sort_map["abuse"] = 1;
value_sort_map["unit"] = 3;
value_sort_map["duty"] = 4;
cout << "🚀 SORT BY VALUE" << endl;
sortByValue(value_sort_map);

打印结果如下:

1
2
3
4
5
6
🚀 SORT BY VALUE
abuse 1
boss 2
unit 3
duty 4
================================

完整代码

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
#include <iostream>
#include <map>
#include <utility> // 使用make_pair()
#include <string>
#include <vector>
using namespace std;

// 升序排列
bool cmp(const pair<string, int>& p1, const pair<string, int>& p2) {
return p1.second < p2.second;
}

void sortByValue(map<string, int>& map) {
vector<pair<string, int> > data;
for (auto it = map.begin(); it != map.end(); it++) {
data.push_back(make_pair(it -> first, it -> second));
}
sort(data.begin(), data.end(), cmp);
for (pair<string, int> p : data) {
cout << p.first << " " << p.second << endl;
}
cout << "================================" << endl;
cout << endl;
}


void show(map<string, int>& map) {
for (auto it = map.begin(); it != map.end(); it++) {
cout << it -> first << " " << it -> second << endl;
}
cout << "================================" << endl;
cout << endl;
}

void show(map<string, int, greater<string>>& map) {
for (auto it = map.begin(); it != map.end(); it++) {
cout << it -> first << " " << it -> second << endl;
}
cout << "================================" << endl;
cout << endl;
}


int main() {
map<string, int> asc_map;
asc_map["boss"] = 2;
asc_map["abuse"] = 1;
asc_map["unit"] = 3;
asc_map["duty"] = 4;
// map默认按照key的大小升序排列, 即第三个参数为less<string>
cout << "🚀 DEFAULT: " << endl;
show(asc_map);

// map可以指定按照key的大小升序或降序排列
map<string, int, greater<string>> desc_map;
desc_map["boss"] = 2;
desc_map["abuse"] = 1;
desc_map["unit"] = 3;
desc_map["duty"] = 4;
cout << "🚀 DESC:" << endl;
show(desc_map);


// 对map的value进行排序
map<string, int> value_sort_map;
value_sort_map["boss"] = 2;
value_sort_map["abuse"] = 1;
value_sort_map["unit"] = 3;
value_sort_map["duty"] = 4;
cout << "🚀 SORT BY VALUE" << endl;
sortByValue(value_sort_map);
return 0;
}

Machine Learning-Concepts

Machine Learning-Concepts

1. 数据

大写字母表示举证,大写字母表示向量

  • 数据整体叫数据集(data set)
  • 每一行数据称为一个样本(sample)
  • 每一个字段表达样本的一个特征(feature)
  • 第i个样本写作 $ X^{(i)} $ ,第i个样本第j个特征值写作 $X^{(i)}_j $
  • 学习的任务:标记(label), 表示为 $ y $, 第 $i$ 个样本的标记写作 $ y^{ (i) } $
  • 第 $i$ 行,也就是第 $i$ 个样本,也被称作特征向量 $ X^{ (i) } $

$$
X^{(i)} = \left(
\begin{matrix}
5.1 \
3.5 \
1.4 \
0.2
\end{matrix}
\right)
$$

  • 数学中通常把向量表示成列向量,所以通常特征可以表示成如下的形式:

$$
\left(
\begin{matrix}
(X^{ (1)} )^T \
(X^{ (2)} )^T \
(X^{ (3)} )^T
\end{matrix}
\right)
$$

  • 所有特征所存在的空间,称为特征空间(feature space)
    • 分类任务的本质就是特征空间的划分
    • 在高维空间同理
  • 特征可以很抽象
    • 图像中,每一个像素点都是特征,e.g. 28 * 28的图像就有28 * 28 = 784个特征
    • 如果彩色图像特征更多

2. 基本任务

监督学习主要处理分类和回归问题

分类

  • 二分类
    • 判断邮件是否是垃圾邮件
    • 判断发放给客户信用卡是否有风险
    • 判断肿瘤是恶性还是良性
    • 判断股票涨跌
  • 多分类
    • 数字识别
    • 图像识别
    • 判断发放给客户的信用卡的风险评级

很多复杂的问题可以转换成多分类问题

  • 一些算法只支持二分类的任务,但多分类的任务可以转换成二分类的任务
  • 一些算法天然可以完成多分类任务
  • 多标签分类 e.g. 对图片中的元素进行划分

回归

  • 结果是一个连续数字的值,而非一个类别
    • 房屋价格
    • 市场分析
    • 学生成绩
    • 股票价格
  • 有一些算法只能解决回归问题,有一些算法只能解决分类问题,有一些算法都可以解决
  • 一些情况下,回归任务可以简化为分类任务

流程

image-20200209171829338

  • 模型 $f(x)$

3. 机器学习分类

监督学习

给机器的训练数据拥有"标记"or"答案"

  • 图片已经拥有了标定信息
  • 银行已经积累了一定的客户信息和他们信用卡的信用情况
  • 医院已经积累了一定的病人信息和他们最终确诊是否患病的情况
  • 市场积累了房屋的基本信息和最终成交的金额

非监督学习

给机器的训练数据没有任何"标记"或者“答案”

对没有"标记"的数据进行分类-聚类分析

意义

对数据进行降维处理

  • 特征提取:信用卡的信用评级和人的胖瘦无关?
  • 特征压缩(特征之间关系很强):PCA

降维处理可以方便可视化

异常检测

半监督学习

  • 一部分数据标有"标记"或者"答案",另一部分数据没有

  • 更常见:各种原因产生的标记缺失

  • 通常都先使用无监督学习手段对数据做处理,之后使用监督学习手段做模型的训练和预测

增强学习

根据周围环境的情况,采取行动,根据采取行动的结果,学习行动方式

行动-反馈

奖赏或惩罚机制

4. 机器学习的其他分类

批量学习(Batch Learning)

  • 优点:简单
  • 问题:如何适应环境变化?
  • 解决方案:定时重新批量学习
  • 缺点:每次重新批量学习,运算量巨大;同时,在某些环境变化非常快的情况下,甚至不可能

在线学习(Online Learning)

输入样例和正确结果迭代进入机器学习算法

  • 优点:及时反映新的环境变化
  • 问题:新的数据带来不好的变化?
  • 解决方案:需要加强对数据进行监控
  • 其他:也适用于数据量巨大,无法完全批量学习的环境

参数学习(Parametric Learning)

e.g. 假设模型定为 $f(x) = ax + b$,那么机器学习的任务就是找到合适的 $a$ 和 $b$

特点:一旦学到了参数,就不再需要原有的数据集

非参数学习(Nonparametric Learning)

  • 不对模型进行过多假设
  • 非参数不代表没有参数

HappyNewYear

Happy New Year

今年的最后10分钟,又是自己独自面对着电脑。

没有什么别的愿望,只是希望2020年别再像2019这么烂了。

2019.12.31

23:55

validation-api

validation-api

JSR303/JSR-349,hibernate validator,spring validation之间的关系

JSR303是一项标准,JSR-349是其的升级版本,添加了一些新特性,他们规定一些校验规范即校验注解,如@Null,@NotNull,@Pattern,他们位于javax.validation.constraints包下,只提供规范不提供实现。而hibernate-validator是对这个规范的实践(不要将hibernate和数据库orm框架联系在一起),他提供了相应的实现,并增加了一些其他校验注解,如@Email,@Length,@Range等等,他们位于org.hibernate.validator.constraints包下。而万能的spring为了给开发者提供便捷,对hibernate validator进行了二次封装,

使用validation-api,通过注解形式进行数据校验

依赖包含关系

校验注解包含在spring-boot-starter-web里面

1
2
3
4
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>

查看spring-boot-starter-web的子依赖:

1
2
3
4
5
6
7
8
9
10
11
12
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-validation</artifactId>
<version>2.2.1.RELEASE</version>
<scope>compile</scope>
<exclusions>
<exclusion>
<artifactId>tomcat-embed-el</artifactId>
<groupId>org.apache.tomcat.embed</groupId>
</exclusion>
</exclusions>
</dependency>

子依赖中包含了spring-boot-starter-validation,再查看该依赖的子依赖:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<dependency>
<groupId>jakarta.validation</groupId>
<artifactId>jakarta.validation-api</artifactId>
<version>2.0.1</version>
<scope>compile</scope>
</dependency>
<dependency>
<groupId>org.hibernate.validator</groupId>
<artifactId>hibernate-validator</artifactId>
<version>6.0.18.Final</version>
<scope>compile</scope>
<exclusions>
<exclusion>
<artifactId>validation-api</artifactId>
<groupId>javax.validation</groupId>
</exclusion>
</exclusions>
</dependency>

可以发现,该子依赖中包含了validation-api,同时包含了它的实现hibernate-validator

validation-api基本注解

限制 说明
@Null 限制只能为null
@NotNull 限制必须不能为null
@AssertFalse 限制必须为false
@AssertTrue 限制必须为true
@DecimalMax(value) 限制必须为一个不大于指定值的数字
@DecimalMin(value) 限制必须为一个不小于指定值的数字
@Digits(integer,fraction) 限制必须为一个小数,且整数部分的位数不能超过integer,小数部分的位数不能超过fraction
@Future 限制必须是一个将来的日期
@FutureOrPresent 限制必须是将来的日期或现在
@PastOrPresent 限制必须是过去的日期或现在
@Past 限制必须是一个过去的日期
@Min(value) 限制必须为一个不小于指定值的数字,@Min and @Max supports primitives and their wrappers.
@Max(value) 限制必须为一个不大于指定值的数字
@Pattern(regrexp) 限制必须符合指定的正则表达式,通过regrexp指定正则表达式
@Size(max,min) 限制字符长度必须在min到max之间,supports String, Collection, Map and arrays
@NotEmpty 验证注解的元素值不为null且不为空(字符串长度不为0、集合大小不为0)
@NotBlank 验证注解的元素值不为空(不为null、去除首位空格后长度为0),不同于@NotEmpty@NotBlank只应用于字符串且在比较时会去除字符串的空格(The difference to @NotEmpty is that this constraint can only be applied on character sequences and that trailing white-spaces are ignored.)
@Email(regrexp, flags) 验证注解的元素值是Email,也可以通过正则表达式和flag指定自定义的email格式

注意

1. 对dto(@RequestBody)进行数据校验

直接在dto的类中的属性上加上校验注解。但是仅仅这样的话,该注解不会生效

需要在controller中需要校验的参数前加上@Validated注解:

e.g.

1
2
3
4
5
6
@PostMapping("/register")
public ResultEntity register(@Validated
@RequestBody CustomerRequest customerRequest){
customerService.register(customerRequest);
return ResultEntity.succeed();
}

2. 对GET请求的参数(@RequestParam)进行数据校验

@RequestParam注解的参数通常没有专门的类,需要直接在controller方法的参数处加上校验注解:

1
2
3
4
5
6
@GetMapping("/check-code")
public ResultEntity sendCheckCode(@RequestParam
@Email(message = "必须为合法邮箱地址") String email) {
customerService.sendCheckCode(email);
return ResultEntity.succeed();
}

仅仅这样,注解也不会生效。切记需要在controller类上加入@Validated注解才可以生效:

1
2
3
4
5
@Slf4j
@RestController
@Validated // 对@RequestParam的校验需要在controller上加@Validated注解
@RequestMapping("/customer")
public class CustomerController {

官方文档

https://docs.jboss.org/hibernate/stable/validator/reference/en-US/html_single/#section-builtin-constraints

Spring Boot对静态方法进行打桩

Spring Boot对静态方法进行打桩

问题

在对Spring Boot项目进行测试的时候,会对业务逻辑service层进行测试。而service层的代码可能会使用util中的工具类,而工具方法通常来说都是static类型的方法。问题在于,当对service层的代码进行测试时,我们往往需要对静态方法打桩,返回我们需要的结果。然而,主流的测试框架Mockito并不支持对静态方法的打桩。对于此问题,我们需要寻求其他框架的解决方案

解决

1.

首先,通过mockito官方文档的描述,可以发现:

What are the limitations of Mockito

  • Cannot mock final classes
  • Cannot mock static methods
  • Cannot mock final methods - their real behavior is executed without any exception.
  • Mockito cannot warn you about mocking final methods so be vigilant.

可以看到,Mockito并不支持mock静态方法,同时也有以下的描述:

Can I mock static methods?

No. Mockito prefers object orientation and dependency injection over static, procedural code that is hard to understand & change. If you deal with scary legacy code you can use JMockit or Powermock to mock static methods.

通过这样的描述,我们发现其他框架提供了解决方案:

  • JMockit
  • Powermock

之后,由于网上的回答中,Powermock更加主流,且与Mockito的语法相近,于是考虑通过Powermock框架解决问题。

再次查阅了Powermock在github上的项目主页:,得到以下的说明:

urrently PowerMock supports JUnit and TestNG. There are three different JUnit test executors available, one for JUnit 4.4-4.12, one for JUnit 4.0-4.3. The test executor for JUnit 3 is not avaliable since PowerMock 2.0.

可以看出,Powermock当前最新版本仅支持到JUnit4.12,而无法对JUnit5提供支持。然而,spring-boot-starter-test中,整合的已是JUnit5. 在网上找寻了众多的回答,所有的例子都是通过JUnit4编写的测试脚本。

且通过Powermock测试的脚本结构如下:

1
2
3
4
5
@RunWith(PowerMockRunner.class)
@PrepareForTest( { YourClassWithEgStaticMethod.class })
public class YourTestCase {
...
}

该结构为JUnit4的写法,并不能在JUnit5中使用。我也尝试强行在Spring Boot项目中单独添加JUnit4依赖,然后单独通过JUnit4来运行通过Powermock编写的测试脚本,多次尝试之后依然无法运行。于是转向另一个框架–JMockit。

2.

尝试通过JMockit来测试静态方法。首先查看JMockit是否支持JUnit5,在官网寻找到了答案:

To run tests that use any of the JMockit APIs, use your Java IDE, Maven/Gradle build script, etc. the way you normally would. In principle, any JDK of version 1.7 or newer, on Windows, Mac OS X, or Linux, can be used. JMockit supports (and requires) the use of JUnit (version 4 or 5) or TestNG

既然JMockit支持JUnit5,且可以对静态方法进行打桩,这就是一种可行的解决方案。所以接下来我就去寻找对静态方法进行打桩的实现方案。

在一篇博客中,我发现了解决方案:

  • 首先,需要添加JMockit的依赖,通过mvnrepository添加最新版的JMockit依赖:

    1
    2
    3
    4
    5
    6
    7
    <!-- https://mvnrepository.com/artifact/org.jmockit/jmockit -->
    <dependency>
    <groupId>org.jmockit</groupId>
    <artifactId>jmockit</artifactId>
    <version>1.48</version>
    <scope>test</scope>
    </dependency>
  • 查看博客中给出的例子:

    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
    // 需要测试的类
    public class AppManager {

    public boolean managerResponse(String question) {
    return AppManager.isResponsePositive(question);
    }

    public static boolean isResponsePositive(String value) {
    if (value == null) {
    return false;
    }
    int length = value.length();
    int randomNumber = randomNumber();
    return length == randomNumber ? true : false;
    }

    private static int randomNumber() {
    return new Random().nextInt(7);
    }
    }

    // 对静态方法进行打桩
    @Test
    public void givenAppManager_whenStaticMethodCalled_thenValidateExpectedResponse() {
    new MockUp<AppManager>() {
    @Mock
    public boolean isResponsePositive(String value) {
    return false;
    }
    };

    assertFalse(appManager.managerResponse("Some string..."));
    }
  • 按照类似的写法,完成了我的测试脚本的编写

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    @Test
    @DisplayName("发送邮件内容正确")
    void shouldSendCorrectEmailWhenUserIsNew(){
    // 使用JMockit对静态方法进行打桩
    new MockUp<CheckCodeUtil>(){
    @mockit.Mock
    public String generateCheckCode(){
    return "123456";
    }
    };
    when(redisTemplate.opsForValue()).thenReturn(new ValueOperationsFake());
    ArgumentCaptor<String> emailCaptor = ArgumentCaptor.forClass(String.class);
    ArgumentCaptor<String> subjectCaptor = ArgumentCaptor.forClass(String.class);
    ArgumentCaptor<String> contentCaptor = ArgumentCaptor.forClass(String.class);
    customerService.sendCheckCode("10175101152@stu.ecnu.edu.cn");
    verify(mailService, times(1))
    .sendHtmlMail(emailCaptor.capture(), subjectCaptor.capture(), contentCaptor.capture());
    assertAll(
    () -> assertEquals("10175101152@stu.ecnu.edu.cn", emailCaptor.getValue()),
    () -> assertEquals("Registration from MeetHere", subjectCaptor.getValue()),
    () -> assertEquals("<h1>Welcome to MeetHere!</h1><p>Your check code is <u>" +
    "123456" + "</u></p>", contentCaptor.getValue())
    );
    }
  • 编写完毕后,尝试是否可以运行,但是依然报错:

    1
    java.lang.IllegalStateException: JMockit didn't get initialized; please check the -javaagent JVM initialization parameter was used

    针对报错信息去Google进行查找,大多数的解决方案是:

    1
    @RunWith(JMockit.class)

    这同样是JUnit4的写法。并不能解决我所遇到的问题

  • 再次回到JMockit的官方文档,查看官方文档中给出的运行方法,发现了潜在的解决方案:

    JMockit also requires the -javaagent JVM initialization parameter to be used; when using the Maven Surefire plugin for test execution, it’s specified as follows:

    所以看来想要运行JMockito编写的测试脚本,需要指定-javaagent的JVM参数才可以。

    官网给出了方案:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    <plugins>
    <plugin>
    <artifactId>maven-surefire-plugin</artifactId>
    <version>2.22.2</version> <!-- or some other version -->
    <configuration>
    <argLine>
    -javaagent:${settings.localRepository}/org/jmockit/jmockit/${jmockit.version}/jmockit-${jmockit.version}.jar
    </argLine>
    </configuration>
    </plugin>
    </plugins>

    将这段xml复制到pom文件中,并将${jmockit.version}替换为项目中使用的1.48

  • 再次运行测试脚本:

    屏幕快照 2019-12-10 下午6.12.39

    BINGO!