Fork me on GitHub

ARTS(6)

Posted on | Edited on | In | Views:

ARTS 第六周

每周完成一个ARTS（也就是 Algorithm、Review、Tip、Share 简称ARTS）：

  1. 每周至少做一个 leetcode 的算法题
  2. 阅读并点评至少一篇英文技术文章
  3. 学习至少一个技术技巧
  4. 分享一篇有观点和思考的技术文章。

Algorithm

力扣 541. 反转字符串 II

给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。

示例:

1
2
输入: s = "abcdefg", k = 2
输出: "bacdfeg"

要求:

  1. 该字符串只包含小写的英文字母。
  2. 给定字符串的长度和 k 在[1, 10000]范围内。
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

import org.junit.Test;

public class 反转字符串 {

	@Test
	public void getResult() {
		String s = "abcdefg";
		String result = reverseStr(s, 3);
		System.out.println(result);
	}

	public String reverseStr(String s, int k) {
		String ans = "";
		ans = reverseAll(s, ans, k);
		return ans;
	}

	private String reverseAll(String s, String ans, int k) {
		if (s == null || s.length() == 0) {
			return s;
		}
		int n = s.length();
		while (n >= k) {
			ans += reverse(s, k);
			if (n <= 2 * k) {
				ans += s.substring(k);
				break;
			} else {
				ans += s.substring(k, 2 * k);
			}
			s = s.substring(2 * k);
			n = s.length();
		}
		if (n < k) {
			ans += reverse(s, n);
		}
		return ans;
	}

	private String reverse(String s, int k) {
		String reverseStr = "";
		for (int i = k - 1; i >= 0; --i) {
			reverseStr += s.substring(i, i + 1);
		}
		return reverseStr;
	}
}

Review

英文原文：What are the advantages of DAG execution of big data algorithms over MapReduce?

引申文章：What are the Apache Spark concepts around its DAG execution engine, and its overall architecture? Spark 中的 DAG 引擎：

两篇文章主要讲了 DAG 算法在 Hadoop、Spark、Storm 中的应用。

总结：

  1. 简介 MapReduce，以及不使用 DAG 可能出现的后果：
    1. MapReduce 的工作分为三步：① 从 HDFS 中读取数据；② 进行 Map 和 Reduce 操作；③ 计算结果写回 HDFS。
    2. 每个 MapReduce 相互独立，Hadoop 也不论多个 MapReduce 的先后顺序。
    3. 存在浪费 HDFS 的情况：若两个 MapReduce 的数据读取相互无关，那么使用 HDFS 就是对磁盘的浪费。
    4. 存在耗时长的情况：稍微复杂的计算可能需要大量的时间，即使数据量很少的情况，因为有些操作需要等上一步全部完成后，才开始执行。
  2. DAG （有向无环图）不是 MapReduce 专属，它的应用要更广泛一些。
  3. 在处理多 jobs 时（让它们 serialize 或 parallelize 时），DAG 是很合适的。
  4. 在 Spark 中，DAG 发挥着同样重要的作用，相比之下，Hadoop 在使用时存在严重的磁盘负担(Spark 是依赖内存的)。
    1. Spark RDD 是只读可分区的分布式数据集，是 Spark 中的重要概念。
    2. 在 Spark 中，Spark RDD 被DAG scheduler划分为多个 stages（比如map操作会被放进一个 stage 中），每个 stage 被分为多个 tasks。
    3. 不同的 stages 会经由cluster manager交付给Task Scheduler，但这些 stages 的依赖关系对于Task Scheduler是透明度。
    4. Spark 使用”连续计算的方式”，对任务的执行进行了优化（主要是手动调整了 MapReduce 任务的执行步骤），尽量减少移动数据的次数。
    5. RDD transformation函数能分为 narrow transformation 跟wide transformation两种用法。前者不需要跨 stage 移动数据(比如 map(),filter())，后者则可能需要跨 stage(比如reduceByKey())。
      1. RDD transformation的意思就是在一些 RDD 中执行一些数据操作，来产生一个或多个新的 RDD。
      2. 每个 RDD 都会维护一个指向parent RDD的指针，比如 b=a.map()，b 就会指向 a。
  5. Storm 在某一确定时刻只处理少量数据，DAG 在其中使代码模块化，避免大量的 if-else 语句。

Tip

今天分享一下手机上的”训练”功能，省时省心。

小米手机上一般使用小爱同学只能够查天气、定闹钟以及简单的打开 app 的功能，一旦想实现一些比较高级的操作比如：打开虾米音乐我的收藏中随机播放歌曲，就需要用到”训练”功能了。

做法：添加一些语音激活关键词，然后把我的个人操作进行录屏。以后只需要向小爱同学发出指令，小爱同学会自动完成剩下的操作。

最佳实践：播放第三方 app 上的音乐、keep 跑步、查看淘宝快递、各种 app 的每日签到等。

Share

本周分享的是位图这种数据结构的特性，文章在本站另一处，点击查看：

BitMap 特性解读

-------------The End-------------