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 在性能上的差异（多态形式性能差一些，然而能够带来开发的便利性）。