Skip to content

Latest commit

 

History

History
475 lines (345 loc) · 15.6 KB

2018-11-14.md

File metadata and controls

475 lines (345 loc) · 15.6 KB

一. Algorithm

本次做的一道是栈相关的题目 682. Baseball Game，类似于经典的表达式计算，给一个字符串数组，如果是数字代表本次得分，此外还有三个符号:

  • C: 上次得分作废
  • D: 本次得分是上次得分的两倍
  • +: 本次得分是前两次得分之和

实现代码如下：

class Solution {
     private static final String OPS_REMOVE = "C";
    private static final String OPS_DOUBLE = "D";
    private static final String OPS_ADD = "+";

    public int calPoints(String[] ops) {

        Stack<Integer> points = this.getPoints(ops);
        int sum = 0;
        for (int num: points) {
            sum += num;
        }
        return sum;
    }

    public Stack<Integer> getPoints(String[] ops) {
        Stack<Integer> points = new Stack();

        int len = ops.length;
        for (int i = 0; i < len; i ++) {
            switch (ops[i]) {
                case OPS_REMOVE:
                    if (points.size() != 0) {
                        points.pop();
                    }
                    break;
                case OPS_DOUBLE:
                    if (points.size() != 0) {
                        Integer lastPoint = points.pop();
                        int newPoint = lastPoint.intValue() * 2;
                        points.push(lastPoint);
                        points.push(newPoint);
                    }
                    break;
                case OPS_ADD:
                    if (points.size() >= 2) {
                        Integer lastPoint = points.pop();
                        Integer lastLastPoint = points.pop();

                        int newPoint = lastPoint.intValue() + lastLastPoint.intValue();
                        points.push(lastLastPoint);
                        points.push(lastPoint);
                        points.push(newPoint);
                    }else if (points.size() == 1) {
                        Integer lastPoint = points.pop();
                        points.push(lastPoint);
                        points.push(lastPoint.intValue());

                    }
                    break;
                default:
                    String s = ops[i];
                    Integer newPoint = new Integer(s);
                    points.push(newPoint);
                    break;
            }
        }
        return points;

    }
    
}

题目本身不难，只要明白栈的用法并想清楚计算过程就可以了，因为要遍历，因此时间复杂度为 O(N)，另外实际执行的时候同样的代码执行效率分别为 12ms beats 10%, 11ms、5 ms beats 93%。也是醉了，可以看到 LeetCode 的代码执行测试也不是非常的精确，重点还是搞清楚算法的时空复杂度。

二. Review

本次 Review 读了一篇小短文 5 Reasons Why We switched from Python To Go。 作者简要介绍了自己从 Python 转向 Go 的原因。作者所在公司网站 TreeScale.com 主要技术栈如下:

  • React 作为前端技术栈
  • Django 作为后端框架
  • Node.js 提供 API 服务
  • PostgreSQL 作为数据库

当作者尝试将 API 服务和后端集成在同一个项目中时因为使用语言不同，导致各自做了很多相同的事情，并且集成时因为 Django 自身不支持太多的自定义开发，导致一些特殊和复杂的需求得不到解决，因此作者最终决定转向 Go 语言，然后给出了 5 点主要原因在，总结如下:

1. 编译型语言

Go 在使用时将基于操作系统和 CPU 架构的相关依赖全部用静态链接的方式编译进二进制文件，将编译好的二进制文件上传到服务器后就可以正常使用了，省去了很多安装环境和依赖的操作。

2. 强类型语言

虽然 Python 作为动态类型语言，提供了非常高的编程灵活性，但也会因为类型问题遇到很多意想不到的问题，尤其是在大型系统中，因为类型引发的问题往往不好定位。而 Go 语言的静态数据类型可以很好的避免这一点，提高程序的严谨性和健壮性。

3. 高性能

在实际使用中，尤其是高并发场景下，Go 语言的性能要比 Python 高并且消耗的资源比 Python 小，因为 Go 天生就是适合高并发的语言。

4. 无需学习新的 web 框架

Go 语言内置了大量的功能，比如 http、json、html templating 等，因此无需使用开发框架也可以完成一个完整的 web 服务，这大大降低了团队的技术负担。

5. 优秀的 IDE 工具与 Debug

