这是我在掘金翻译计划中的译文。 译文链接：[译] 动态规划算法的实际应用：接缝裁剪

• 原文地址：Real-world dynamic programming: seam carving
• 原文作者：Avik Das
• 译文出自：掘金翻译计划
• 本文永久链接：https://github.com/xitu/gold-miner/blob/master/TODO1/real-world-dynamic-programming-seam-carving.md
• 译者：nettee
• 校对者：JalanJiang，TokenJan

我们一直认为动态规划（dynamic programming）是一个在学校里学习的技术，并且只是用来通过软件公司的面试。实际上，这是因为大多数的开发者不会经常处理需要用到动态规划的问题。本质上，动态规划可以高效求解那些可以分解为高度重复子问题的问题，因此在很多场景下是很有用的。

在这篇文章中，我将会仔细分析动态规划的一个有趣的实际应用：接缝裁剪（seam carving）。Avidan 和 Shamir 的这篇文章 Seam Carving for Content-Aware Image Resizing 中详细讨论了这个问题以及提出的技术（搜索文章的标题可以免费获取）。

这篇文章是动态规划的系列文章中的一篇。如果你还不了解动态规划技术，请参阅我写的动态规划的图形化介绍。

环境敏感的图片大小调整

为了用动态规划解决实际问题，我们需要将问题建模为可以应用动态规划的形式。本节介绍了这个问题的必要的准备工作。

论文的原作者介绍了一种在智能考虑图片内容的情况下改变图片的宽度或高度的方法，叫做环境敏感的图片大小调整（content-aware image resizing）。后面会介绍论文的细节，但这里先做一个概述。假设你想调整下面这个冲浪者图片的大小。

论文中详细讨论了，有多种方法可以减少图片的宽度。我们最先想到的是裁剪和缩放，以及它们相关的缺点。删除图片中部的几列像素也是一种方法，但你也可以想象得到，这样会在图片中留下一条可见的分割线，左右的内容无法对齐。而且即使是这些方法全用上了，也只能删掉这么点图片：

前一阵子，收到烨兄的私聊，他突然要解决这样一个任务：

做如下格式的表达式转换：

• Multi(a, Multi(b, c)) --> a * (b * c)
• Divide(a, Sub(b, c)) --> a / (b - c)

支持的运算符有：

• Add: +
• Sub: -
• Multi: *
• Divide: /

而且好死不死的需要用他没怎么用过的 C++ 来写。我发现这是一个 parser 的问题，第一反应是推荐他用 flex/bison，但想到为了这么大点任务大费周章不太合适，又开始想手写这样一个表达式的 parser 难不难。最后得出的结论是，不难。

了解编译原理的人都知道什么是 parser。Parser 中文名（语法）分析器，是每个编译器的前端都会有的一个东西。不过，从编译原理的视角来看，“语言”的范畴要比我们理解的编程语言要广义得多，任何有一定规则的字符串构成方式，都可以看成是语言，例如上面的那个任务里用 Add、Sub 这样的函数描述的表达式。

那么，要解决上面这个任务，只需要对表达式的字符串进行语法分析，得到一个中间表示（一般是分析树或抽象语法树），再将中间表示输出为所需的格式即可。也就是说我们需要为表达式提供一个 parser，这个任务的任何解决方式，本质上都可以看成是写了一个 parser。

这是我在掘金翻译计划中的译文。 译文链接：[译] 分布式系统如何从故障中恢复？— 重试、超时和退避

• 原文地址：Retries, Timeouts and Backoff
• 原文作者：namc
• 译文出自：掘金翻译计划
• 本文永久链接：https://github.com/xitu/gold-miner/blob/master/TODO1/retries-timeouts-backoff.md
• 译者：nettee
• 校对者：fireairforce

分布式系统很难。即使我们学了很多构建高可用性系统的方法，也常常会忽略系统设计中的弹性（resiliency）。

我们肯定听说过容错性，但什么是“弹性”呢？个人而言，我喜欢将其定义为系统处理意外情况并最终从中恢复的能力。有很多方法使你的系统能从故障中回弹，但在这篇文章中，我们主要关注以下几点：

• 超时
• 重试
• 退避
• 分布式系统中的幂等性

