Problem Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
    There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […[2 3], [4 5], [7 5], [11 5], [12 7]…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […[2 3], [4 5], [12 7], …]

problem link:
https://leetcode.com/problems/the-skyline-problem/

Solution

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
public class TheSkylineProblem_218 {
public List<int[]> getSkylineSimpleSolution(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
// height < 0: the height of building started
// height > 0: the height of building ended
for (int[] b : buildings) {
height.add(new int[]{b[0], -b[2]});
height.add(new int[]{b[1], b[2]});
}
// sorted by x value, if x equals then sorted by y value
Collections.sort(height, (a, b) -> {
if (a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
});
// record the height of visited buildings by reverse order
Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
int prevHeight = 0;
for (int[] h : height) {
if (h[1] < 0) {
// save the height of building
pq.offer(-h[1]);
} else {
// remove the height of building
pq.remove(h[1]);
}
int curHeight = pq.peek();
if (prevHeight != curHeight) {
// find the turn point
result.add(new int[]{h[0], curHeight});
prevHeight = curHeight;
}
}
return result;
}
}

算法解释

算法思路

  1. 遍历所有的点,height用来存放每个顶点,左顶点的高度转为负数,右顶点的高度仍然是正数
  2. 对height数组排序,首先按x的值排序,当x的值相等时按z排序,这样保证了即使矩形的起点一样,也是最先处理最高的点。对于[{1,2,1},{1,2,2},{1,2,3}]这样的情况会优先处理{1,2,3}这个点。
  3. 使用优先级队列pq来保存当前最近buildings的高度,这个结构很重要!
  4. 遍历height数组,碰到左顶点时,将高度放入pq中,否则,碰到右顶点时则将高度从pq从移除。这样做的好处是,每次走完一个矩形时,高度能回归到之前的buildings的高度。
  5. 获取当前的最高高度,因为如果比当前矮的话,是不需要放入拐点中的,这点很重要!
  6. 如果当前的最高高度和之前的高度不一致,说明出现了拐点。**如果当前的最高高度矮于之前的值,说明之前的很高的建筑遇到了它的右顶点从而被移除了,所以目前的最高高度即使矮于之前的点,但是是新的隔离的building了,所以可以加入。那么如果高呢?当前高度比之前高,那肯定会是拐点了。

总结

几个关键点:

  1. 对顶点进行排序保存,对左右顶点根据正负号来加以区分
  2. 使用一个优先级队列来保存目前最高的建筑
  3. 碰到右顶点时消除目前的建筑高度
  4. 根据之前的高度和处理目前顶点以后(可能是加入了高度也可能是消除了之前的高度)的高度,对两者进行比较来找到拐点

Reference

https://leetcode.com/discuss/54201/short-java-solution

扔瓶子测楼层

一栋楼有n层,需要测试某种材质的玻璃瓶从哪一层掉下来恰好会碎。现在仅有两个这样的瓶子。请问怎样仍才能最快的测出楼层的临界值?

A. 只用一个瓶子从第一层扔到第n层

找到临界值的扔瓶子次数的期望为每一层的期望次数之和

1
E(x) = 1/n * 1 + 1/n * 2 + 1/n * 3 + ... + 1/n * n = (1+n)/2

所以时间复杂度是O(n)

B. 用贪心的思维

第一个瓶子从第1层开始扔,每次层数翻倍,依次为,1,2,4,8,16,直至在第 2^k 层碎掉。
第二个瓶子从第 2^(k-1) 层开始扔,直至第 2^k 层为止,中间肯定能找到临界值。
所以时间复杂度是O(lgn)

C. 用二分法

第一个瓶子每次以(i, j)为区间,扔的位置为(i+j)/2, 初始情况, i=0,j=n, 如果瓶子没碎,则i=j,直至碎掉。
第二个瓶子从第 i 层开始扔,直至第 j 层为止,中间肯定能找到临界值。

对于第 i 层,扔的情况为:

  • 第一个瓶子:n/2, $/2+n/4 i, n/2+n/4+n/8
  • 第二个瓶子:n/2+n/4, (n/2+n/k+1), …, i

显而易见,时间复杂度是O(n)

D. 数学推算

这个题目是需要最快的找出临界值,可以转换为,即使在最坏的情况下,也能最快地找出临界值。

我们先假设最坏情况下,瓶子下落次数为x,即我们为了找出N,一共用瓶子做了x次的实验。

那么,我们第一次应该在哪层楼往下扔瓶子呢?

先让我们假设第一次是在第y层楼扔的瓶子,如果第一个瓶子在第一次扔就碎了,我们就只剩下一个瓶子,要用它准确地找出N,只能从第一层向上,一层一层的往上测试,直到它摔坏为止,答案就出来了。

由于第一个瓶子在第y层就摔破了,所以最坏的情况是第二个瓶子要把第1到第y-1层的楼都测试一遍,最后得出结果,噢,原来瓶子在第y-1层才能摔破(或是在第y-1层仍没摔破,答案就是第y层。) 这样一来测试次数是1+(y-1)=x,即第一次测试要在第x层。

OK,那如果第一次测试鸡蛋没摔破呢,那N肯定要比x大,要继续往上找,需要在哪一层扔呢?我们可以模仿前面的操作,如果第一个瓶子在第二次测试中摔破了,那么第二个瓶子的测试次数就只剩下x-2次了(第一个瓶子已经用了2次)。这样一来,第二次扔瓶子的楼层和第一次扔瓶子的楼层之间就隔着x-2层。

我们再回过头来看一看,第一次扔瓶子的楼层在第x层,第1层到第x层间共x层;第1次扔鸡蛋的楼层到第2次扔瓶子的楼层间共有x-1层(包含第2次扔瓶子的那一层),同理继续往下,我们可以得出,第2次扔瓶子的楼层到第3次扔瓶子的楼层间共有x-2层,最后把这些互不包含的区间数加起来,应该大于等于总共的楼层数量100,即

1
2
3
x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100
得出答案是14

即我先用第1个瓶子在以下序列表示的楼层数不断地向上测试,直到它摔破。 再用第2个瓶子从上一个没摔破的序列数的下一层开始,向上测试,即可保证在最坏情况下也只需要测试14次,就能用2个瓶子找出从哪一层开始,往下扔鸡蛋,瓶子就会摔破。

1
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

E. DP的解法

假设f(n)表示从第n层楼扔下鸡蛋,没有摔碎的最少尝试次数。第一个鸡蛋,可能的落下位置[1,n],第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,第二个鸡蛋,需要从第一层开始试验,有i-1次机会
  • 没碎,两个鸡蛋,还有n-i层。这个就是子问题了f(n-i)

所以,当第一个鸡蛋,由第i个位置落下的时候,要尝试的次数为 1 + max{i - 1, f(n - i)},那么对于每一个i,尝试次数最少的,就是f(n)的值。
状态转移方程如下:

1
f(n) = min{1 + max{i - 1, f(n - 1)}}

其中: i的范围为[1, n], f(1) = 1.

F. 推广到一般化的问题

为n层楼,m个鸡蛋。
如下分析: 假设f(n,m)表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,还剩m-1个鸡蛋,为确定下面楼层中的安全楼层,还需要f(i-1,m-1)次,找到子问题
  • 不碎,上面还有n-i层,还需要f(n-i,m)次,又一个子问题。

状态转移方程如下:

1
f(n, m) = min{1 + max{f(n - 1, m - 1), f(n - i, m)}}

其中: i为[1, n], f(i, 1) = 1

Reference

http://www.cricode.com/3558.html
https://gist.github.com/sing1ee/5971946

快速排序的思路

1
2
3
4
5
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)

快速排序的partition方式

一种是Lomuto partition scheme,另外一种是Hoare partition scheme。

Lomuto partition

This scheme is attributed to Nico Lomuto and popularized by Bentley in his book

lomuto的partition实现方式

i指示最前面的大于pivot的元素位置,j从前往后滑动来调整元素位置。每次j碰到小于pivot的元素,则swap i位置的元素和j位置的元素,再i指向下一个大于pivot的元素。
最后,记得swap i位置的元素和最末尾的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
private int lomutoPartition(int nums[], int lo, int hi) {
int pivot = nums[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, hi); // replace the guard element
return i;
}

Hoare partition scheme

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion.

Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.

hoare的partition实现方式

i从前往后找到大于pivot的元素,j从后往前找到小于pivot的元素,然后两者swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int hoarePartition(int nums[], int lo, int hi) {
int pivot = nums[lo];
int i = lo, j = hi;
while (true) {
while (nums[i] < pivot) {
i++;
}
while (nums[j] >= pivot) {
j--;
}
if (i >= j) {
return j;
}
swap(nums, i, j);
}
}

硬币找零问题(Coin Change)

Question

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

DP求解

如果是用DP求解,那么思路首先就是找到子问题。子问题很容易确定,那就是amount-x是子问题的amount。比较容易想到的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int coinChange(int[] coins, int amount) {
if (amount == 0)
return 0;
int n = amount + 1; // the answer must smaller than [amount+1], nice!
for (int coin : coins) {
int curr = 0;
if (amount >= coin) {
int next = coinChange(coins, amount - coin);
if (next >= 0)
curr = 1 + next;
}
if (curr > 0)
n = Math.min(n, curr);
}
return (n == amount + 1) ? -1 : n;
}

上述算法的时间复杂度为O(c^n),c是coin的数量,n是amount的值。

时间复杂度较大的原因是,中间存在很多重复计算。那么需要用到DP的备忘录,不用全局变量来保存计算过的值,也不用递归的方法来实现,而是只用一个一维数组,再用循环来实现。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount <= 0)
return 0;
int[] minNumber = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
minNumber[i] = amount + 1;
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && minNumber[i - coins[j]] != amount + 1)
minNumber[i] = Integer.min(minNumber[i], 1 + minNumber[i - coins[j]]);
}
}
if (minNumber[amount] == amount + 1)
return -1;
else
return minNumber[amount];
}

