Skip to content

Latest commit

 

History

History
351 lines (251 loc) · 10.8 KB

arts-2018-12-07.md

File metadata and controls

351 lines (251 loc) · 10.8 KB

ARTS之旅(23周)

Algorithm

问题描述

本周做的习题是234. Palindrome Linked List:给定一个单链表,判断其是否是回文。

例1:

Input: 1->2
Output: false

例2:

Input: 1->2->2->1
Output: true

解题思路与代码实现

  1. 堆栈法

遍历链表,将其值存入栈中,然后再次遍历链表时比较栈顶元素是否与链表中的值一样,不一样则不是回文,否则是。

  • 代码实现
public boolean isPalindrome(ListNode head) {
    if (null == head || null == head.next) {
        return true;
    }
    // loop the linked list, store its value into stack 
    Stack<Integer> stackInt = new Stack<Integer>();
    ListNode currNode = head;
    while (currNode != null) {
        stackInt.push(currNode.val);
        currNode = currNode.next;
    }
    currNode = head;
    while (currNode != null) {
        if (stackInt.isEmpty()) {
            return false;
        }
        if (stackInt.pop() != currNode.val) {
            return false;
        }
        currNode = currNode.next;
    }
    return stackInt.isEmpty();
}
   
  • 复杂度分析

    • 时间复杂度为 O(n), n为链表的长度
    • 空间复杂度: O(n)
  1. 快慢指针法 + 链表反转

利用快慢指针法找到中间节点,然后反转右边的子链表,比对左子链表和右子链表。

  • 代码实现
public boolean isPalindrome(ListNode head) { 
    if (null == head || null == head.next) {
        return true;
    }
    ListNode pFast = head;
    ListNode pSlow = head;
    while (pFast != null && pFast.next != null) {
        pFast = pFast.next.next;
        pSlow = pSlow.next;
    }
    // odd linked list,the middle of it is  pSlow.next
    if (pFast != null) {
        pSlow = pSlow.next;
    }
    
    // reverse right list: [pSlow ...]
    pSlow = reverseList(pSlow);
    while (pSlow != null) {
        if (head.val != pSlow.val) {
            return false;
        }
        head = head.next;
        pSlow = pSlow.next;
    }
    return true;
}

private ListNode reverseList(ListNode head) {
    if (null == head || null == head.next) {
        return head;
    }
    ListNode preNode = null;
    while (head != null) {
        ListNode nextNode = head.next;
        head.next = preNode;
        preNode = head;
        head = nextNode;
    }
    return preNode;
}
  • 复杂度分析

    • 时间复杂度为 O(n), n为链表的长度
    • 空间复杂度: O(1)

Review

本周阅读的英语文章

  • 来源: Medium
  • 标题:Code Review Best Practices

特别是如何评审代码以及如何处理评审意见值得学习,都需要一个open的心态。

动机(Motivation)

代码评审(CR)能够提高代码质量以及从团队和公司文化获得正面响应。不管是对提交者还是评审者都有易处: 双方可以相互学习,提高代码质量、避免常见的bug或者安全问题。

评审什么(What to review)

没有一定之规,团队成员自行决定的:

  • 有的评审每个提交记录
  • 有的则是提供一个阀值,达到之后才会进入评审之列

总之,权衡工程师的时间与代码质量。还有就是任何人都需要的,不针对层级:并不是说你是团队的资深开发者就意味着你的代码不需要评。

Code reviews are classless: being the most senior person on the team does not imply that your code does not need review.

代码评审的时间点

经过代码测试、代码风格等检查之后,归并到主干之前进行评审。对于大的改动需要分多个分支,分支中有小分支,然后一个个评审之。

代码评审的准备

提交者有责任保证CR的容易进行,不要浪费彼此的时间:

  • 范围和大小:太多文件或者超过20分钟需要分多次评审
  • 为了节省评审者的时间仅提交完全自测、自我评审的。
  • 重构变化:更多的是关注程度逻辑而不是代码风格、语法、格式化的东西,这些都可以交由工具处理。

提交信息两种方式

  • 总结性写,在80个字以内
  • 具体也可以,第一行是邮件;后面是120字以内的具体描述

例子:

> BAD. Don't do this.
Make compile again

> Good.
Add jcsv dependency to fix IntelliJ compilation

找到相关的reviewer

至少两位熟悉代码基的两位评审者,其中一般有一位是项目主导者或者资深工程师。

【我们现在的评审,都是不是特别熟悉项目代码的人,不过有两轮,第一轮是与小组长过,但其已经不写代码,需求评审他有参与;第二轮是与分组经理评,更多关注流程安全、数据查询的性能啥的。始终有不合理的地方,个人觉得应该需要交叉评审,就是一个需求下来,在整个需求开发人员,互评,这种更为细致,讨论更多,但缺点是耗费的时间很多,需要找到哪些地方是需要重点评审的地方,比如数据库查询、业务逻辑的地方,其他的可以不评。】

代码评审执行

