Skip to content

Latest commit

 

History

History
253 lines (164 loc) · 10.7 KB

2019-05-22.md

File metadata and controls

253 lines (164 loc) · 10.7 KB

一. Algorithm

继续做买卖股票的题目，这次是123. Best Time to Buy and Sell Stock III，这也是比较难的一道了，题目也是要求买卖股票的最大利润，但是交易次数最多为两次。

首先想到的就是分治求解了，第一道题目中我们已经完成了求一个区间中只交易一次的最大收益，这道题就是从 0 开始，每次都将数据分成两个区间，分别求最大值后相加即可，实现代码如下：

public class Solution {
    
    public int maxProfit(int[] prices) {

        int len = prices.length;
        if (len <= 1) {
            return 0;
        }

        int result = 0;

        for (int i = 1; i < len; i ++) {
            if (i == (len-1)) {
                 result = Math.max(result, getProfit(prices, 0, i));
            }else {
                result = Math.max(result, getProfit(prices, 0, i) + getProfit(prices, i+1, len-1));
            }
            

        }

        return result;

    }

    // 买卖股票第一题中已经实现的算法
    public int getProfit(int[] prices, int start, int end) {
        int result = 0;

        int lowestPrice = prices[start];

        for (int i = start+1; i <= end; i ++) {
            if (prices[i] > lowestPrice) {
                result = Math.max(result, prices[i] - lowestPrice);
            }else {
                lowestPrice = prices[i];
            }
        }
        return result;

    }
}

通过分治的方法计算，时间复杂度为 O(N^2)，效率是比较低的，因此需要进一步的优化。

第二种解法是看了 discuss 部分学到的一种比较取巧的解法，因为最多交易两次，因此遍历到任意一天时都会存在四种状态

  • 第一次买入
  • 第一次卖出
  • 第二次买入
  • 第二次卖出

那么我们要做的就是每次遍历求这四个状态时的最大受益值，最终返回 sell2 即为最大收益，实现代码如下：

public class Solution {
    
