先解释一下什么是 ARTS ?
Algorithm：每周至少做一个 leetcode 的算法题
Review：阅读并点评至少一篇英文技术文章
Tip：学习至少一个技术技巧
Share：分享一篇有观点和思考的技术文章
为什么要开始做呢 ？
保持学习与思考的习惯 ， 万事开头难 ，先开头再讲其他的。
···
这周的内容如下：
Algorithm
LRU缓存机制算法。 什么是LRU缓存机制呢 ？ 以下是我复制百度百科的内容
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
leetcode上的题目介绍 （原题链接：https://leetcode-cn.com/problems/lru-cache/）
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：O(1) 时间复杂度内完成这两个操作
基本思路：最基本的数据存储即为数组，按照插入顺序put，后put的数据排到最后面。get一次，即将该数据排在最前面，当put(T)时，超过了最大容量，则把队列的末尾数据删除，再把T数据插入到最前面。
思考下来，决定用 HashMap 来做基础存储，Node节点作为value，Node维护双向链表的结构，并且保存Map的key和value，便于数据的删除。
执行结果： 24ms ， 内存消耗 48MB
public class LRUTest01 {
/**
* 头部为最老数据, 尾部为最新数据
*/
private Map<Integer,Node> map ;
private Node head;
private Node tail;
private int MAX = 0;
public LRUTest01(int capacity){
map = new HashMap<>(capacity);
MAX = capacity;
}
public void put(int key , int value){
//先判断是否存在, 存在做替换操作
if(map.get(key) != null){
//重新设置value值,value值可能改变
Node node = map.get(key);
node.value = value;
exchange(node);
return;
}
//再判断是否超过了大小
if(map.size() == MAX){
//删除head
Node newHead = head.next;
if(newHead == null){
//边界的补充 只有一个节点(补充)
map.remove(head.key);
//一处逻辑漏洞 bug
tail = null;
}else{
newHead.pre = null;
map.put(newHead.key,newHead);
map.remove(head.key);
head = newHead;
}
}
//将当前元素放在队尾
Node node = null;
if(tail != null){
//已经存在队尾元素
Node oldTail = tail;
node = new Node(oldTail,null,key,value);
oldTail.next = node;
map.put(oldTail.key,oldTail);
}else{
node = new Node(null,null,key,value);
head = node;
}
map.put(key,node);
tail = node;
}
/**
* 交换位置
* @param node
*/
private void exchange(Node node) {
Node next = null;
Node pre = null;
Node oldTail = null;
if(node.equals(tail)){
//是队尾节点
return;
}else if(node.equals(head)){
//是头节点
//将后继节点作为头结点
next = node.next;
next.pre = null;
head = next;
//将当前节点设置成尾节点
oldTail = tail;
oldTail.next = node;
node.pre = oldTail;
tail = node;
//重新设置进入HashMap中
}else{
//将该数据插入到队尾
//将断开的两边合拢
pre = node.pre;
next = node.next;
pre.next = next;
next.pre = pre;
//将当前节点设置成尾节点
oldTail = tail;
oldTail.next = node;
node.pre = oldTail;
tail = node;
//重新设置进入HashMap中
}
resetMap(next);
resetMap(pre);
resetMap(oldTail);
}
private void resetMap(Node next) {
if(next != null){
map.put(next.key,next);
}
}
public int get(int t){
Node node = map.get(t);
if(node != null){
exchange(node);
return node.value;
}else{
return -1;
}
}
public static void main(String[] args) {
/*LRUTest01 lruTest = new LRUTest01(1);
lruTest.put(2,1);
System.out.println(lruTest.get(2));
lruTest.put(3,2);
System.out.println(lruTest.get(2));
System.out.println(lruTest.get(3));*/
LRUTest01 lruTest = new LRUTest01(2);
lruTest.put(2,1);
lruTest.put(2,2);
System.out.println(lruTest.get(2));
lruTest.put(1,1);
lruTest.put(4,1);
System.out.println(lruTest.get(2));
}
class Node{
private Integer value;
private Integer key;
private Node next;
private Node pre;
Node(Node pre, Node next,Integer key, Integer value){
this.key = key;
this.value = value;
this.next = next;
this.pre = pre;
}
}
}
Review
文章标题：10 Signs You Will Suck at Programming
原文地址：https://blog.usejournal.com/10-signs-you-will-suck-at-programming-5497a6a52c5c
文章表达的大致思想：
糟糕（suck）程序员的10个标志
1， Lack of curiosity （缺乏好奇心）
2， Lack of autonomy and resourcefulness （缺乏自主学习）
要相信自己的学习能力，学会google解决问题是第一个要跨过的障碍，遇到问题先google，并且深入阅读文档，实在解决不了再问别人。
3，Lack of persistence in the face of a problem （缺乏坚持解决所遇问题的决心）
编程的本质就是解决问题，遇到问题就解决，别认为"这就是正常情况" 。 解决的问题越多，你对技术的理解会更深入与透彻（deeply and thoroughly），解决一个个问题，其实就是战胜一个一个的挑战。
4，No feeling of success in overcoming a problem （无成就感 -- 碰到问题过早放弃）
只要是自己努力解决了的问题，都要给自己鼓励，这样会增加解决接下来问题的信心。 Let the feeling of success sink in and energize you for the next problem you face（让成功的感觉渗透到你血液中，将会激励你面对接下来的问题）
5，Impatient abourt learning and understanding （对学习和理解缺乏耐心）
不要希望能快速轻松的掌握所有东西，你要让自己享受学习过程，承认自己是在进步的，而不是让自己不堪重负（overwhelmed）。
6，Getting bored/tired from thinking （厌烦思考）
ps：摘抄其中的一段描述，觉得非常典型
Symptoms of this include staring blankly at the screen, feeling a cloud descend on your thoughts, procrastinating on a problem, flipping between browser tabs, and desperately scanning StackOverflow for “an answer”.These are signs that you have hit a mental limitation and need to find away through
大致意思：当你茫然的盯着屏幕，感觉乌云笼罩，在一个问题上花费时间，在浏览器中不断切换，希望能从网上（stackOverflow）中找到答案，这些迹象表明，你心力交瘁地想要解决这个问题。
你的思维能力，会因为以上方式锻炼的越来越好。
7，Inability to think for yourself （缺乏独立思考）
不要指望别人替你思考问题
8，Rigid, narrow and/or disorganized thinking （思维僵化无条理）
事后时常反思，怎么把事情做得更好。
9，Needing the “right” answer instead of recognizing a spectrum of “good” and “bad” answers （只要正确答案，而不是认识一系列的 "好"与“坏”的答案）
要有创造性，解决问题的方法很多，要去不断发现更好，更优的解决方法。
摘抄原文如下：
Recognize that there are numerous ways to solve a problem, and through experience and exposure, you will develop a nuanced understanding overtime about which solutions feel better than others. Looking at the big picture, imagining different possibilities and trusting your gut will lead to better solutions that are more satisfying
10，Not paying careful attention to details （不注意细节）
细节很重要，能帮助你更深入理解问题。
看完这篇文章花费了很长时间，很久没长时间看英文文章了，希望通过这个习惯，能提高自己的阅读能力。
Tip
关于使用技巧上，就简单记录下IDEA上的两个简单的用法
1，VM options 在启动时，设置这个参数，可以在控制台打印出程序的GC信息。
-XX:+PrintGCDetails
2，IDEA的一个插件，用来画 UML 图。插件名称： PlantUML ，如下图 ， 至于使用方式，下次另开一篇博客介绍。
image
Share
本来想准备AQS源码剖析的，UML图画的总是不如人意，秉着源码原理性东西还是精确点好，就留到下周再发出来吧。
这周就简单介绍一个单机高性能框架：Disruptor
它的主页地址： http://imax-exchange.github.io/disruptor/
它是用来做什么的呢 ？ 用来做 单机生产者/消费者场景。
它的特点：
1，它是一个环形队列（环形数组，巧妙的避免了扩容，避免了头尾指针）
2，无锁（涉及到多线程情况下，都是通过cas保证一致性）
3，直接覆盖已消费旧数据，减少GC频率
4，通过一个sequence指针指向下一个元素（并且该指针使用了缓存行对齐，来提高效率）
5，假设该队列长度为 n ，添加 m 个元素的时候， 所在的序号为 n%m 。为了追求高性能，它要求容器的长度设置成2的n次幂，利于二进制计算。
6，如果队列有一个轮回，发现下一个位置有未消费的队列，它提供了8种等待策略
其中最常用的有3种
BlockingWaitStrategy：通过线程堵塞的方式，通过生产者唤醒，被唤醒后，再循环检查依赖的esequence是否已经消费
YieldingwaitStrategy：尝试100次，然后 Thread.yield() 让出cpu
SleepingWaitStrategy： 直接sleep
网友评论