题目

输入二维数组,a[i][j]=1 表示从i结点指向j结点。

eg1

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

是一棵树,树为:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/
d

eg2

0 1 1 0

1 0 0 1

1 0 1 0

0 1 1 0

不是一颗树,是有环(a-b-d-c-a)的图:

1
2
3
4
5
6
7
8
9
a
/ \
b c
/ /
d - — -

关键点

判断一张图是否是一颗树的两个关键点:

  • 不存在环路(对于有向图,不存在环路也就意味着不存在强连通子图)
  • 满足边数加一等于顶点数的规律(不考虑重边和指向自身的边)

方法

  1. DFS

  2. 如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。时间复杂度O(ve),v是顶点数,e是边数。

    第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一。

    第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点,则存在环,否则没有环。这个复杂度也很高

  3. 结合树的特性(边数+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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
import java.util.ArrayList;
import java.util.List;
public class TreeJudgeUnionB {
private static class Edge {
int start;
int end;
public Edge(int start, int end) {
this.start = start;
this.end = end;
}
}
// the number of edges
private int n;
// edge list
private List<Edge> edges = new ArrayList<>();
// the index of group
private int[] group;
// the size of tree
private int[] size;
public TreeJudgeUnionB(int n, List<Edge> edges) {
this.n = n;
this.edges = edges;
group = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
group[i] = i;
size[i] = 1;
}
}
private int find(int i) {
// find the root of a tree which contains i node
while (i != group[i]) {
i = group[i];
}
return i;
}
private boolean union(int groupI, int groupJ) {
int iRoot = find(groupI);
int jRoot = find(groupJ);
if (iRoot != jRoot) {
if (size[iRoot] < size[jRoot]) {
group[iRoot] = jRoot;
size[jRoot] += size[iRoot];
} else {
group[jRoot] = iRoot;
size[iRoot] += size[jRoot];
}
return true;
} else {
return false;
}
}
public boolean isTree() {
for (Edge edge : edges) {
if (!union(edge.start, edge.end)) {
System.out.println("input two nodes in the same tree");
return false;
}
}
boolean hasRoot = false;
for (int i = 0; i < group.length; i++) {
if (i == group[i]) {
if (!hasRoot) {
hasRoot = true;
} else {
System.out.println("exist more than one tree root");
return false;
}
}
}
printGroup();
return hasRoot;
}
public void printGroup() {
for (int i = 0; i < n; i++) {
System.out.print(group[i] + ", ");
}
System.out.println();
}
public static void main(String[] args) {
int n = 5;
List<Edge> edges = new ArrayList<>();
addEdge(edges, 0, 1);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // true
n = 5;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 0, 2);
addEdge(edges, 2, 3);
addEdge(edges, 2, 4);
isTree(n, edges); // false
n = 4;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 2, 3);
isTree(n, edges); // false
n = 7;
edges.clear();
addEdge(edges, 0, 1);
addEdge(edges, 1, 2);
addEdge(edges, 4, 5);
addEdge(edges, 3, 4);
addEdge(edges, 2, 3);
addEdge(edges, 0, 6);
isTree(n, edges); // true
}
protected static void addEdge(List<Edge> edges, int i, int j) {
edges.add(new Edge(i, j));
}
protected static void isTree(int n, List<Edge> edges) {
TreeJudgeUnionB treeJudgeUnionA = new TreeJudgeUnionB(n, edges);
boolean isTree = treeJudgeUnionA.isTree();
System.out.println("This is a tree? " + isTree);
}
}

