1. Algorithm: 每周至少做一个 LeetCode 的算法题

题目

206. Reverse Linked List



Reverse a singly linked list.



Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:



A linked list can be reversed either iteratively or recursively. Could you implement both?



自定义链表

为了打印链表信息，笔者组装了链表



package common;
public class ListNode {
    public int val;
    public  ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    static public ListNode listNodeWithIntArray(int[] input) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i: input) {
            ListNode newNode = new ListNode(i);
            node.next = newNode;
            node = node.next;
        }
        return head.next;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode node = this;
        while (node != null) {
            sb.append(node.val).append("-->");
            node = node.next;
        }
        return sb.append("Null").toString();
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        return false;
    }
}



1. 迭代解决（顺序思维，人类思维）

假设我们有链表1 → 2 → 3 → Ø，我们想将其更改为Ø ← 1 ← 2 ← 3。



在遍历列表时，更改当前节点的下一个指针以指向其上一个元素。由于一个节点没有对其先前节点的引用，因此必须预先存储其先前元素。在更改引用之前，您还需要另一个指针来存储下一个节点。不要忘了最后返回新的主要参考！



复杂度分析



时间复杂度： 上）O （n ）。假使，假设ññ 是列表的长度，时间复杂度是 上）O （n ）。



空间复杂度： O（1）O （1 ）。



