ARTS-for-week12

阅读文本大概需要 10 分钟。

每周完成一个 ARTS

Algorithm 来源 LeetCode 15. 3Sum

Review 阅读了关于 Go 语言官方文档中 FAQ 的部分内容

Tip 总结最近项目中出现的问题

Share 分享一篇【ELK 笔记】如何快速搭建一个 ELK 日志分析平台。

下面更新 ARTS 第 十二 周的内容。

1.Algorithm

LeetCode 15. 3Sum难度：[Medium]

【题意】

Given an arrayofnintegers, are there elementsa,b,cinsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.

Note:The solution set must not contain duplicate triplets.

Example：

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1,0,1],

[-1,-1,2

]

【思路】

先固定第一个数，然后采用双指针法

这里注意养成一个好习惯，在开始写代码前，务必考虑代码的鲁棒性！

注意后台测试样例有可能出现下面这种情况

Input[0,0,0,0]

expect output[[0,0,0]]

1. 我们对原数组进行排序，然后开始遍历排序后的数组。这里我们可以先做个剪枝优化，就是当遍历到正数的时候就 break，为啥呢，因为我们的数组现在是有序的了，如果第一个要固定的数就是正数了，那么后面的数字就都是正数，就永远不会出现和为0的情况了。

2. 然后我们还要处理重复出现的情况，处理方法是从第二个数开始，如果和前面的数字相等，就跳过，因为不能把相同的数字 固定两次。对于遍历到的数，用 0 减去当前这个固定的数得到一个 target，然后只需要再之后找到两个数之和等于 target 即可。

3. 我们用两个指针分别指向固定数字之后开始的数组首尾两个数，如果两个数和正好为 target，则将这两个数和固定的数一起存入结果中。然后就是继续处理重复的步骤了，两个指针都需要检测重复数字。如果两数之和小于 target，则我们将左边那个指针右移一位，使得指向的数字增大，同理，如果两数之和大于 target，则我们将右边那个指针左移一位，使得指向的数字减小

时间复杂度 O（n^2），空间复杂度 O（n^2）。

【参考代码】

/*

Author: rongweihe

Time: 2019-01-04

*/