介绍

在计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:

Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

Union:将两个子集合并成同一个集合。

适用场景

适合于判断,给出一组结点,判断他们是否联通。

实现思路

  1. 建立n个分组,每个分组代表一堆可以互相联通的结点。
  2. 遍历每对结点,找到他们各自所属的分组A, B
  3. 如果A != B,则将A, B分组union起来,表示A, B分组联通了
  4. 如果A == B,则跳过

Simple Find 操作

用 group[] 数组来判断某个id属于的组。初始状态时,每个id都属于不同的组。

1
2
for(int i = 0; i < size; i++)
group[i] = i;

Simple Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q) {
// get the groupId of every node
int pId = find(p);
int qId = find(q);
// the two nodes are connected, return
if (pId == qId) {
return;
}
// union the two nodes, change groupId
for (int i = 0; i < id.length; i++) {
if (group[i] == pId) {
group[i] = qId;
}
}
}

优化

上面最后一步的union操作存在性能问题,即每次都需要改变其中一个分组中的所有结点的分组id。优化的做法是,用一颗树来表示每个分组,树的根节点表示当前组的id。

但如果用树来表示会引入一个问题,即可能存在树退化为链表的情况,这样一来,每一次加入一个结点再找根结点也会很耗时,没有达到优化的目的。
针对树可能退化为链表的解决方案是,每次合并树时,总是将矮的树挂到高的树下。这种方式也称为「按秩合并」

