arts-20200705

Algorithm

• 题目：LeetCode-724 寻找数据的中心索引
• 分析
  • 根据题目定定义，中心索引 i 左边和右边的元素之和相等，最直接的思路二层循环暴力来算，但是实际上
    • leftSum(i + 1) = leftSum(i) + nums[i]，其中 leftSum(i) = nums[0] + nums[1] + ... + nums[i - 1]
    • rightSum(i + 1) = rightSum(i + 1) + nums[i]，其中 rightSum(i + 1) = nums[i + 2] + nums[i + 3] + ... + nums[nums.length - 1]
  • 需要注意情况，当 i 左边或右边没有元素时，和为 0
• 解法
  1. 如果 nums.length < 2 则中心索引为 i
  2. 先算出 nums[1] 到 nums[nums.length -1] 之和记为初始 rightSum，初始 leftSum 为 0
  3. 从下标 1 开始遍历 nums，如果 leftSum 和 rightSum 相等或i == nums.length 时结束，如果 i < nums.lrgnth 返回 i，否则返回 -1
• 代码

  public int pivotIndex(int[] nums) {
         if (nums.length == 0) {
             return -1;
         }
         if (nums.length == 1) {
             return 0;
         }
  
         int left = 0;
         int right = 0;
  
         for (int i = 1; i != nums.length; i++) {
             right += nums[i];
         }
  
         int i = 1;
         while (i < nums.length && left != right) {
             left += nums[i - 1];
             right -= nums[i];
             i++;
         }
  
         return left == right ? i - 1 : -1;
     }

Review

• 原文地址：MapReduce: Simplified Data Processing on Large Clusters
• Google 经典论文，提出了 MapReduce 编程模型，以及该模型在分布式系统下实现的一些要点和优化
  • 背景：Google 处理大规模的数据需要解决并行化、数据分发、故障处理的问题
  • 解法：提出 MapReduce 的编程模型，隐藏并行、数据分许、故障处理的细节
    • Map: (k1, v1) -> list(k2, v2) 根据输入的 key/value 对生产新的 key/value 对的集合，作为中间结果，计算逻辑需要用户实现
    • Reduce: (k2, list(v2)) -> list(v2) 从同一个 key 有序结合中计算得出最终结果，计算逻辑需要用户实现
  • 影响
    • 提出了处理海量数据的通用方案，推动了大数据计算领域发展
    • 简化了并行、故障处理逻辑，提升了研发效果
    • 提供了水平扩展能力，可以通过加机器来提升性能
  • 工程设计
    • Master Slave 架构：Master 负责监控Woker状态、调度任务
    • 并行策略：
      1. 输入文件进行按切分，本质是上做分片，每个分片有对应的 Worker 进行处理
      2. Map 和 Reducer 阶段，Worker 之间没有数据重叠，因此不存在并发问题
    • 故障处理策略：重新执行
      • 执行 Map 任务的 Worker 故障：重新执行该 Worker 的 Map 任务以及相关的 Reduce 任务
      • 执行 Reduce 任务的 Worker 故障：重新执行该 Worker 的 Reduce 任务
    • 优化
      • 本地化：MapReduce 的输入输出为 GFS 分布式文件系统，每个文件存多个副本（通常为3），给 Worker 分配任务时尽量分配给保存输入数据副本的 Worker，不满足条件时，尽量分给靠近持有副本结点的 Worker，降低网络 IO 开销
      • Backup：当执行任务快结束时，还有某个结点特别慢（可能是机器硬件差或故障等原因）影响整个任务进度，会在其他结点执行一个 Backup 任务，这两个任务任意一个执行完就算执行完成

Tip

1. 以 SDK 的形式提供能力是常见的做法，但是升级会非常头疼，可以考虑把 SDK api 声明暴露给用户，以 javaagent 的方式提供实现可以缓解这个问题，可以在这个方向有些探索
2. 以 javaagent 的方式提供装饰逻辑，来代替 cglib 看起来具有分离、对用户无感知的优点

Share

读了《非暴力沟通》前两章，有几个印象比较深的点：

1. 沟通的表达方式很重要，并且是可以后天训练的，有意识的行为比纯本能的行为通常更有效
2. 学会区分观察和评论，不要习惯性采用防御性的姿态，学会区分是客观事实的评价，还是主观个人的评论