    public int maxProfit(int[] prices) {

     int len = prices.length;
        if (len <= 1) {
            return 0;
        }

        // 开始计算 sell 的值其实是没有买入情况的，因此设置起始值为无限小
        // 为 0 的话那么最开始的 sell 计算就会等于遍历到的值，出现没有买入就有收益的情况。
        int buy1 = Integer.MIN_VALUE;
        int buy2 = Integer.MIN_VALUE;

        int sell1 = 0;
        int sell2 = 0;

        for (int i = 0; i < len; i++) {

            // sell2 的利润等于 buy2 + 当前值。即后一次的操作要依赖前一次操作的值
            // 因此计算顺序依次为 sell2、buy2、sell1、buy1。
            sell2 = Math.max(sell2, buy2 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
                
            sell1 =Math.max(sell1, buy1 + prices[i]);
            buy1 = Math.max(buy1, -prices[i]);

        }

        return sell2;
    }   
}

这样遍历依次就可以求出最大收益值，时间复杂度为 O(N)。

二. Review

读了一篇 ES 相关的文章：Elasticsearch Best Practices and Increasing Performance，文章介绍了一些 ES 的最佳实践，下面是简单的总结：

1. 始终定义 Mapping

MySQL 在存储数据之前必须要先定义表，而 ES 不同，其存储数据不需要事先定义索引的数据结构，其会根据存储的数据自动生成 Mapping，但这样也会造成问题，当某个字段数据发生变化时可能导致报错，示例如下：

{
  "id" : 1,
  "title" : "Install ElasticSearch on Ubuntu",
  "link" : "https://linuxhint.com/install-elasticsearch-ubuntu/",
  "date" : "2018-03-25"
}

我们先存入了一段数据，ES 会自动生成 Mapping，此时 date 字段的数据类型的 date 日期类型，后面在写入下面数据：

{
  "id" : 1,
  "title" : "ES Best Practices and Performance",
  "date" : "Pending"
}

这时候因为 date 已经是日期类型了，写入字符串就会报错。

在实际工作中使用时更建议的一种方式是，

首先构建一条正确的数据写入 ES，然后拿到其自动生成的 Mapping，在此基础之上根据需要做合适的修正，并且对每个索引的 Mapping 加上版本控制。

2. 为集群添加生产标识与合适的数据恢复设置

ES 的默认集群名称是 elasticsearch，在实际使用中我们可能会有多个集群，此时针对每个集群起针对性的名字可以使我们更方便的维护集群，例如

cluster.name: app_es_production
node.name: app_es_node_001

节点的恢复设置对于集群中的数据恢复和同步至关重要，我们集群中因为节点故障或者其他原因导致节点重启时，必须要保证 ES 集群中节点数据的一致性，可以通过 ES 的 local gateway 模块来进行合理的配置，示例如下：

gateway.recover_after_nodes: 10
gateway.expected_nodes: 20
gateway.recover_after_time: 7m

详细信息可以参阅 ES 文档Local Gateway。通过合适的恢复设置，可以将原本可能需要花费数小时的数据恢复缩短到分钟级别。

3. 关闭内存交换

当内存不够时，Linux 可能将一部分硬盘当做内存来使用，但是硬盘的读写速度远远低于内存，这样做会严重影响 ES 的性能，因此始终建议 ES 禁止内存交换，配置如下：

ES 5.0+ 版本配置：

bootstrap.memory_lock: true

较低版本配置

bootstrap.mlockall: true

ES 的搜索需要占用大量的内存，因此一开始就应该提供足够的内存，而不应该使用交换内存。

4. 尽可能少的更新 Mapping

Mapping 的更新会影响集群的性能，当我们无法预估影响大小时，可能进行如下配置：

indices.cluster.send_refresh_mapping: false

当更新 Mapping 的请求还在等待 master 节点处理时，此时如果向数据节点发送了旧的 Mapping 结构的数据，那么稍后必须将更新 Mapping 的请求发到所有数据节点，这会影响 ES 的性能。当上面的配置设置为 false 时 master 将不会发送请求。

5. 优化线程池

ES 内部维护了较多的线程池来改进节点内线程的管理方式，每个线程所处理的数据量是有限制的，可以通过如下配置进行设置：

threadpool.bulk.queue_size: 2000

当没有可用线程时，该配置指定了队列中可以等待被执行的请求数量，如果等待执行的请求数超过该设置，则会触发 RemoteTransportException 异常。值越高，说明可等待执行的请求数越多，那么内存占用也会越高。另外当异常发生时我们需要做好异常处理工作。

三. Tips

本周使用 Python requests 库通过 https 请求又拍云图片时报错：

SSLError: HTTPSConnectionPool(host='xxx.xxx', port=443): Max retries exceeded with url: /fc31518057ee674ee6df30dfcfb3cac4 (Caused by SSLError(CertificateError("hostname 'xxx.cn' doesn't match '*.xx.upaiyun.com'",),))

搜索了一下发现很多人都遇到过这个问题，就是 SSL 证书验证失败。有下面几种解决方案。

1. 方案一：跳过校验

算是一种最野路子的解决方式，代码如下：

url = "https://xxx.xxx"
requests.get(url,verify=False)

这并不是根本解决方案，但是当服务出现问题并且无法快速定位到原因时时可以先通过该方式及时的恢复服务，保证服务的可用性，后续再从根本上解决问题。

2. 方案二：升级 Python 或者安装库

这个问题非常常见以至于 requests 的官方文档中给出了解释：

"hostname doesn't match" 错误是怎么回事？ 当 SSL certificate verification 发现服务器响应的认证和它认为自己连接的主机名不匹配时，就会发生这样的错误。如果你确定服务器的 SSL 设置是正确的（例如你可以用浏览器访问页面）> ，而且你使用的是 Python 2.6 或者 2.7，那么一个可能的解释就是你需要 Server-Name-Indication。

Server-Name-Indication 简称 SNI，是一个 SSL 的官方扩展，其中客户端会告诉服务器它连接了哪个主机名。当服务器使用虚拟主机（ Virtual Hosting）时这点很重要。这样的服务器会服> 务多个 SSL 网站，所以它们需要能够针对客户端连接的主机名返回正确的证书。

Python 3 和 Python 2.7.9+ 的 SSL 模块包含了原生的 SNI 支持。更多关于在 Request、SNI 以及 Python < 2.7.9 的信息请参见这个 Stack Overflow 答案。

结合文档和 Stack Overflow 中的答案，引发该问题的原因有两个：

  • Python 版本过低
  • 缺少库

因此解决方案也就有如下两种：

  • 升级 Python 版本，这是最根本的解决方式
  • 如果你的 Python 版本低于 Python 2.7.9+ 并且因为某些原因不能升级的话，那么就需要安装下面两个库：
pip install pyopenssl
pip install idna

安装后就可以正常访问了。

四. Share

最近读采铜老师的《精进》一书，里面提到我们现代人很容易陷入一种对于未来的焦虑之中，这种焦虑大多数情况下不仅不会改变未来的情况，反而会忽视掉当下，而为了克服这种焦虑感，采铜老师提出的建议是：

至少在你全情投入的这一刻，不要去想未来会怎么样，不要去想这件事的最终结果会如何。

自己对于这种充满焦虑的、老是惦记未来会怎样的感受有过非常深刻的经历，大学的时候在图书馆刷做高数题的时候，包括这两年在做算法题的时候这种想法都会时不时的冒出来：

我做这个会有什么用呢？

在这个想法的驱使下，本来可以学好的知识，本来可以更加优化的算法题也就没有下文了。与没有继续深入钻研导致没有学到知识相比更可怕的是，这种想法会让自己很容易养成凡事差不多得了的坏习惯，凡事不再拼尽全力做到最好，进而丧失了更进一步的可能性。

行为养成习惯,习惯形成性格,性格决定命运。虽然一个人命运并不完全由性格决定（毕竟还要看历史进程），但一个人的性格极大程度上决定了其行事的方式，而行事的方式反过来也会影响其性格。因此最好行事的方式就是当决定要做一件事情的时候就要拼尽全力做到最好，不要过多的瞻前顾后，更不能抱着差不多就行了的态度敷衍了事。