超时

简单来说，超时就是两个连续的数据包之间的最大不活动时间。

假设我们在某个时刻已经使用过了数据库驱动和 HTTP 客户端。所有帮助你的服务连接到一个外部服务器的客户端或驱动都有 Timeout 参数。这个参数通常默认为零或 -1，表示超时时间未定义，或是无限时间。

例如：参考 connectTimeout 和 socketTimeout 的定义 Mysql Connector 配置

大多数对外部服务器的请求都附有一个超时时间。当外部服务器没有及时响应时，超时的设置非常有必要。如果没有设置超时，并使用默认值 0/-1，你的程序可能会阻塞几分钟或更长的时间。这是因为，当你没有收到来自应用服务器的响应，并且你的超时时间无限或非常大时，这个连接会一直开着。随着有更多的请求到来，更多的连接会打开，并永远无法关闭。这会导致你的连接池耗尽，进而导致你的应用的故障。

Monkey 是一个 Android 设备（模拟器或真实设备）上的一个程序，可以产生大量随机的用户输入事件，如点击、触摸、手势等。因此 Monkey 可用于 UI 上的压力测试。例如，下面的命令会启动一个特定的 app 并发送 500 个随机的事件：

1

adb shell monkey -p your.package.name -v 500

然而，Monkey 程序还有一个特殊的 --port 选项。当这个选项开启后，Monkey 会运行在 Automated Network Control 模式下，可以精确地向 app 发送一些 KeyEvent 和 MotionEvent。这也提供了一种在 adb shell input 命令之外，程序性地发送用户事件的方法。关于 adb shell input 命令，可以参考这里。经测试，Monkey 支持的用户事件比 input 命令的用户事件更细致一些。例如 input 命令对 swipe 动作只能指定滑动时间，但 Monkey 可以细致地指定滑动中的多次手指移动。

如果你有 AOSP 源代码，可以在 development/cmds/monkey/ 目录下找到 README.NETWORK.txt 文件，其中有说明 Automated Network Control 协议的简单文档。或者你可以访问这里。

下面简单概括一下文档内容：

建立连接

monkey --port 命令会让 monkey server 运行起来，并监听特定的端口：

1

adb shell monkey --port 1080

那么我在 host 机器上就可以通过 TCP 连接来向 monkey server 发送命令。注意 monkey server 只会绑定 localhost。TCP 协议是 ADB 支持的，因此需要设置端口转发：

1

adb forward tcp:1080 tcp:1080

这样就可以向 monkey server 发送命令了。

协议格式

不同的命令之间通过换行来分隔。对于正常完成的命令，monkey 会回复 OK；否则会回复 ERROR。如果命令有返回值，返回值会放在与 OK 或 ERROR 的同一行，以冒号分隔。ERROR 回复的返回值一般是错误消息。下面是一个请求-响应序列的例子：

1
2
3
4
5
6
7
8

key down menu
OK
touch monkey
ERROR: monkey not a number
getvar sdk
OK: donut
getvar foo
ERROR: no such var

最近在掘金翻译计划上参与翻译，这也是我第一次参与正式的开源项目。虽然这不是一个编程的项目，但也会使用 GitHub 的 issue / branch / pull request 这些工具来进行协作。我在一次更新分支的时候，push 了一些不必要的 commits。好在我仔细分析，然后在十分钟之内解决了问题。这是我第一次在正式的开源项目中遇到 Git 相关的挑战，想想也挺有趣的。在这里写篇文章记录一下。

首先介绍一下这个翻译项目的工作流程。项目的主分支是 master，当认领一篇文章进行翻译的时候，需要创建一个新分支 translate/file-name.md，翻译完成后需要创建一个 pull request 以供 review（也就是校对）。校对的主要过程是对 pull request 中内容进行评论。而校对之后，译者根据校对意见进行修改的时候，只需要直接提交到原分支，GitHub 就会自动将修改的内容同步到 pull request 中，非常方便。可以看到，整个项目其实和编程项目的工作方式类似，只不过你提交的不是源代码，而是翻译过的 markdown 文章。

漫不经心的错误