除了使用树来优化union性能以外,还有一种方式,称为「路径压缩」,即 Find 递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者间接引用节点的操作加速。

总结:

  1. 使用树来存储分组,Union时「按秩合并」
  2. 「路径压缩」,Find时改变每一个节点的引用到根节点

Find 操作

1
2
3
// store every tree's size
for (int i = 0; i < N; i++)
size[i] = 1;
1
2
3
4
5
6
7
8
private int find(int p)
{
if(p != group[p]){
group[p] = find(group[p])
}
return group[p]
}

Union 操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void union(int p, int q)
{
int i = find(p);
int j = find(q);
if (i == j) {
return;
}
if (size[i] < size[j]) {
group[i] = j;
size[j] += size[i];
} else {
group[j] = i;
size[i] += size[j];
}
}

时间复杂度

Statement: If m operations, either Union or Find, are applied to n elements, the total run time is O(m logn), where log is the iterated logarithm.
Proof of O(logn) time complexity of union-find: https://en.wikipedia.org/wiki/Proof_of_O\(logn)_time_complexity_of_union%E2%80%93find

Refer

https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
http://blog.csdn.net/dm_vincent/article/details/7655764
https://en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

避免使用 GroupByKey

当调用 groupByKey 时,所有的键值对(key-value pair) 都会被移动。在网络上传输这些数据非常没有必要。

以下函数应该优先于 groupByKey :

  • combineByKey
    组合数据,但是组合之后的数据类型与输入时值的类型不一样。

  • foldByKey
    合并每一个 key 的所有值,在级联函数和“零值”中使用。

combineByKey

combineByKey的定义

1
2
3
4
5
6
7
8
9
def combineByKey[C](
createCombiner: V => C,
mergeValue: (C, V) => C,
mergeCombiners: (C, C) => C,
partitioner: Partitioner,
mapSideCombine: Boolean = true,
serializer: Serializer = null): RDD[(K, C)] = {
// do something
}