1.提交者需要与评审者沟通好时间,而评审者若发现不能评审或者评审不完需要找其他的人; 2.评审尽可能是一个整块时间,以便评审者能够详细指明代码的改动合理性; 3.作为评审者,是有责任让代码符合公司标准和质量; 4.评审关注点:

  • 目标

    • 代码是否实现了开发者的需求(新特性、重构、修复bug等)
    • 提问:函数和类存在的理由,设计是否合理
  • 实现层面

    • 以自己的角度,若是你去实现,你会怎么做;然后比对之;
    • 是否添加了系统依赖;
    • 是否进行了重复造轮子;
  • 可读性和风格方面

  • 维护性方面

    • 评审测试案例,看其是否有遗漏,或者没有覆盖到。
    • 是否包含了集成测试
    • 留下comment的
    • 相关文档是否更新?

总之,对于好的代码,不要吝啬夸赞;对于不同意的代码需要合理的提供建议,尊重提交者,一旦权衡不下来的,可以与之讨论或者找其他人一同评审

安全方面

  • 检查是否有常见的缺陷;
  • 不好配置、缺少日志事件等;
  • 若不能确认,可以找安全专家协同处理;

Comments: 简洁, 友好, 可行

  • 评论需要简洁明了,针对代码,而不是开发者;
  • 不清楚的地方,提出来,不要忽略了;
  • 切记使用占有性语句,比如你的代码存在bug、我之前的代码是可以工作的,给你改得不行了;或者一无是处的语句,比如:这根本不会工作
  • 区别出建议和讨论的评论,如有必要更为深层次指出问题;
  • 若需要再次评论,请指出;

提交者如何回应评审人

  • 不要拒绝评审者的意见,对于任何一个评论都需要认真对待,即便你不认同的;
  • 回应每一个comment,解释你所做决定的理由;
  • 若你不认同其观点,可以进行实时沟通或者找第三方观点;
  • 提交到同一个分支,每次处理一个comment的。

代码评审示例

代码评审的注释格式://R:....

  1. 名字不一致性
class MyClass {
  private int countTotalPageVisits; //R: name variables consistently
  private int uniqueUsersCount;
}
  1. 函数签名不一致性
interface MyInterface {
  /** Returns {@link Optional#empty} if s cannot be extracted. */
  public Optional<String> extractString(String s);

/** Returns null if {@code s} cannot be rewritten. */
  //R: should harmonize return values: use Optional<> here, too
  public String rewriteString(String s);
}
  1. 库使用
//R: remove and replace by Guava's MapJoiner
String joinAndConcatenate(Map<String, String> map, String keyValueSeparator, String keySeparator);
  1. 个人品味
int dayCount; //R: nit: I usually prefer numFoo over fooCount; up to you, but we should keep it consistent in this project
  1. Bugs
//R: This performs numIterations+1 iterations, is that intentional?
//   If it is, consider changing the numIterations semantics?
for (int i = 0; i <= numIterations; ++i) {
  ...
}

架构疑虑

 //R: I think we should avoid the dependency on OtherService. 
 // Can we discuss this in person?
otherService.call();

Tip:暂缺


Share:Redis持久化之AOF模式

什么是AOF模式

以追加文件的方式将写命令写入文件,保存数据状态。

AOF模式的优缺点

优点 缺点
追加方式写文件 对于相同大小的数据集,AOF方式比RDB方式耗费时间更多
多种写文件的方式,并自动重写AOF文件 AOF恢复数据起来比RDB要慢
会将写命令连续记录,易于解析文件 AOF文件过大时,一旦遇到I/O阻塞,可能无法恢复数据

AOF模式的工作原理

  • Redis服务器调用fork,生成一个子进程
  • Redis子进程写一个新的AOF文件
  • Redis服务器将写的命令缓存与内存buffer中,同时写旧的AOF文件
  • 当Redis子进程写完AOF文件后,Redis服务器会得到一个信号,并将之前缓存的写命令传给子进程
  • 更改旧AOF的文件名,并开始将内存的写命令写入新文件中

AOF重写

随着Redis服务器的运行,不断写命令会写入AOF文件,使其会变得越来越大,占用的磁盘会越来越多。若发生故障,恢复数据时,执行AOF中的内容,占用的时间也会很多。重写操作触发两种方式:

  • 手动触发

在Redis客户端执行 bgrewriteaof, Redis服务器接收到之后会创建一个子进程读取AOF文件,并将重复的命令剔除。

  • 配置方式
auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 60mb

AOF模式的配置示例

appendonly yes
appendfsync everysec
no-appendfync-on-rewrite no
auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 60mb

其中,

  • auto-aof-rewrite-percentageauto-aof-rewrite-min-size 控制AOF重写, 例子中表示重写之后AOF最小是60mb,超过上一次重写文件的一倍就会触发重写操作;

  • appendfsync 与两个关键的系统调用:writefsync有关。有三个选项:

    • no:系统决定何时同步,不推荐使用。不在主动调用fsync,系统会在每30s执行一次内核的缓存到disk中;
    • everysec:每秒钟将写命令写入文件中,每秒调用write和fsync;如果disk拷贝的速度比write还要慢 Redis会保证在2s之内将写命令写入文件;
    • always:一旦有写命令就将其写入文件中,write和fsync是一个组合操作,类似于组提交

参考资料