Dimple在左耳听风ARTS打卡（十五）

程序员小跃

发布于 2019-12-27 15:00:47

4540

发布于 2019-12-27 15:00:47

文章被收录于专栏：程序员小跃程序员小跃

所谓ARTS：每周至少做一个LeetCode的算法题；阅读并点评至少一篇英文技术文章；学习至少一个技术技巧；分享一篇有观点和思考的技术文章。（也就是Algorithm、Review、Tip、Share 简称ARTS）这是第十五期打卡。

小编最近入手了粥左罗老师的21天写作课，收获满满，所以这次的ARTS打卡来晚了。在最近的几篇文章，基本上都会把学习写作课的心得或者经验发出来让大家看看，技术文，先缓缓哈。

Algorithm LeetCode算法

x的平方根 (https://leetcode-cn.com/problems/sqrtx/)

题目描述：实现 int sqrt(int x) 函数

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1：

输入: 4

输出: 2

示例 2：

输入: 8

输出: 2

说明：8的平方根是2.82842...，由于返回类型是整数，小数部分将被舍去

大家发现没有，其实LeetCode上很多题目，都是让你去实现一个现在有的API函数，印象中，这样的例子已经很多了。之前让你去查找字母的位置之类的，在Java中其实都是API实现的，现在让你自己实现，也是挺好的一件事。

所以，算法的练习，也是对API的更进一步的解释，为什么人家能当API，你自己的却不行，这就是需要我们深刻思考的问题，对吧。

就比如这题，你可以去看看Java的源代码找灵感，反正我的第一反应只有下面这个除法来做，当总是通不过，后来迫不得已，我看了一个大佬的解释，恍然大悟了已经。那我先把二分法拿出来分享，还有一个更厉害的，叫牛顿法。

以下部分参考了https://leetcode-cn.com/problems/sqrtx/solution/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/ 这个地址，如果有侵权，请及时和我联系哦。

class Solution {
    public int mySqrt(int x) {
        // 注意：针对特殊测试用例，例如 2147395599
        // 要把搜索的范围设置成长整型
        // 为了照顾到 0 把左边界设置为 0
        long l = 0;
        // # 为了照顾到 1 把右边界设置为 x // 2 + 1
        long r = x / 2 + 1;
        while (l < r) {
            // 注意：这里一定取右中位数，如果取左中位数，代码可能会进入死循环
            long mid = l + (r - l + 1) / 2;
            long square = mid * mid;
            if (square > x) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return (int) l;

    }
}

牛顿法，真的，小编学生时代没怎么认真学习，不知道有这个算法，所以这里也不好发表啥。我把题解拿出来给大家分享下。

使用牛顿法可以得到一个正实数的算术平方根，因为题目中说“结果只保留整数部分”，因此，我们把使用牛顿法得到的浮点数转换为整数即可。

这里给出牛顿法的思想：

在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 xx 轴的交点，重复这个过程直到收敛。

表示我已经没有任何发言权了，大家自己去看看牛顿法的牛逼之处吧。我这里仅提供代码和出处

class Solution {
    public int mySqrt(int x) {
        long y = x;
        while (y * y > x) {
            y = (y + x / y) / 2;
        }
        return (int) y;
    }
}

Review 阅读并点评至少一篇英文文章

Oculus founder : Silicon Valley firms should do more defense (https://mp.weixin.qq.com/s/tk6-30pNxfXTOEJD5AnPzQ)

这周开始，报名了粥左罗老师的21天学写作，这周是第一周，有点不太适应，所以看英文文档的时候，就选了一篇我之前关注的号主，相信也很多人认识他，就是飞总。

飞总也是极客时间的作者，现在在美帝工作，经常有英文让我们学习的，所以今天我放一篇出来。

这篇文章，讲的是一个有争议性的硅谷企业主，Oculus的创始人，Luckey，哈哈，这名字好吧。

这篇文章，是飞总让我们练习英语用的，我看了下，其实就是介绍了Luckey的一个访谈。Luckey成立了自己的国防公司，身体力行并呼吁更多的美国高科技公司和投资人进入国防领域，来填补一些空白，避免中国和俄罗斯在人工智能等领域获取更大的军事优势。

看完了感觉也像是一个传奇人物。我之前对马斯克很崇拜，现在对这位老哥也产生了敬畏之情，哈哈。

全文还是挺容易懂得，大家看看就好。

Tip 一个技术技巧

这次分享的是网络优化中的第二篇，关于复杂多变的移动网络该如何优化。

移动端优化

一个数据包从手机出发要经过无线网络、核心网络以及外部网络（互联网），才能达到我们的服务器。那整个网络请求的速度会跟哪些因素有关呢？

客户端网络库实现、服务器性能以及网络链路的质量都是影响网络请求速度的因素。下面我们先从客户端的网络库说过，看看应该如何进行网络优化。

何为网络优化

核心内容有以下三个：

速度：在网络正常或者良好的时候，怎样更好地利用带宽，进一步提升网络请求苏苏
弱网络：移动端网络复杂多变，在出现网络连接不稳定的时候，怎样最大程度保证网络的连通性
安全：网络安全不容忽视，怎样有效防止被第三方劫持、窃听甚至篡改

整个请求分为：发起请求、DNS解析、创建连接、发送数据包、接受数据包、关闭连接

请求的耗时可以细分到每一个步骤里

DNS解析
创建连接
发送/接收数据
关闭连接

所谓的网络优化，就是围绕速度、弱网络、安全这三个核心内容，减少每一个步骤的耗时，打造快速，稳定且安全的高质量网络

何为网络库

一个网络库的核心作用主要有以下三点：

统一编程接口。无论是同步还是异步请求，接口都非常简单易用。同时我们可以统一做策略管理，统一进行流解析（JSON、XML、Protocol Buffers）等
全局网络控制。在网络库内部我们可以做统一的网络调度、流量监控以及容灾管理等工作
高性能。既让我们把所有的网络请求都交给了网络库，那网络库是否实现高性能就至关重要。既然要实现高性能，那我会非常关注速度，CPU，内存，I/O使用，以及失败率、崩溃率、协议的兼容性等方面

高质量网络库

业内的蘑菇街、头条、UC浏览器都在Chromium网络库（Cronet）上做了二次开发，而微信Mars在弱网络方面做了方面做了大量优化，拼多多、虎牙、链家、美丽说这些应用都在使用Mars

大网络平台

网络优化不仅仅是客户端的事情，所以我们有了统一的网络中台，它负责提供前后一整套的网络解决方案。

阿里的ACCS、蚂蚁的mPaas、携程的网络服务都是公司级的网络中台服务，这样所有的网络优化可以让整个集团的所有接入应用收益。

HTTPDNS DNS的解析是我们网络请求的第一项工作，默认我们使用运营商的LocalDNS服务。

解析慢并不是默认LocalDNS最大的原罪，他还存在一些其他问题：

稳定性
准确性
及时性

连接复用
压缩与加密对于HTTP请求来说，数据主要包括三个部分：

请求URL
请求header
请求body

压缩算法的选择，通用的压缩算法主要是入gzip，Google的Brotli或者Facebook的Z-standard都是压缩率更高的算法。

对于特定数据我们还有其他的压缩方法，例如针对图片我们可以使用webp、hevc、SharpP等压缩率更高的格式。另一方面，基于AI的图片超清化(http://imgtec.eetrend.com/d6-imgtec/blog/2017-08/10143.html) 也是一大神器，QQ空间通过这个技术节约了大量的带宽成本

安全

HTTPS的优化有下面几个思路：

连接复用率。通过多个域名公用同一个HTTP/2连接、长连接等方式提升连接复用率
减少握手次数。TLS 1.3可以实现0-RTT协商，事实上在TLS 1.3 release之前，微信的mmtls、Facebook的fizz、阿里的SlightSSL都已在企业内部大规模部署
性能提升。使用ecc证书代替RSA，服务端签名的性能可以提升4-10倍，但是客户端校验性能低了约20倍，从10微妙级降低到100微妙级。