combineByKey函数主要接受了三个函数作为参数,分别为createCombiner、mergeValue、mergeCombiners。这三个函数足以说明它究竟做了什么。理解了这三个函数,就可以很好地理解combineByKey。

createCombiner

createCombiner:在遍历RDD的过程中,对于遍历到的(k,v),如果是第一次遇到,则对这个(k,v)调用createCombiner函数,它的作用是将v转换为c(类型是C,即聚合对象的类型,c作为聚合对象的初始值)

mergeValue

mergeValue:在遍历RDD的过程中,对于遍历到的(k,v),如果不是第一次(而是第i次, 1 < i <= n)遇到,那么将对这个(k,v)调用mergeValue函数,它的作用是将v累加到聚合对象(类型C)中,mergeValue的类型是(C,V)=>C,参数中的C遍历到此处的聚合对象,然后对v进行聚合得到新的聚合对象值

mergeCombiners

mergeCombiners:因为combineByKey是在分布式环境下执行,RDD的每个分区单独进行combineByKey操作,最后需要对各个分区的结果进行最后的聚合。它的函数类型是(C,C)=>C,每个参数是分区聚合得到的聚合对象。

combineByKey的流程

  • 假设一组具有相同 K 的 records 正在一个个流向 combineByKey(),createCombiner 将第一个 record 的value 初始化为 c (比如,c = value),然后从第二个 record 开始,来一个 record 就使用 mergeValue(c,
  • record.value) 来更新 c,比如想要对这些 records 的所有 values 做 sum,那么使用 c = c + record.value。等到records 全部被 mergeValue(),得到结果 c。假设还有一组 records(key 与前面那组的 key 均相同)一个个到来,
  • combineByKey() 使用前面的方法不断计算得到 c’。现在如果要求这两组 records 总的 combineByKey() 后的结果,那么可以使用 final c = mergeCombiners(c, c’) 来计算。

Example

1
2
3
4
5
6
7
var rdd1 = sc.makeRDD(Array(("A",1),("A",2),("A",3),("B",1),("B",2),("C",3)))
// result: ((A,1_$2_@3), (B,1_$2_), (C,3_))
rdd1.combineByKey(
(v : Int) => v + "_",
(c : String, v : Int) => c + "@" + v,
(c1 : String, c2 : String) => c1 + "$" + c2 ).collect

combineByKey应用举例