IDEA 系列工具对 Go 语言提供了很好的支持，可以保证开发和调试效率。

以上就是作者提到的 5 点原因，还有一个重要原因是 Go 非常的易学，因此可以使我们快速上手开发。

最后，Go 越来越火了，是时候准备学习一波 Go 语言了。

三. Tip

本周 Tip 分享下 《Effective Python》 中提到的关于序列切片的用法。

在 Python 中，可以对 str、list、bytes 中进行切片操作，可以使我们非常方便的访问序列中的元素。

基本使用如下:

In [1]: a = [1,2,3,4]

In [2]: b = a[1:2]

In [3]: b
Out[3]: [2]

In [4]: c = a[1:4]

In [5]: c
Out[5]: [2, 3, 4]

可以看到基本语法就是:

somelist[start:end]

切片之后的结果包含 start 索引出的值而不包含 end 索引的值。

当我们从 0 处开始切片或者切片到最后一个元素时，可以省略 start 或者 end。示例如下:

In [7]: d
Out[7]: [1, 2, 3]

In [8]: e = a[1:]

In [9]: e
Out[9]: [2, 3, 4]

切片后得到的序列是一个新的序列，和原序列不是同一个对象，结合上面提到的省略 start、end 的做法，可以用如下方式快速复制一个序列:

In [10]: f = a[:]

In [11]: f
Out[11]: [1, 2, 3, 4]

另外需要注意的一点是切片不会引发索引越界异常，


In [12]: g = a[1:30]

In [13]: g
Out[13]: [2, 3, 4]

In [14]: g = a[-11:30]

In [15]: g
Out[15]: [1, 2, 3, 4]

四. Share

本次 Share 分享自己整理的一篇关于 ElasticSearch 查询机制笔记。

一. Query and Fetch

ES 查询过程可以分为 query 和 fetch 两个阶段。

1. query 阶段

当一个查询请求发送到 coordinating 节点后，该节点会首先进行 query 操作，具体步骤如下:

  • coordinating 节点在主副分片中随机选择包含所有数据的分片并向被选中的分片所在节点发送查询请求
  • 各个分片节点收到请求后执行具体的查询，返回 from + size 个文档 ID 及其相关性算分值
  • coordinating 节点拿到所有节点的数据，按照相关性算分或者指定的排序规则排序后拿到 from + size 个文档 ID

上面就是 query 阶段的主要操作，其实就是根据条件查询倒排索引获取文档 ID 的过程。拿到了文档 ID 就该根据 ID 获取到真正的数据了，这就是 fetch 阶段。

2. fetch 阶段
  • coordinating 节点通过 query 阶段获取对应的文档 ID 后，向分片发送 multi_get 请求
  • 各个分片接收到请求返回文档的具体数据
  • coordinating 节点拿到数据后进行拼接然后返回给客户端

这样我们知道 ES 是先将从各个分片查到一个较大的文档 ID 集合，执行一次筛选后在去查询具体的数据，因此如果要数据的数据量很大的话可能在 query 阶段会占用大量的内存，因此需要注意查询的数据量，后面分析 from + size 分页时在更详细的讲解。

二. 相关性算分

上面提到了，ES 对各个分片返回的文档 ID 默认按照相关性算分后排序后筛选 from + size 个文档 ID 然后获取数据，本节就看下什么是相关性算分。

相关性算分 (relevance) 指的是文档与查询语句的相关度，也可以理解为文档与查询条件的匹配度，文档与查询条件越匹配，则相关性算分越高

在对用户进行查询结果返回时，就是依据相关性算分进行排序的

1. 相关概念

关于相关性算分的计算，有如下几个概念:

  • Term Frequency（TF）词频，单词在文档中的出现次数，词频越高，相关度越高
  • Document Frencu（DF）文档频率，单词出现的文档数
  • Inverse Document Frequency (IDF)：逆向文档频率，1/DF
  • Field-length norm: 字段长度标准，文档越短，相关度越高
2. 相关性算分模型

ES 有两种计算相关性算分的算分 TF/DF 算法 与 5.x 后使用的 BM25 算法，下面简要介绍下这两种算分。

【1】TF/DF 算分模型

