ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

Algorithm

本周的算法题是 LeetCode 683 K个空花盆。

这道题最简洁的方法就是用双指针。实现比较简单，但是理解起来不太容易。核心思路就是翻转 bulbs 的映射到 花盆->开花天数 的 days. 题目要求的「他们中间间隔了 k 朵花并且都没有开放」等价于 days[i] 和 days[i+K+1] 中间的所有有的 days[x] 都比 days[i] 和 days[i+K+1] 大，也就是开花时间比两侧 days[i] 和 days[i+K+1] 都晚，这样就能保证 days[i] 和 days[i+K+1] 中间有 K 个花盆没开花.

func kEmptySlots(bulbs []int, K int) int {
    if len(bulbs) == 0 {
        return -1
    }
    days := make([]int, len(bulbs))
    for i, n := range bulbs {
        days[n-1] = i
    }

    ans, left, right := 1<<31-1, 0, K+1
    for right < len(days) {
        breakFlag := false
        for i := left+1; i < right; i++ {
            if days[i] < days[left] || days[i] < days[right] {
                left, right = i, i+K+1
                breakFlag = true
                break
            }
        }
        if ! breakFlag {
            ans = min(ans, max(days[left], days[right]))
            left, right = right, right+K+1
        }
    }
    if ans == 1<<31-1 {
        return -1
    }
    return ans+1
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Review 文章推荐

本周的英文文章是 Redis 官方的 Redis Persistence，主要介绍 Redis 持久化。

• RDB 和 AOF
  RDB 文件保存的是 Redis 数据的快照，AOF 文件保存的是每次数据发生变化时的写入操作。AOF 可以粗浅的理解成保存了已执行的「命令」，这些「命令」会在 Redis 服务启动的时候进行重放。Redis 的持久化是可选项，可以选择不进行持久化，也可以选择同时使用 RDB 和 AOF 两种文件。
• RDB 优劣
  快照式的 RDB 对于存储和传输大段时间的数据更友好。
  数据量比较大时，服务器的启动速度方面，使用 RDB 作为持久化方案比使用 AOF 表现更好。
  因为制作快照需要设定时间间隔，所以如果发生故障，一定会损失一个时间间隔内的数据。
  RDB 文件加载到内存需要 Redis 服务 fork 一个子进程来完成，数量非常大的极端情况下可能占用过多的 CPU 而影响正常服务响应速度。
• AOF 优劣
  更加灵活（比如很短）的持久化数据间隔，可以降低故障发生时数据损失，比如每秒甚至每次执行命令追加 AOF.
  append only的方式不需要seek, 写入故障更容易处理。
  如果 AOF 文件过大，Redis 可以对文件进行「化简」，抛弃冗余的操作记录。
  AOF 保留了相当好的可读性。
  AOF 通常比 RDB 文件要大。
• 官方对于两种持久化方式的建议
  只用一种的话，最好用 RDB.

Tip 编程技巧

• 可能引起索引失效的用法
  使用范围查询，例如 id < 10
  对联合索引使用 like + %blabla 进行模糊匹配
  使用 or 连接两个条件

可能引起索引失效的场景：所有对字段使用函数，类型转换，前置模糊匹配（like "%blabla" ），where子句的多条件组合不当（比如使用了 or, 或者对联合索引中的非结尾字段使用了范围查找，比如 id < 10）。
ps 后置模糊匹配（like "blabla%"）可以使用前缀索引。

Share 灵光一闪

人以群分的本质是否就是「鄙视链」构建起来的认同感？

本周阅读列表

• Optimizing OR (union) operations in MySQL
  文章比较详细的介绍了一次使用 inner join 查询两张表，同时使用 or 连接其中一张表中的筛选条件时，如何使用索引进行查询优化的过程。其中分别使用了 union 分拆原来 or 连接的两个条件，以及优化其他并列的 where 条件从而使得查询优化器能够使用到 index merge 功能。过程比较详细，但是没有对这些操作的原因做出任何解释，这点比较尴尬。
  所以，上面这些对 or 关键字的优化原理到底是什么呢？
• 如何使用性能分析工具定位SQL执行慢的原因？
  先是总体介绍 MySQL 查询优化的整体思路，以及一些慢 SQL 常用命令和参数。
  然后介绍了 EXPLAIN 的用法，包括 type 字段各个值代表的含义，下面是一些关于 type 的总结。
  all 是最坏的情况，因为采用了全表扫描的方式。index 和 all 差不多，只不过 index 对索引表进行全扫描，这样做的好处是不再需要对数据进行排序，但是开销依然很大。如果我们在 Extral 列中看到 Using index，说明采用了索引覆盖，也就是索引可以覆盖所需的 SELECT 字段，就不需要进行回表，这样就减少了数据查找的开销。
  range 表示采用了索引范围扫描，这里不进行举例，从这一级别开始，索引的作用会越来越明显，因此我们需要尽量让 SQL 查询可以使用到 range 这一级别及以上的 type 访问方式。
  ref 类型表示采用了非唯一索引，或者是唯一索引的非唯一性前缀，同时在 ref 列中显示 const，表示连接匹配条件是常量，用于索引列的查找。
  eq_ref 类型是使用主键或唯一索引时产生的访问方式，通常使用在多表联查中。
  const 类型表示我们使用了主键或者唯一索引（所有的部分）与常量值进行比较。
  但是不同的连接方式的效率也会有所不同，效率从低到高依次为 all < index < range < index_merge < ref < eq_ref < const/system。
  唯一的缺点就是讲的稍微有点乱，而且配图不太讲究（不是我吹毛求疵，毕竟这是付费课）。
• 操作系统模型与乐高积木 · OSDI 2018
  本文要介绍的是 2018 年 OSDI 期刊中的论文 —— LegoOS: A Disseminated, Distributed OS for Hardware Resource Disaggregation1，它是 OSDI 2018 的最佳论文（Awarded Best Paper），这篇论文实现的 LegoOS 操作系统可以将数据中心中的单体服务器拆分成通过网络连接的分散硬件，其中每个硬件都由独立的控制器管理。因为现有的操作系统都无法处理类似的场景，所以这篇论文提出了一种分离内核（Split kernel）的操作系统模型来管理和控制底层的硬件资源。
• 为什么系统调用会消耗较多资源
  重读这篇文章，作者列举了详细的系统调用实现方式。但不管那种实现，都会涉及到比较复杂的流程。
• Go语言设计与实现 4.2接口
  Go 中的两种「接口」，即 Go interface{} 和 type xxx interface{} 的内部实现需要依赖 iface 和 eface 结构体，前者只保存对象的属性，后者还会保存对象的方法集。文中还介绍了内存中两种结构的分布方式，并且对比了直接进行类型推断之后再调用对象的方法，和使用多态进行 Dynamic Dispatch 在性能上的差别（多态方式性能差一些，但是可以带来开发的便利性）。

有疑问加站长微信联系（非本文作者）