求均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
val rdd = sc.textFile("气象数据")
val rdd2 = rdd.map(x=>x.split(" ")).map(x => (x(0).substring("从年月日中提取年月"),x(1).toInt))
val createCombiner = (k: String, v: Int)=> {
(v,1)
}
val mergeValue = (c:(Int, Int), v:Int) => {
(c._1 + v, c._2 + 1)
}
val mergeCombiners = (c1:(Int,Int),c2:(Int,Int))=>{
(c1._1 + c2._1, c1._2 + c2._2)
}
val vdd3 = vdd2.combineByKey(
createCombiner,
mergeValue,
mergeCombiners
)
rdd3.foreach(x=>println(x._1 + ": average tempreture is " + x._2._1/x._2._2)

Step1 Find the resource

search in Google, steam 上已经没有了。

Step2 Fix the Max OS 10.11 bug

An error occured while starting the X11 server:
Failed to activate core devices”
Click Quit to quit X11. Click Report to see more details or send a report to Apple.

https://www.reddit.com/r/OSXElCapitan/comments/3d64sd/wineskin/ 找到解决方法。即:
open terminal:

mkdir/lib
cp -r /Applications/aoeHD.app/Contents/Frameworks/* /lib

此时再打开游戏,成功运行,听到了熟悉的声音。

Reference
https://www.reddit.com/r/OSXElCapitan/comments/3d64sd/wineskin/

将数据转成json格式:python -m json.tool

$ echo '{"json":"obj"}' | python -m json.tool
{
"json": "obj"
}

查看gzip数据

使用python的zlib库来解压

s='\x1F\x8B\x08\x00\x00\x00\x00\x00\x00\x005N\xCD\x0A\xC3 \x18{\x97\xEF,\xE5s\xF3gz\xAB\xA0/1z\x18\xC31\x87m\xA5\xEA\xA1\x94\xBE\xFB\xBE\xC3vJHB\x92\x03z\x8D\xDBXJ\x05{?\xA0,`\xE1\xB9\xCEC\xEB\x9F\xF4\x18\xDEk\x8B\x19\x18\xD4\x99d\xC9/\xCE\xF9\x10Ft\xE1\xAA\x9DFm\x8C\x92B)w\xF3\x02\xBD\xA1\x5C\xA3\x16.\x84\xE4\x5CHD\x94\x82Ao`\x97\x9E3\x83Df\xDBzdP\xD2_{\x11C\x06\xB9\x13\x9C\x13\x0D\xED\xF5\xF7e:\xBF\xAB \xDB\x10\x9B\x00\x00\x00' 

import zlib
d=zlib.decompressobj(16+zlib.MAX_WBITS) 
data=d.decompress(s)

统计服务器上的历史登录记录

last -ad | awk '{print $1}' | sort | uniq -c | sort -t$'\t' -k1,1 -nr 

linux文件格式转换

在linux下,不可避免的会用VIM打开一些windows下编辑过的文本文件。我们会发现文件的每行结尾都会有一个^M符号,这是因为DOS下的编辑器和Linux编辑器对文件行末的回车符处理不一致,
对于回车符的定义:

  • windows:0D0A
  • unix\linux: 0A
  • MAC: 0D
    去除这些符号的方法有:
  • vim下 :set fileformat=unix
  • 终端 dos2unix filename

git图形化提交历史

git log --pretty=format:"%h %an %s" --graph

echo 总结

  1. echo默认是带换行符做结尾的
  2. echo -n 可以去掉换行符
  3. printf是没有换行符结尾的
  4. tr可以删掉一个字符,如 tr -d ‘\n’

删除空行

  1. grep: grep -v ‘^$’ file
  2. sed: sed ‘/^$/d’ file 或 sed -n ‘/./p’ file
  3. awk: awk ‘/./ {print}’ file

shell读文件

读取 md5s 文件,对每行做处理。

cat md5s | while read line 
do 
     md5=$line 
     level2Path=`expr substr "$md5" 30 2` #50 
     level1Path=`expr substr "$md5" 32 1` #a 
     storagePath=hdfs:///ljp/apk/path/$level1Path/$level2Path/$md5 
     echo $storagePath
done 

什么是序列化

java 序列化是将对象转化为二进制流。不同的序列化框架会将对象转成不同的二进制流。通过 透过byte数组简单分析Java序列化、Kryo、ProtoBuf序列化 这篇文章里可以看到,不同的序列化框架最终转成的二进制流是不一样的。

Java 默认序列化

默认序列化机制

如果仅仅只是让某个类实现Serializable接口,而没有其它任何处理的话,则就是使用默认序列化机制。使用默认机制,在序列化对象时,不仅会序列化当前对象本身,还会对该对象引用的其它对象也进行序列化,同样地,这些其它对象引用的另外对象也将被序列化,以此类推。所以,如果一个对象包含的成员变量是容器类对象,而这些容器所含有的元素也是容器类对象,那么这个序列化的过程就会较复杂,开销也较大。

整个过程都是Java虚拟机(JVM)独立的,也就是说,在一个平台上序列化的对象可以在另一个完全不同的平台上反序列化该对象。

serialVersionUID

serialVersionUID的作用
不仅取决于类路径和功能代码是否一致,一个非常重要的一点是两个类的序列化 ID 是否一致(就是 private static final long serialVersionUID = 1L

Java 序列化实现

ObjectInputStream && ObjectOutputStream

类ObjectInputStream 和ObjectOutputStream是高层次的数据流,它们包含序列化和反序列化对象的方法。
ObjectOutputStream 类包含很多写方法来写各种数据类型,但是一个特别的方法例外:

public final void writeObject(Object x) throws IOException

上面的方法序列化一个对象,并将它发送到输出流。相似的ObjectInputStream 类包含如下反序列化一个对象的方法:

public final Object readObject() throws IOException, ClassNotFoundException

该方法从流中取出下一个对象,并将对象反序列化。它的返回值为Object,因此,你需要将它转换成合适的数据类型。

Serializable 接口

情境:一个子类实现了 Serializable 接口,它的父类都没有实现 Serializable 接口,序列化该子类对象,然后反序列化后输出父类定义的某变量的数值,该变量数值与序列化时的数值不同。
解决:要想将父类对象也序列化,就需要让父类也实现Serializable 接口。如果父类不实现的话的,就 需要有默认的无参的构造函数。在父类没有实现 Serializable 接口时,虚拟机是不会序列化父对象的,而一个 Java 对象的构造必须先有父对象,才有子对象,反序列化也不例外。所以反序列化时,为了构造父对象,只能调用父类的无参构造函数作为默认的父对象。因此当我们取父对象的变量值时,它的值是调用父类无参构造函数后的值。如果你考虑到这种序列化的情况,在父类无参构造函数中对变量进行初始化,否则的话,父类变量值都是默认声明的值,如 int 型的默认是 0,string 型的默认是 null。

Externalizable 接口

无论是使用transient关键字,还是使用writeObject()和readObject()方法,其实都是基于Serializable接口的序列化。JDK中提供了另一个序列化接口—Externalizable,使用该接口之后,之前基于Serializable接口的序列化机制就将失效。
writeExternal:把一个Java对象写入到流中
readExternal:从流中读取一个Java对象

java序列化一览

Java 序列化框架比较

性能比较

测试方法

jvm-serializers 提供了一个很好的比较各种Java序列化的的测试套件。 它罗列了各种序列化框架, 可以自动生成测试报告。

适用性比较

  • json
    json的序列化框架有fastjson,jackson,gson等。
    适用于数据量小,实时性较低(例如秒级别)的服务。JSON格式具有非常强的前后兼容性,并且调式方便,所以对客户端与服务端的通讯尤其适用。
  • xml
    xml的序列化框架有XStream。XML的序列化和反序列化的空间和时间开销都比较大,对于对性能要求在ms级别的服务,不推荐使用。
  • hessian
    hessian主要用于java序列化。它的实现机制是着重于数据,附带简单的类型信息的方法:
  • 对于简单的数据类型。就像Integer a = 1,hessian会序列化成I 1这样的流,I表示int or Integer,1就是数据内容。
    • 对于复杂对象,通过Java的反射机制,hessian把对象所有的属性当成一个Map来序列化,产生类似M className propertyName1 I 1 propertyName S stringValue
    • 对于引用对象,在序列化过程中,如果一个对象之前出现过,hessian会直接插入一个R index这样的块来表示一个引用位置,从而省去再次序列化和反序列化的时间。
  • thift
    Thrift是Facebook开源提供的一个高性能,轻量级RPC服务框架,其产生正是为了满足当前大数据量、分布式、跨语言、跨平台数据通讯的需求。 但是,Thrift并不仅仅是序列化协议,而是一个RPC框架。相对于JSON和XML而言,Thrift在空间开销和解析性能上有了比较大的提升,对于对性能要求比较高的分布式系统,它是一个优秀的RPC解决方案;但是由于Thrift的序列化被嵌入到Thrift框架里面,Thrift框架本身并没有透出序列化和反序列化接口,这导致其很难和其他传输层协议共同使用(例如HTTP)。
  • protobuf
    序列化数据非常简洁,紧凑,析速度非常快,提供了非常友好的动态库。使用简介,反序列化只需要一行代码。但是在JavaBean和proto之间的转换较麻烦。
  • avro
    Avro的产生解决了JSON的冗长和没有IDL的问题。 Avro提供两种序列化格式:JSON格式或者Binary格式。Binary格式在空间开销和解析性能方面可以和Protobuf媲美,JSON格式方便测试阶段的调试。
  • 动态类型:Avro并不需要生成代码,模式和数据存放在一起,而模式使得整个数据的处理过程并不生成代码、静态数据类型等等。这方便了数据处理系统和语言的构造。
    • 未标记的数据:由于读取数据的时候模式是已知的,那么需要和数据一起编码的类型信息就很少了,这样序列化的规模也就小了。
    • 不需要用户指定字段号:即使模式改变,处理数据时新旧模式都是已知的,所以通过使用字段名称可以解决差异问题。

Reference

https://www.ibm.com/developerworks/cn/java/j-lo-serial/
http://www.infoq.com/cn/articles/serialization-and-deserialization
http://sqtds.github.io/2015/05/13/2015/java-serizable/
http://www.solinx.co/archives/377