TF/DF 算分公式如下图: 图片

  • q 指的是查询条件，d 指的是某个文档。细节这里不做赘述，可以看到公式中有上面提到的 TF、DF、IDF 和 norm 值。

注意事项

  • ES 算分是按照 shard 进行的，即 shard 之间的算分是独立的

由于是分片独立的，所以可能出现文档其实匹配度并不相同，但相关性算分一致的情况，尤其是在文档数较少的时候。有两种解决方法:

  • 1 . 只使用一个分片。只有一个分片的话就不用担心这个问题了，但是存储容量和读写性能会受到很大影响
  • 2 . 使用 DFS query-then-fetch 方式查询，原理就是在所有分片查询完成后，在 coordinating 节点在进行一次相关性算分计算，当数据量比较大时比较消耗 CPU 和 内存资源，使用方式如下:
GET test_index/_search?search_type=dfs_query_then_fetch
{
  "explain": true,
  "query": {
    "match": {
      "name": "zyj"
    }
  }
}

相关性算分查询分析

ES 提供了 explain 参数，可以在查询结果中展示出相关性算分的计算过程，使用如下。

GET test_index/_search
{
  "explain": true,
  "query": {
    "match": {
      "name": "zyj"
    }
  }
}
【2】BM25 模型

BM25 模型是 5.x 之后的默认计算模型，是针对 TF/DF 算分模型的优化，可以简单理解为是迭代了 25 次才进行的计算。关于 BM25 算分可以参考这篇文章, 这里不作深入解析了。

三. ES 分页查询

ES 提供如下三种分页方式:

  • from/size
  • scroll
  • search_after
1. from/size

这是最常用的分页方案，from 指明开始位置，size 指明获取总数

GET test_index/_search
{
    "from": 1,
    "size": 10
}
深度分页问题

设想一下在一个分布式搜索引擎中如何获取前 990 到 1000 个文档呢？当我们执行 from=990, size=10 的查询时，ES 执行过程如下:

  • ES 从每个分片获取 前 1000 个文档 ID
  • 然后由 Coordinating 节点聚合所有结果，排序后选取前 1000 个文档,
  • 聚合完成后返回 from 到 from+size 位置的文档数据

由此我们知道无论查到第几页，ES 都会将分片上 1 ~ from +size 的数据查询出来，做聚合分析后在返回 from ~ from+size 个值。该过程非常占用内存，页数越深，处理文档越多，则耗时越长，为了避免深度分页，ES 通过下面参数设定最多查询 10000 条数据。

index.max_result_window

深度分页问题是搜索引擎无法绕过的问题，哪怕是 Google 也是默认只提供了 20 页的分页。毕竟对一个搜索引擎而言，重要的是获取与我们查询条件最贴切的数据，如果遍历了 20 页都没有符合条件的数据的话之后的数据基本不需要在遍历了。

2. scroll 查询

和 from + size 在内存中聚合数据的方式不同，scroll 快照的方式查询，这样可以避免深度分页的问题。但其也有如下缺点:

  • 因为使用快照，数据无法做到实时性查询
  • 使用稍微复杂

使用示例如下

1.执行 scroll 查询

首先执行一次 scroll 查询，指定查询的文档数和快照的有效时间

POST /test_index/_search?scroll=1m
{
    "size": 100,
    "query": {
        "match" : {
            "name" : "zyj"
        }
    }
}

scroll=1m 表示快照的有效时间，执行后返回结果如下:

{
  "_scroll_id": "DnF1ZXJ5VGhlbkZldGNoBQAAAAAABnZ0FjROUkgzZVVvVFUyYkJYX1lCTHpGN0EAAAAAAAml6hZkM3lHZkpucFFEdWhXd0xITzRvVTRRAAAAAAAGdnYWNE5SSDNlVW9UVTJiQlhfWUJMekY3QQAAAAAABnZ1FjROUkgzZVVvVFUyYkJYX1lCTHpGN0EAAAAAAAm5LBZhRGJlYUo4Q1RUQ0cyZ3VVMGlvZFdn",
  "took": 2,
  "timed_out": false,
  "_shards": {
    "total": 5,
    "successful": 5,
    "skipped": 0,
    "failed": 0
  },
  "hits": {
    "total": 1,
    "max_score": 0.2876821,
    "hits": [
      {
        "_index": "test_index",
        "_type": "doc",
        "_id": "1",
        "_score": 0.2876821,
        "_source": {
          "name": "zyj"
        }
      }
    ]
  }
}