class Solution {

public:

vector> threeSum(vector& nums) {

vector> ret;

sort(nums.begin(),nums.end());//排序

if(nums.empty() || nums.front()>|| nums.back()

for(intk=; k

if(nums[k] >)break;// 剪枝，排完序，若当前数非负，则 break

if( k>&& nums[k]==nums[k-1])continue;

inti=k+1;//枚举第二个数

intj=nums.size()-1;//枚举第三个数

inttarget=-nums[k];//第二个数与第三个数之和

while(i

if(nums[i]+nums[j]==target){//如果三数为0判断结果

ret.push_back();

while(i

while(i

++i,--j;

}

elseif(nums[i]+nums[j]

elseif(nums[i]+nums[j] > target) {--j;}//如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小

}

}

returnret;

}

};

当然，我们还可以利用 set 的去重特点，也就是不能包含重复项来防止重复项的产生，那么我们就不需要检测数字是否被固定过两次。参照上面的代码稍微改一下就可以，这里就不贴了。

2.Review

本次 Review 阅读了关于 Go 语言官方文档中 FAQ 的 起源内容: Frequently Asked Questions (FAQ)（英文）。将其中几个有意思的问题整理了一下。

起源

1 这个项目目的何在？

非系统底层语言的出现已经有十多年的时间, 而在这期间，计算机编程环境已经发生了巨大变化。以下是几大发展趋势:

1. 计算机的运算速度有了极大提升， 但是软件开发效率没有明显的提高。

2. 依赖管理是今天软件开发一个重要部分, 但像 C 语言中的 “header files” 阻碍了简单的依赖分析和快速的编译。

3. 与类似 Java, C++ 等带有重类型系统的语言相比, 弱类型语言编程的兴起促使越来越多的开发者使用诸如 Python 或 JavaScript 这些动态类型语言来进行编程

4. 像垃圾回收和并行计算这些基础概念在当前流行的系统语言中并没有得到很好的支持。

5. 多核计算机的出现引起了更多的担忧和疑惑。

我们相信值得去尝试开发一种支持并发、垃圾回收并且能被快速编译的新语言。对于以上的几点:

1. 能够在一台单机上快速编译(如几秒内)的一个大项目。

2. Go 提供了这样一个软件开发模型: 使依赖分析更简单, 而避免了类似 C 那样在文件和库上使用依赖的不便。

3. Go 的类型系统没有层次结构, 所有没有把时间花在定义类型关系上。同样, 虽然Go有静态类型, 它也尽量使类型显得更加轻量(相对于其他经典 Object-Oriented 语言来说)。

4. Go 提供了完整的垃圾回收机制, 并且在并发执行和通讯方面提供了基础支持。

5. 基于自身设计, Go 在多核机器上的软件系统的构建给出了方案。

关于这个问题，更详细和有价值的答案可以参考这篇文章 Go at Google: Language Design in the Service of Software Engineering。

2 这个项目的历史?

Robert Griesemer, Rob Pike 和 Ken Thompson 在 2007 年 9 月份变开始在白板上描绘一个新语言的目标，很快目标便被敲定，而该语言有了最初的轮廓，并且在大家的业余努力下渐进发展。

到了 2008 年 1 月份, Ken 开始着手设计输出结果为 C 语言的编译器，用以探索思路。

到了年中，Go 已经成为一个全职项目，并且有充足准备来开发其编译器。

在 2008 年 5 月，Ian Taylor 使用一份规范草案独立地为 Go 启动了 GCC 前端工作(In May 2008, Ian Taylor independently started on a GCC front end for Go using the draft specification???)

而后半年加入的 Russ Cox, 通过原型开始实现 Go 的语言规则及一些基础库。

Go 在 2009/11/10 时成为一个开源项目。之后经过几年的积极发展, 在 2012/3/28 这天 Go1.0 稳定版本正式发布。该版本包含了语言规范、标准库、 常用工具库, 为创建可靠的企业项目提供了基础。

有了稳定的基础, 我们使用 Go 来开发程序,工具以及一些项目。 而不是频繁的更换语言或者库。

实际上 Go1.0 版本的目标是提供长期稳定的开发环境。Go1.0 版本上的任何更改都是向后兼容的。我们要清楚将来的 Go应该发展成什么样子，而不只是修改了版本号。

当然, Go 会不断改进, 但方向侧重在性能, 可靠性, 可移植性以及一些新功能的开发， 比如完善国际化支持。

将来可能有 Go 2 版本, 不过目前几年主要是发展 Go1.0 版本(译注: 截止目前, 最新为Go 1.11.4（2018年12月15日）正式发布)。

Go 在 2009-11-10 正式成为一个开源项目。社区中的众多开发者贡献了非常多的建设性建议及讨论, 还有相应的代码。

3 为什么要创建一门新语言?

Go 之所以诞生, 是对现有语言和系统编程环境不满的一种驱动释然。

编程变得如此困难, 而语言的选择也变得越加迷茫。

高效编译, 高效执行, 易于编程这三个目标在同一个主流语言中往往不可同时兼得。

开发者被动选择了动态类型语言(如 Python/JavaScript )以进行安全有效的开发，而不是 C++ 或 Java。

Go 尝试既做到解析型、动态类型语言那样易于开发，也做到静态、编译语言一样高效安全，同样它侧重支持网络及多核编程。

最后还有一个设计目标， 希望Go来加速编译: 在单台机器上最多需要几秒钟时间来完成一个大项目的编译流程。要达到这些目标，需要解决大量这样的问题: 一个富于表达而且轻巧的类型系统；并发和垃圾回收等等。现有的库或者工具并不能很好的解决这些问题, 因此新的语言应运而生。

Go at Google阐述了 Go 语言诞生的背景以及动机，通过它可以找到更多有关这个问题的答案。

4 Go 语言的基础设计原则?

Go 尝试减少输入的代码数量； 通过它的设计, 尝试减少混乱和复杂度。

在 Go 中，没有前置声明和头文件；所有对象/变量都是只声明一次；初始化方式易读, 自动化而且易用；语法干净, 关键字轻量；可以使用 := (声明并定义)的结构来简化普通表达式: foo.Foo* myFoo = new(foo.Foo)。而最基本的 Go 的类型没有层次结构，也就不需要声明类型之间的关系。这种简化机制使得 Go 轻松做到富于表达,易于理解。

另外一个重要的原则是保持概念正交。可以实现任何类型的方法； 结构体用来表示数据而接口用来表示抽象；等等。正交性使得组合操作时更容易清楚其中发生了什么。

先整理这么多吧，毕竟也是初学者，等在深入学习下后在回头来看

三 Tip

记录一下最近项目中遇到的问题。

项目背景：Linux 环境下 服务端和客户端建立连接，进行 UDP 通信，需要发送报文，处理报文。

要求：一个服务端要同时相应多个客户端。

同一台 IP 机子上同时开启两个或多个客户端和服务器端进行 UDP 通信。

当一个客户端和服务端建立一次连接之后，准备相应的播放数据完毕之后，还未开始正常回放数据前。此时在同一台机子上启动另一个客户端时，第一个客户端就崩溃。

分析与排查：

首先我们想到的是端口占用的问题，是不是多个客户端和服务端进行通信的时候端口冲突了，但是我们很快又怀疑起了我们这种想法，如果是端口占用的问题，第一个客户端会因为端口占用会收不到服务端发送的命令而不应该出现崩溃这种现象，我们又很快的想到了在第二个客户端建立连接之后，按正常情况来说，服务端会返回给客户端一个反馈命令和连接 ID，这个连接 ID 是服务端唯一识别客户端的凭证，也是客户端跟服务端进行通信的唯一标识。连接 ID 随着客户端的连接数增加而增加，会不会是服务端在最后一次客户端建立连接之后会给所有已经建立连接的客户端发送最后一次连接的 ID，比如说第一个客户端建立连接时 连接ID 为 0，第二个客户端建立连接时 连接 ID 为 1，但是此时服务端会在第二个客户端建立连接之后不仅会给第二个客户端反馈 连接 ID 1同时也会给第一个客户端反馈连接 ID 1，但是第一个客户端的连接 ID 是 0。为了验证我们的想法，我们立即开始调试代码，在服务端的代码和客户端的代码分别设置断点，在调试的过程中我们发现第二个客户端与服务端建立连接之后，服务端会同时给两个客户端反馈命令，而且由于第一个客户端连接之后连接 ID 已经为 0 ，第二次服务端又传过来一个连接 ID 1 会更新之前的 ID，这样一来，在操作连接的相关数据结构的时候访问下标就会越界从而出现崩溃现象！，但是发现还没止步，我们接着在服务端调试代码发现每次发送的目的端口居然是随机的，奇怪的是两个客户端居然都收到了反馈命令！

初步猜想：UDP 通信是不可靠连接。在下图我们可以看到，UDP 通信客户端和服务端并没有建立连接而只是发送和接受数据，初步猜想，因为这两个客户端是同一个 IP，所以服务端在反馈命令的时候,服务端会给同一 IP 的客户端都返回命令，并且端口设置好像并没有什么用。

先暂时记录这么多，下次深入研究下回头再更新下。

四 Share

ELK笔记 中文

分享一篇【ELK笔记】如何快速搭建一个ELK日志分析平台。