package linkedlist;
import common.ListNode;
// https://leetcode.com/problems/reverse-linked-list/
public class ReverseLinkedList {
  public ListNode reverseList(ListNode head) {
    // check edge
    if (head == null || head.next == null) {
      return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    slow.next = null;
    ListNode temp;
    while (fast != null) {
      temp = fast.next;
      fast.next = slow;
      slow = fast;
      fast = temp;
    }
    return slow;
  }
}



2. 递归解决（逆向思维，机器思维）

就是把上面的while 循环部分，改为递归实现.

递归注意先写退出条件：if (fast == null) return slow;.



package linkedlist;
import common.ListNode;
// https://leetcode.com/problems/reverse-linked-list/
public class ReverseLinkedList {
  public ListNode reverseListWithRecursive(ListNode head) {
    // check edge
    if (head == null || head.next == null) {
      return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    slow.next = null;
    return reverseList(fast, slow);
  }
  private ListNode reverseList(ListNode fast, ListNode slow) {
    if (fast == null) {
      return slow;
    }
    ListNode temp = fast.next;
    fast.next = slow;
    slow = fast;
    fast = temp;
    return reverseList(fast, slow);
  }
}



3. 递归实现 （不需要辅助方法）

递归版本有些棘手，关键是向后工作。假设列表的其余部分已经被撤消，那么我该如何撤回前面的部分？假设列表为：n1 → … → nk-1 → nk → nk+1 → … → nm → Ø



假设从节点n k + 1到n m已反转，并且您在节点n k处。



n1 → … → nk-1 → nk → nk+1 ← … ← nm



我们希望n k + 1的下一个节点指向n k。



所以，



nk.next.next = nk;



要非常小心，n 1的下一个必须指向Ø。如果您忘记了这一点，则您的链表中会有一个循环。如果您使用大小为2的链表测试代码，则可能会捕获此错误。



复杂度分析



时间复杂度： 上）O （n ）。假使，假设ññ 是列表的长度，时间复杂度是 上）O （n ）。



空间复杂度： 上）O （n ）。由于递归，额外的空间来自隐式堆栈空间。递归可以上升到ññ 水平深。



package linkedlist;
import common.ListNode;
// https://leetcode.com/problems/reverse-linked-list/
public class ReverseLinkedList {
  public ListNode reverseListWithRecursiveClean(ListNode head) {
    // check edge
    if (head == null || head.next == null) {
      return head;
    }
    ListNode result = reverseListWithRecursiveClean(head.next);
    head.next.next = head;
    head.next = null;
    return result;
  }
  public static void main(String[] args) {
    ReverseLinkedList obj = new ReverseLinkedList();
    int[] input = {1, 2, 3, 4, 5};
    ListNode head = ListNode.listNodeWithIntArray(input);
    System.out.println("init ListNode");
    System.out.println(head.toString());
    //ListNode result = obj.reverseList(head);
    //ListNode result = obj.reverseListWithRecursive(head);
    ListNode result = obj.reverseListWithRecursiveClean(head);
    System.out.println("result ListNode");
    System.out.println(result.toString());
  }
}



4. 最终结果打印输出



package linkedlist;
import common.ListNode;
// https://leetcode.com/problems/reverse-linked-list/
public class ReverseLinkedList {
  public static void main(String[] args) {
    ReverseLinkedList obj = new ReverseLinkedList();
    int[] input = {1, 2, 3, 4, 5};
    ListNode head = ListNode.listNodeWithIntArray(input);
    System.out.println("init ListNode");
    System.out.println(head.toString());
    //ListNode result = obj.reverseList(head);
    //ListNode result = obj.reverseListWithRecursive(head);
    ListNode result = obj.reverseListWithRecursiveClean(head);
    System.out.println("result ListNode");
    System.out.println(result.toString());
  }
}



控制台输出

init ListNode
1-->2-->3-->4-->5-->Null
result ListNode
5-->4-->3-->2-->1-->Null



2. Review: 阅读并点评至少一篇英文技术文章



谷歌大脑团队：重新思考计算机视觉预训练和自我训练的

https://arxiv.org/pdf/2006.06882.pdf



这篇论文描述了机器学习视觉训练，对数据的人工标注，使信息丢失，虽然训练出的模型速度比较快，但是效果会有误差。没有人工标注的信息量更大，而且能够做实验证实，人工标注后得到的模型并非永远最佳。



3. Tips: 学习至少一个技术技巧

笔者写的博客：



翻译：在Mac上将Python 3设置为默认的正确和错误方法

说明

弃用：Python 2.7将于2020年1月1日到期，请升级您的Python，因为在此日期后将不再维护Python 2.7。pip的未来版本将不再支持Python 2.7。



对于新买的Mac Book Pro来说，默认的安装是 Python 2.7的版本。如何设置默认的版本为Python 3 呢？



这有什么难的？

macOS随附的Python版本与Python建议用于开发的版本已经过时。正如XKCD指出的那样，Python运行时有时也具有可笑的挑战。

那有什么计划？我的计算机上已经有数十个Python解释器，而且我不知道如何有效地管理它们。我不想下载最新版本，将其移到我的路径中，然后每天称呼它（或使用brew install python3，它会执行类似的操作）。我认为这会以一种非常令人沮丧的方式导致线路中断，我不知道如何进行故障排除。我认为最好的方法是淘汰并替换我正在运行的任何版本的Python，以明确，明确地切换到最新和最伟大的版本。



我们可以做（但不应该做）

现在我们知道了不该做的事情，让我们看一下我们可以做的事情。当我们考虑macOS上应用程序的常见安装模式时，有两种选择。



使用Python 3作为macOS默认设置

Python的网站上有一个macOS Python 3安装程序，我们可以下载和使用。如果使用软件包安装，则/usr/local/bin/中将提供python3填充。



别名是必须的，因为不能更改/ usr / bin /中存储的Python二进制文件。别名的好处是它特定于我们的命令行外壳。由于默认情况下使用zsh，因此将以下内容放入.zshrc文件中：



$ echo "alias python=/usr/local/bin/python3.7" >> ~/.zshrc
$ source ~/.zshrc



如果您使用默认的Bash shell，则可以将此相同的文本附加到.bashrc中：



$ echo "alias python=/usr/local/bin/python3.7" >> ~/.bashrc
$ source ~/.bashrc



查看 Python版本

$ python --verions
# python 3.7.1



该策略有效，但是对于将来对Python进行更新并不是理想的选择。这意味着我们必须记住要检查网站并下载新文件，因为Python不包含用于更新的命令行方式。



让Homebrew管理Python 3

该Homebrew提供适用于MacOS，许多人依靠免费和开源的包管理器。它赋予Apple用户类似于apt-get或yum的功能。如果您是Homebrew用户，则可能已经安装了Python。要快速检查，请运行：



$ brew list | grep python
python

如果Python在命令下显示，则表明已安装。它是什么版本？让我们检查：



$ brew info python
python: stable 3.7.3 (bottled), HEAD
Interpreted, interactive, object-oriented programming language
https://www.python.org/
/usr/local/Cellar/python/3.7.2_1 (8,437 files, 118MB) *
## further output not included ##

好，太棒了！Homebrew维护人员已将默认的Python瓶更新为指向最新版本。由于Homebrew维护者比我们大多数人更依赖于更新发行版，因此我们可以通过以下命令使用Homebrew的Python 3版本：



$ brew update && brew upgrade python

现在，我们要将别名（从上面）指向Homebrew管理的Python副本：



# If you added the previous alias, use a text editor to update the line to the following
alias python=/usr/local/bin/python3

为了确保上面的路径指向Homebrew在我们的环境中安装Python的位置，我们可以运行brew info python并查找路径信息。



这种使用Homebrew管理我们的Python环境的方法是一个很好的起点，在当时对我来说是有意义的。



如果我们仍然需要Python 2怎么办？

对于Python的新手来说，从Python 3开始是有意义的。但是，我们仍然需要Python 2的人（例如，为仅在Python 2中可用的Python项目做出贡献）可以继续使用可用的默认macOS Python二进制文件在/usr/bin/python中：



$ /usr/bin/python
>>> print("This runtime still works!")
This runtime still works!

Homebrew非常棒，甚至为Python 2提供了不同的公式：



# If you need Homebrew's Python 2.7 run
$ brew install python@2

在任何时候，我们都可以从外壳程序的配置文件中删除别名，以使用系统上的默认Python副本返回。



不要忘记将pip更新为pip3！

该PIP命令是Python包专门默认的包管理器。尽管我们将默认的Python命令更改为版本3，但如果它在以前的版本中，我们必须单独为pip命令添加别名。首先，我们需要检查使用的版本：



# Note that this is a capital V (not lowercase)
$ pip -V
pip 19.0.3 from /Library/Python/2.7/site-packages/pip-19.0.3-py2.7.egg/pip (python 2.7)

为确保我们安装的软件包与我们新版本的Python兼容，我们将使用另一个别名来指向pip的兼容版本。由于在这种情况下我们将Homebrew用作软件包管理器，因此我们在安装Python 3时便知道它已安装pip3。默认路径应与Python 3相同，但是我们可以通过要求Shell找到它来确认它：



$ which pip3
/usr/local/bin/pip3

现在我们知道了位置，我们将像以前一样将其添加到shell配置文件中：



$ echo "alias pip=/usr/local/bin/pip3" >> ~/.zshrc 
# or for Bash
$ echo "alias pip=/usr/local/bin/pip3" >> ~/.bashrc

最后，我们可以通过打开新的shell或重置当前的shell并查看指向的内容来确认运行中的pip指向pip3：



# This command reloads the current shell without exiting the session
# Alternatively, exit the shell and start a new one
$ exec $0
# Now we can look to see where pip points us
$ which pip
pip: aliased to /usr/local/bin/pip3



我们可以避免使用Homebrew更新pip，但这需要Python文档中更长的教程。



我们应该怎么做

当要求对本文进行技术审查时，Moshe Zadka向我警告说，我的解决方案可能导致运行哪个Python的想法不可靠，而该想法过于依赖于shell加载别名。我知道Moshe熟悉Python，但我不知道他是许多 Python教程的作者，还是即将出版的有关macOS上Python开发的书。他遵循一项核心原则，帮助40位同事在macOS系统上安全，一致地开发Python：

“所有Python开发的基本前提是永远不要使用系统Python。您不希望 Mac OS X的'默认Python'是'python3'。您永远不必关心默认的Python。”



我们如何停止关心默认值？Moshe建议使用pyenv来管理Python环境（要进一步了解pyenv的配置，[请参阅本文](https://opensource.com/article/19/6/virtual-environments-python-macos)）。该工具将管理Python的多个版本，并被描述为“简单，易懂且遵循Unix的一站式工具的传统”。



尽管提供了其他安装选项，但最简单的入门方法是使用Homebrew：



$ brew install pyenv
🍺  /usr/local/Cellar/pyenv/1.2.10: 634 files, 2.4MB

现在，让我们安装最新的Python版本（截至撰写本文时为3.7.3）：



$ pyenv install 3.7.3
python-build: use openssl 1.0 from homebrew
python-build: use readline from homebrew
Downloading Python-3.7.3.tar.xz...
-> https://www.python.org/ftp/python/3.7.3/Python-3.7.3.tar.xz
Installing Python-3.7.3...
## further output not included ##

现在已经通过pyenv安装了Python 3，我们希望将其设置为pyenv环境的全局默认版本：



$ pyenv global 3.7.3
# and verify it worked
$ pyenv version
3.7.3 (set by /Users/mbbroberg/.pyenv/version)

pyenv的力量来自对外壳路径的控制。为了使其正常工作，我们需要将以下添加到我们的配置文件（.zshrc对我来说，可能的.bash_profile）：



$ echo -e 'if command -v pyenv 1>/dev/null 2>&1; then\n  eval "$(pyenv init -)"\nfi' >> ~/.zshrc

该命令后，我们的dotfile（.zshrc为zsh中或.bash_profile中的Bash的）应该包括这些行：



if command -v pyenv 1>/dev/null 2>&1; then
  eval "$(pyenv init -)"
fi

我们还需要删除在以上各节中使用的别名， 因为它们会阻止正确使用pyenv。删除它们后，我们可以确认pyenv正在管理我们的Python 3版本：

I start by resetting the current shell

Alternatively, start a new terminal instance



$ exec $0
$ which python
/Users/mbbroberg/.pyenv/shims/python
$ python -V
Python 3.7.3
$ pip -V
pip 19.0.3 from /Users/mbbroberg/.pyenv/versions/3.7.3/lib/python3.7/site-packages/pip (python 3.7)

现在我们可以确定我们正在使用Python 3.7.3，并且pip会与之一起更新，而无需在版本之间进行任何手动别名。使用Moshe的建议来使用版本管理器（pyenv），使我们能够轻松地接受将来的升级，而不必对我们在给定时间运行的Python感到困惑。



接下来配置Python

熟悉此工作流程后，您可以使用pyenv来管理Python的多个版本。对于依赖关系管理，使用虚拟环境也是必不可少的。我在文章中提到了如何使用内置的[venv](https://docs.python.org/3/library/venv.html)库，Moshe建议使用 [virtualenvwrapper来管理虚拟环境](https://opensource.com/article/19/6/python-virtual-environments-mac)。



从一开始就做

如果您刚刚开始在macOS上进行Python开发，请进行必要的配置，以确保从一开始就使用正确的Python版本。安装Python 3（带或不带Homebrew）以及使用别名可以让您开始编码，但是从长远来看，这并不是一个好的策略。使用pyenv作为简单的版本管理解决方案，可以让您顺利开始。



参考

https://opensource.com/article/19/5/python-3-default-mac



4. Share: 分享一篇有观点和思考的技术文章

笔者写的博客链接



极客大学架构师训练营 大数据架构、Spark、Storm、Spark Streaming、Flink、HiBench、Impala 第25课 听课总结



说明

讲师：首席架构师 李智慧



Spark

Spark 生态体系

Spark vs Hadoop

Spark 特点（Spark 为什么更快）

1. DAG (Directed Acyclic Graph)有向无环图 切分的多阶段计算过程更快速；

2. 使用内存存储中间计算结果更高效；

3. RDD (Resilient Distributed Datasets) 的编程模型更简单。



Spark WordCount 编程示例

// 根据 HDFS 路径生成一个输入数据 RDD。
val textFile = sc.textFile("hdfs://...")
// 在输入数据 RDD上执行3个操作，得到一个新的 RDD。  
val counts = textFile.flatMap(line => line.split(" ")) // 1. 将输入数据的每一行文本用空格拆分成单词
						.map(word => (word, 1)) // 2. 将每个单词进行转换，word => (word, 1), 生成的结构。
						.reduceByKey(_ + _) // 3. 相同的 Key 进行统计，统计方式是对 Value 求和，(_ + _).
counts.saveAsTextFile("hdfs://...") // 将这个 RDD 保存到 HDFS



Shuffle 把相同的Key进行汇集，由Spark的执行引擎调用 reduceByKey，。

大数据关键的点就在于 Shaffle，把相关联的数据进行汇集。



作为编程模型的 弹性分布式数据集RDD (Resilient Distributed Datasets)

RDD 是 Spark 的核心概念，是弹性分布式数据集（Resilient Distributed Datasets）的缩写。RDD 既是 Spark 面向开发者的编程模型，又是 Spark 自身架构的核心元素。



作为 Spark 编程模型的 RDD。 我们知道，大数据计算就是在大规模的数据集上进行一系列的数据计算处理。MapReduce 针对输入数据，将计算过程分为两个阶段，一个 Map 阶段，一个 Reduce 阶段，可以理解成是面向过程的大数据计算。我们在用 MapReduce 编程的时候，思考的是，如何将计算逻辑用 Map 和 Reduce 两个阶段实现， map 和 reduce 函数的输入和输出是什么，MapReduce是面向过程的。



而 Spark 则直接针对数据进行编程，将大规模数据集合抽象成一个 RDD 对象，然后在这个 RDD 上进行各种计算处理，得到一个新的 RDD，继续计算处理，直到得到最后的结果数据。所以 Spark 可以理解成是面向对象的大数据计算。我们在进行 Spark 编程的时候，思考的是一个 RDD 对象需要经过什么样的操作，转换成另一个 RDD 对象，思考的重心和落脚点都在 RDD 上。



WordCount 程序 RDD 分析

WordCount 的代码示例里，第 2 行代码实际上进行了 3 次 RDD 转换，每次转换都得到一个新的 RDD，因为新的 RDD 可以继续调用 RDD 的转换函数，所以连续写成一行代码。事实上，可以分成 3 行。

val rdd1 = textFile.flatMap(line => line.split(" "))
var rdd2 = rdd1.map(word => (word, 1))
var rdd3 = rdd2.reduceByKey(_ + _)



RDD 上定义的函数分两种，一种是转换（transformation）函数，这种函数的返回值还是 RDD；另一种是执行（action）函数，这种函数不再返回 RDD.



RDD 定义了很多转换操作函数，比如有计算 map(func)、过滤 filter(func)、合并数据集 union(otherDataset)、根据 Key 聚合 reduceByKey(func, [numPartitions])、连接数据集 join(otherDataset, [numPartitions])、分组 groupByKey([numPartitions]) 等十几个函数。



作为数据分片的 RDD

跟 MapReduce 一样，Spark 也是对大数据进行分片计算，Spark 分布式计算的数据分片、任务调度都是以 RDD 为单位展开的，每个 RDD 分片都会分配到一个执行进程去处理。



RDD 上的转换操作又分成两种，一种转换操作产生的 RDD 不会出现新的分片，比如 map、filter等，也就是说一个 RDD 数据分片，经过 map 或者 filter 转换操作后，结果还在当前分片。就像你用 map 函数对每个数据加 1，得到的还是这样一组数据，只是值不同。实际上，Spark 并不是按照代码写的操作顺序去生成 RDD，比如 rdd2 = rdd1.map(func).



这样的代码并不会在物理上生成一个新的 RDD。物理上，Spark 只有在产生新的 RDD 分片的时候，才会真的生成一个RDD，Spark 的这种特性也被称作惰性计算。



另一种转换操作产生的 RDD 则会产生新的分片，比如 reduceByKey，来自不同分片的相同 Key 必须聚合在一起进行操作，这样就会产生新的 RDD 分片。然而，实际实际执行过程中，是否会产生新的 RDD 分片，并不是根据转换函数名就能判断出来的。

Spark 的计算阶段：DAG (Directed Acyclic Graph)有向无环图

和 MapReduce 一个应用一次只运行一个 map 和一个 reduce 不同，Spark 可以更加应用的复杂程度，分割成更多的计算阶段（stage），这些计算阶段组成一个有向无环图 DAG，Spark 任务调度器可以根据 DAG 的依赖关系执行计算阶段。

这个 DAG 对应的 Spark 程序伪代码如下：

rddB = rddA.groupBy(key)
rddD = rddC.map(func)
rddF = rddD.union(rddE)
rddG = rddB.join(rddF)



整个应用被切分成 3 个阶段，阶段 3 需要依赖阶段 1 和阶段 2，阶段 1 和阶段 2 互不依赖。Spark 在执行调度的时候，先执行阶段 1 和阶段 2，完成以后，再执行阶段 3. 如果有更多的阶段，Spark 的策略也是一样的。只有根据程序初始化好 DAG，就建立了依赖关系，然后根据依赖关系顺序执行各个计算阶段，Spark 大数据应用的计算就完成了。



Spark 作业调度执行的核心是 DAG，有了 DAG，整个应用就被切分成哪些阶段，每个阶段的依赖关系也就清楚了。之后再根据每个阶段要处理的数据量生成相应的任务集合（TaskSet），每个任务都分配一个任务进程去处理，Spark 就实现了大数据的分布式计算。



负责 Spark 应用 DAG 生成和管理的组件是 DAGScheduler，DAGScheduler 根据程序代码生成 DAG，然后将程序分发到分布式计算集群，按计算阶段的先后关系调度执行。



那么 Spark 划分计算阶段的依据是什么呢？显然并不是 RDD 上的每个转换函数都会生成一个计算阶段，比如上面的例子有 4 个转换函数，但是只有 3 个阶段。



当 RDD 之间的转换连接线呈现多对多交叉连接的时候，就会产生新的阶段。一个 RDD 代表一个数据集，图中每个 RDD 里面都包含多个小块，每个小块代表 RDD 的一个分片。

Spark 也需要通过 shuffle 将数据进行重新组合，相同 Key 的数据放在一起，进行聚合、关联等操作，因而每次 shuffle 都产生新的计算阶段。这也是为什么计算阶段会有依赖关系，它需要的数据来源于前面一个或多个计算阶段产生的数据，必须等到前面的阶段执行完毕才能进行 shuffle，并得到数据。



计算阶段划分的依据是 shuffle，不是转换函数的类型，有的函数有时候又 shuffle，有时候没有。例子中 RDD B 和 RDD F 进行 join，得到 RDD G，这里的 RDD F 需要进行shuffle，RDD B 就不需要。

Spark 的作业管理

Spark 里面的 RDD 函数有两种，一种是转换函数，调用以后得到的还是一个 RDD，RDD 的计算逻辑主要通过转换函数完成。



另一种 action 函数，调用以后不再返回 RDD。 比如 count() 函数，返回 RDD 中数据的元素个数；saveAsTextFile(path), 将 RDD 数据存储到 path 路径下。Spark 的 DAGScheduler 在遇到 shuffle 的时候，会生成一个计算阶段，在遇到 action 函数的时候，会生成一个作业 (job)。



RDD 里面的每个数据分片，Spark 都会创建一个计算任务去处理，所以一个计算阶段会包含很多个计算任务 (task)。



Spark 的执行过程

Spark 支持 Standalone、Yarn、Mesos、Kubernetes 等多种部署方案，几种部署方案原理也都一样，只是不同组件角色命名不同，但是核心功能和运行流程都差不多。

首先，Spark 应用程序启动在自己的 JVM 进程里，即 Driver 进程，启动后调用 SparkContext 初始化执行配置和输入数据。SparkContext 启动 DAGScheduler 构造执行的 DAG 图，切分成最小的执行单元也就是计算任务。



然后 Driver 向 Cluster Manager 请求计算资源，用于 DAG 的分布式计算。Cluster Manager 收到请求以后，将 Driver 的主机地址等信息通知给集群的所有计算节点 Worker。



Worker 收到信息以后，根据 Driver 的主机地址，跟 Driver 通信并注册，然后根据自己的空闲资源向 Driver 通报自己可以领用的任务数。 Driver 根据 DAG 图开始向注册的 Worker 分配任务。



Worker 收到任务后，启动 Executor 进程开始执行任务。Executor 先检查自己是否有 Driver 的执行代码，如果没有， 从 Driver 下载执行代码，通过 Java 反射加载后开始执行。