言归正传。我一共翻译了两篇文章，不妨称为 A 和 B。这样我就需要从 master 分支分出两个新分支：translate/A.md 和 translate/B.md。由于我两次翻译的间隔时间较短，在我创建分支 B 的时候，分支 A 还没有被 merge 到 master（这是重点）。也就是说，B 分支中的文件是没有我已翻译好的 A 文章的。

终于我的 B 文章也翻译完了，而且两位认真的校对者也在 pull request 中提出了自己的校对意见。我翻译文章 B 本来一直是在我的笔记本电脑上进行的。当我想要根据校对意见进行最后一次修改的时候，我突然决定直接在手边的台式机上干这些活！这当然是完全可以的，只是有点麻烦。我的台式机上有 translate/A.md 分支的所有内容，但很明显没有 translate/B.md 分支。于是我很自然地从 GitHub 上同步新的 B 分支：

1
2

git checkout -b translation/B.md
git pull origin translation/B.md

然而我犯了一个致命的错误，我本该从 master 分支上分出 B 分支的，但是我没有注意到当前分支是 A 分支。于是，我从 A 分支上分出了 B 分支！

这是我在掘金翻译计划中的译文。 译文链接：[译] 教程 - 用 C 写一个 Shell

• 原文地址：Tutorial - Write a Shell in C
• 原文作者：Stephen Brennan
• 译文出自：掘金翻译计划
• 本文永久链接：https://github.com/xitu/gold-miner/blob/master/TODO1/tutorial-write-a-shell-in-c.md
• 译者：nettee
• 校对者：kasheemlew，JackEggie

你很容易认为自己“不是一个真正的程序员”。有一些程序所有人都用，它们的开发者很容易被捧上神坛。虽然开发大型软件项目并不容易，但很多时候这种软件的基本思想都很简单。自己实现这样的软件是一种证明自己可以是真正的程序员的有趣方式。所以，这篇文章介绍了我是如何用 C 语言写一个自己的简易 Unix shell 的。我希望其他人也能感受到这种有趣的方式。

这篇文章中介绍的 shell（叫做 lsh），可以在 GitHub 上获取它的源代码。

学校里的学生请注意！ 许多课程都有要求你编写一个 shell 的作业，而且有些教师都知道这样的教程和代码。如果你是此类课程上的学生，请不要在未经允许的情况下复制（或复制加修改）这里的代码。我建议反对重度依赖本教程的行为。

Shell 的基本生命周期

让我们自顶向下地观察一个 shell。一个 shell 在它的生命周期中主要做三件事。

• 初始化：在这一步中，shell 一般会加载并执行它的配置文件。这些配置会改变 shell 的行为。
• 解释执行：接着，shell 会从标准输入（可能是交互式输入，也可能是一个文件）读取命令，并执行这些命令。
• 终止：当命令全部执行完毕，shell 会执行关闭命令，释放所有内存，然后终止。

Java 在多重继承上的设计甚至不如 C++。这个论点让人很难接受，毕竟我们在第一堂 Java 课上学到了：“Java 的优越性之一是摒除了 C++ 中易出错的多重继承”。然而，Java 的类单继承、接口多继承的设计，最终使 Java 走上了多重继承的老路，这最后一根稻草就是 Java 8 的 default 关键字。

Java 为什么设计成单继承

Java 语言在设计之初显然受到了 C++ 的很大影响。然而，Java 最终却没有采用 C++ 的多重继承方案。这是 Java 与 C++ 区分开的一个特点。在 Java 中，不允许“实现多继承”，即一个类不允许继承多个父类。但是 Java 允许“声明多继承”，即一个类可以实现多个接口，一个接口也可以继承多个父接口。由于接口只允许有方法声明而不允许有方法实现，这就避免了 C++ 中多继承的决议问题。

James Gosling 在设计 Java 的继承方案时，借鉴了 Objective-C 中的“纯接口”概念。他发现，没有实现体的纯接口避免了 C++ 中的很多歧义和坑。因此 Java 引入了 interface。

Java 8：default 关键字的引入

Java 8 这一版本可以说是 Java 5 之后一次最大的改动了。在全面引入了 lambda 和函数式编程之后，JDK 中的很多接口也需要升级，例如 Iterable.forEach:

1
2
3
4

 public interface Iterable<T> {
     Iterator<T> iterator();
+    void forEach(Consumer<? super T> action);
 }

然而，如果直接在 Iterable 接口中添加 forEach 方法。在 Java 7 及以前的所有实现 Iterable 的类都无法通过编译。为了向后兼容已有的代码，Java 8 引入了 default 关键字以及 default method，用来在接口中定义一个有方法体的方法。通过定义一个 default 的 forEach。所有实现了 Iterable 的类无需修改代码，便可在对象上调用 forEach。

1
2
3
4
5
6
7
8
9
10

public interface Iterable<T> {
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
}

default 与多重继承

此文翻译自 Will Crichton 的博客中 2018 年 9 月 9 日的一篇文章。

原文：What is Systems Programming, Really?

翻译者：nettee

译者前言：Go 语言诞生也将近十年了，但它的发展并没有很多人当时期望的那样如火如荼。按照 Go 是 “系统语言”的说法以及 Go 的语法设计，它似乎是以取代 C/C++ 为目标的。然而现如今 Go 没有撼动 C/C++ 一丝一毫的地位，倒是取代了一些 Python 在服务器端的工作。但 Go 语言的作者仍然坚称 Go 是“系统语言”。我们该如何看待“系统语言”这个术语？我们又该如何理解 Go 语言和最近流行的 Rust 语言的定位？我们究竟要不要学习它们？学习它们的什么地方？这篇文章梳理了程序语言的发展历史，能够给我们一个思路。

前言：我对“系统编程” (systems programming) 这个词不太满意。对我而言，它实际上把两个概念混为一谈：“底层编程”（关注机器的实现细节），以及“系统设计”（创建并管理一系列复杂的交互的组件）。为什么会这样？这种情况持续了多久？重新定义“系统”这个概念，我们会得到什么启发？

1970 年代：汇编之上的改进

让我们回到现代计算机系统诞生的时候，看看这个术语是如何改变的。我不知道是谁最先创造了这个词语，但我发现对于“计算机系统”的定义始于 70 年代初期。在 系统编程语言 (Bergeron et al. 1972) 中，作者写道：

系统软件是一些子软件的集合。这些子软件形成一个整体，超过部分之和，并使整体有相当大的规模和复杂性。典型的例子包括 multiprogramming、翻译、模拟、信息管理、time sharing 的系统。[…] 下面是系统软件的几个特性。系统软件不必包含所有的特性，而且一些特性也会出现在非系统软件中。

1. 需要解决的问题内涵广泛，由许多（而且常常是多种多样）的子问题组成。
2. 系统程序可能是用于支持其他的软件和应用程序，也可能本身就是一个完整的应用程序。
3. 它是为持续的“产业”使用而设计，而不是针对单个应用程序问题的一次性解决方案。
4. 它可以持续地演化，支持不同数量和种类的特性。
5. 系统程序无论是模块内还是模块间（即“通信”），都需要遵循一定的规则或结构。它常常是由多人设计并实现的。

这个定义还是比较合理的：计算机系统是大规模的、长期使用的、随时间变化的。然而，虽然定义中大部分是描述性的，有一个关键点却是限定性的：提倡区分底层语言和系统语言（在当时，也就是指区分汇编和 FORTRAN）。

系统编程语言的目标是可以在不过分关注底层细节的情况下使用，但编译得到的底层代码不会比直接手写的差。这种语言需要结合高级语言的简洁性和可读性，以及汇编语言的时间空间效率、深入机器和操作系统的能力。它应该能在不带来额外系统资源开销的前提下，尽量减少设计、编写、调试的时间。

与此同时，CMU 的研究人员发表了 BLISS: 一个系统编程语言 (Wulf et al. 1972)，将其描述为：