可以看到上面返回了一个 scroll_id 的数据。

2. 拿到 scroll_id 继续查询

POST  /_search/scroll
{
    "scroll" : "1m",  # scroll 有效时长
    "scroll_id" : # 上一步返回的 scroll_id "DXF1ZXJ5QW5kRmV0Y2gBAAAAAAAAAD4WYm9laVYtZndUQlNsdDcwakFMNjU1QQ=="
}

返回结果

{
  "_scroll_id": "DnF1ZXJ5VGhlbkZldGNoBQAAAAAABnapFjROUkgzZVVvVFUyYkJYX1lCTHpGN0EAAAAAAAmmFxZkM3lHZkpucFFEdWhXd0xITzRvVTRRAAAAAAAGdqgWNE5SSDNlVW9UVTJiQlhfWUJMekY3QQAAAAAACaYWFmQzeUdmSm5wUUR1aFd3TEhPNG9VNFEAAAAAAAmmFRZkM3lHZkpucFFEdWhXd0xITzRvVTRR",
  "took": 10,
  "timed_out": false,
  "_shards": {
    "total": 5,
    "successful": 5,
    "skipped": 0,
    "failed": 0
  },
  "hits": {
    "total": 1,
    "max_score": 0.2876821,
    "hits": []
  }
}

其实就是不断根据上次返回的 scroll_id 拿下一页的数据，当返回的数据中 hits.hits 为空时就表示没有更多的数据了。

上面我们自行设置了快照的有效时间，但过多的 scroll 也会占用大量的内存，可以通过 clear api 主动删除，使用如下:

# 删除单个
DELETE /_search/scroll
{
    "scroll_id" : "DXF1ZXJ5QW5kRmV0Y2gBAAAAAAAAAD4WYm9laVYtZndUQlNsdDcwakFMNjU1QQ=="
}

# 删除多个
DELETE /_search/scroll
{
    "scroll_id" : [
      "DXF1ZXJ5QW5kRmV0Y2gBAAAAAAAAAD4WYm9laVYtZndUQlNsdDcwakFMNjU1QQ==",
      "DnF1ZXJ5VGhlbkZldGNoBQAAAAAAAAABFmtSWWRRWUJrU2o2ZExpSGJCVmQxYUEAAAAAAAAAAxZrUllkUVlCa1NqNmRMaUhiQlZkMWFBAAAAAAAAAAIWa1JZZFFZQmtTajZkTGlIYkJWZDFhQQAAAAAAAAAFFmtSWWRRWUJrU2o2ZExpSGJCVmQxYUEAAAAAAAAABBZrUllkUVlCa1NqNmRMaUhiQlZkMWFB"
    ]
}

# 删除所有
DELETE /_search/scroll/_all
3. search after

search after 可以提供实时的获取下一页文档的功能，其有如下特点:

  • 不能指定页数
  • 只能取下一页，不能上一页
  • 使用简单

具体使用步骤如下:

  • 1 . 指定排序值，并且保证值唯一，执行一次查询
GET test_index/_search
{
  "size": 1,
  "sort": {
    "name":"desc",
    "_id":"asc"
  }
}
  • 2 . 将上次查询的返回值加入到 search_after 中，然后获取下一页
GET test_index/_search
{
  "size": 1,
  "search_after": ["zyj", "1"],
  "sort": {
    "name":"desc",
    "_id":"asc"
  }
}

执行原理

  • 通过唯一的排序值定位文档，并返回指定 size 数目的文档

  • coordinating node 将这些数据排序后返回 size 即可

  • 因此每次都控制在 size * 分片数 的处理个数，但坏处就是不能查上一页，只能查下一页

  • 三种分页方式的比较

类型 使用场景
From/Size 需要实时获取顶部文档，并且要自由翻页时使用
Scroll 需要全部文档的时候，比如导出数据时
Search After 需要全部文档并且不需要自由翻页

以上就是 ES 的一些查询机制分析，欢迎拍砖指正。