内存和资源管理是 C++ 最强的能力之一，也是 C++ 最复杂和最需要思考的地方。写 Java 的时候，我们只需要无脑地把所有对象都 new 出来。反正所有的对象只能放在堆区，又反正又垃圾回收器帮我们管理内存。然而，在 C++ 中，我们需要思考是把对象放在栈上，还是用 new 把对象放在堆上。默认情况下，对象会放在栈上，这样的好处是我们不会忘记释放对象的内存而造成内存泄漏。不过如果我们把一个大对象放在栈上，又将其作为参数或者返回值传递，就必须要考虑对象拷贝的开销了。C++ 由于和 C 兼容，默认情况下参数是按值传递 (call by value) 的，在传递参数和返回值的时候都会拷贝一遍对象。对于参数，我们尚可以将参数声明为引用类型 T& 来避免对象拷贝。而对于返回值的拷贝开销，则是不能声明为引用类型来解决的。

何时必须返回一个对象

假设我们想写一个 range 函数：

1
2
3
4
5
6
7

vector<int> range(int begin, int end, int step=1) {
    vector<int> res;
    for (int i = begin; i < end; i += step) {
        res.push_back(i);
    }
    return res;
}

这段代码会返回一个 vector<int> 对象，也就是我们不希望看到的：放在栈上的大对象。调用这个函数会产生返回值的临时对象，从而需要拷贝列表中的所有元素。很显然，你不能直接把返回值类型改成 vector<int>& 来避免对象拷贝——编译器会产生一个警告：warning: reference to local variable ‘res’ returned，你返回了一个临时变量的引用，这个引用指向了一个栈上的地址，而这个地址随时可能被回收。这也是 C++ 初学者容易犯的一个错误。既然不能返回一个引用，又想避免对象拷贝的开销，很多“老” C++ 程序员会进行一个人肉优化：把返回值作为引用参数传进去。按这种方法，range() 函数可以改写如下：

1
2
3
4
5
6
7
8
9

vector<int> range(vector<int>& out, int begin, int end, int step=1) {
    for (int i = begin; i < end; i += step) {
        out.push_back(i);
    }
}

// Caller
vector<int> r;
range(r, 0, 10);

C/C++ 程序员可能非常习惯这样写。然而，必须承认这是一个丑陋的写法。那么，直接返回一个 vector<int> 对象到底会怎么样呢？对象拷贝的开销能否避免？

临时对象与返回值优化

根据 《深度探索 C++ 对象模型》第 2.3 节 “程序转化语意学” (Program Transformation Semantics) 所述，函数的返回值会做如下转化：

1. 添加一个临时变量 __result
2. 当函数返回时，调用 __result 的 copy constructor，使用返回值 x 作为参数
3. （如果有的话）对 __result 进行后续操作

注意，后续操作中还能包括更多的 constructor，例如我们调用 range 函数以初始化变量 r1：

1
2

vector<int> r1;
r1 = range(1, 10); // 调用 r1 的 copy assignment operator (即 operator=)

可以看到，虽然只是简单的一次函数调用，临时对象就进行了两次拷贝。而 range 产生的数越多，需要拷贝的内容就越多，对性能的影响就越大。

为了解决这个问题，很多 C++ 编译器都实现了 返回值优化 (Return Value Optimization)，来消除返回值临时对象的多次拷贝。

本文翻译自 Eli Bendersky’s website。

原文：Understanding lvalues and rvalues in C and C++

翻译者：nettee

我们在 C/C++ 编程中并不会经常用到 左值 (lvalue) 和 右值 (rvalue) 两个术语。然而一旦遇见，又常常不清楚它们的含义。最可能出现两这个术语的地方是在编译错误或警告的信息中。例如，使用 gcc 编译以下代码时：

1
2
3
4
5
6
7
8

int foo() {return 2;}

int main()
{
    foo() = 2;

    return 0;
}

你会得到：

1
2

test.c: In function 'main':
test.c:8:5: error: lvalue required as left operand of assignment

没错，这个例子有点夸张，不像是你能写出来的代码。不过错误信息中提到了左值 (lvalue)。另一个例子是当你用 g++ 编译以下代码：

1
2
3
4

int& foo()
{
    return 2;
}

现在错误信息是：

1
2

testcpp.cpp: In function 'int& foo()':
testcpp.cpp:5:12: error: invalid initialization of non-const reference of type 'int&' from an rvalue of type 'int'

同样的，错误信息中提到了术语右值 (rvalue)。那么，在 C 和 C++ 中，左值 和 右值 到底是什么意思呢？我这篇文章将会详细解释。