cartoon's blog

前言

​ 在研究java集合源码的时候，发现了一个很少用但是很有趣的点：Queue以及Deque，平常在写leetcode经常用LinkedList向上转型Deque作为栈或者队列使用，但是一直都不知道Queue的作用，于是就直接官方文档好了。

正文

概念

从上图看出，Queue以及Deque都是继承于Collection，Deque是Queue的子接口。

下面来看一下官方文档的解释。

A linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”. Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value (either null or false, depending on the operation). The latter form of the insert operation is designed specifically for use with capacity-restricted Queue implementations; in most implementations, insert operations cannot fail.

从Deque的解释中，我们可以得知：Deque是double ended queue，我将其理解成双端结束的队列，双端队列，可以在首尾插入或删除元素。而Queue的解释中，Queue就是简单的FIFO队列。

所以在概念上来说，Queue是FIFO的单端队列，Deque是双端队列。

而在使用上，又有什么差别呢？

使用

从上图我们可以得知，Queue有一个直接子类PriorityQueue，而Deque中直接子类有两个：LinkedList以及ArrayDeque。

• PriorityQueue

我觉得重点就在圈定的两个单词：无边界的，优先级的堆。然后再看看源码

在第一张图片的源码中，明显看到PriorityQueue的底层数据结构是数组，而无边界的形容，那么指明了PriorityQueue是自带扩容机制的，具体请看PriorityQueue的grow方法。

在第二张第三张图片中，可以看到插入元素的时候是需要经过compareTo的处理，那么最常用就是一些范围极值的输出，类似于堆排序的用法。

下面演示一下正反序输出三个元素的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

private static void negativePrint(int[] nums) {
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int temp:nums){
            queue.add(temp);
        }
        System.out.println();
        System.out.print("倒序输出：");
        for(int i=0;i<3;i++){
            System.out.print(queue.poll()+" ");
        }
    }

    private static void positivePrint(int[] nums){
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int temp:nums){
            queue.add(temp);
        }
        System.out.print("正序输出：");
        for(int i=0;i<3;i++){
            System.out.print(queue.poll()+" ");
        }
    }

1
2

正序输出：1 2 3 
倒序输出：9 8 8 

这个在一些排行榜或者输入第N个最大/小元素会比较常用。

• LinkedList以及ArrayDeque

从官方解释来看，ArrayDeque是无初始容量的双端队列，LinkedList则是双向链表。而我们还能看到，ArrayDeque作为队列时的效率比LinkedList要高，而在栈的使用场景下，无疑具有尾结点不需判空的LinkedList较高效。

下面演示ArrayDeque作为队列以及LinkedList作为栈的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

private static void usingAsQueue() {
        Deque<Integer> queue=new ArrayDeque<>();
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
        queue.addLast(12);   //添加元素
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
        System.out.println(queue.peekFirst());   //获取队列首部元素
        System.out.println(queue.pollFirst());   //获取并移除栈顶元素
        System.out.println("队列为空:"+queue.isEmpty());   //判断队列是否为空
 }

private static void usingAsStack() {
        //作为栈使用
        Deque<Integer> stack=new LinkedList<>();
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        stack.addFirst(12);
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        System.out.println(stack.peekFirst());   //获取栈顶元素
        System.out.println(stack.pollFirst());   //获取并移除栈顶元素
        System.out.println("栈为空:"+stack.isEmpty());   //判断栈是否为空
        System.out.println("============================================");
    }

栈为空:true
栈为空:false
12
12

栈为空:true

队列为空:true
队列为空:false
12
12
队列为空:true

小提示

在Deque中，获取并移除元素的方法有两个，分别是removeXxx以及peekXxx。

存在元素时，两者的处理都是一样的。但是当Deque内为空时，removeXxx会直接抛出NoSuchElementException，而peekXxx则会返回null。

所以无论在实际开发或者算法时，推荐使用peekXxx方法

其实ArrayDeque和LinkedList都可以作为栈以及队列使用，但是从执行效率来说，ArrayDeque作为队列以及LinkedList作为栈使用会是更好的选择。

另外，我在leetcode看到有人采用Vector下的Stack，这个同步加锁粒度过大(对象级)，另外我觉得算法中没有线程同步的需要吧。

• 小结

PriorityQueue可以作为堆使用，而且可以根据传入的Comparator实现大小的调整，会是一个很好的选择。

ArrayDeque通常作为栈或队列使用，但是栈的效率不如LinkedList高。

LinkedList通常作为栈或队列使用，但是队列的效率不如ArrayQueue高。

总结

在java中，Queue被定义成单端队列使用，Deque被定义成双端队列使用。

而由于双端队列的定义，Deque可以作为栈或者队列使用，而Queue只能作为队列或者依赖于子类的实现作为堆使用。

本文首发于cartoon的博客
转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/queue%E4%B8%8Edeque%E7%9A%84%E5%8C%BA%E5%88%AB/

前序

在看HashMap源码的时候，看到HashMap的hash函数里面有用到>>>的运算符，之前经常在除2操作用到>>运算符，但是还是第一次看到>>>，于是就来记录一下。

情景复现

hashMap的hash函数源码

因为里面主要是先获取key的hashCode，这是jvm生成的，所以我单独用1模拟hashCode

1

System.out.println((h = 1) ^ (h >>> 16));

结果如下

1

情景复现： 1

步骤解析

这段代码主要由三段代码运算而成

1. h直接赋值为1
2. h>>>16位
3. 步骤1与步骤2的异或运算

所以从结果推断出1>>>16结果为0

测试

1
2
3
4

System.out.println("-12>>>2结果为："+Integer.toBinaryString(-12>>>2));
System.out.println("12>>>2结果为："+Integer.toBinaryString(12>>>2));
System.out.println("-12>>2结果为："+Integer.toBinaryString(-12>>2));
System.out.println("12>>2结果为："+Integer.toBinaryString(12>>2));

1
2
3
4

-12>>>2结果为：111111111111111111111111111101
12>>>2结果为：11
-12>>2结果为：11111111111111111111111111111101
12>>2结果为：11

分析

从结果可以看出，利用正数做操作时，>>与>>>结果没有变化，但是负数的操作时发生了变化，这个对比证明了>>>的操作与符号位有关。

• 正数操作

由于位运算时，利用Integer.toBinaryString方法输出不会输出前置0，所以可以推断两个运算符的操作都是右移n位补0

• 负数操作

由于负数存储的是它的补码，在进行>>运算的时候明显看到生成的二进制字符串补1，且长度比正数运算的时候要长，java在二进制中是不区分符号位的，所以最后的十进制表示的数会异常大。

总结

两个运算符，在进行正数移位的时候操作是一样的。但是在处理负数时，>>补1，是带符号操作的。而>>>补0，是无符号操作的。

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/无符号运算符与有符号运算符的区别/

    本文首发于cartoon的博客
    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/for与while时间的对比

    相关文章:JAVA遍历机制的性能的比较

前言

索引随机访问数组相信是很常见的操作.

但是昨天在做leetcode的Reverse String时，发现了很奇怪的现象，具体如下图

当时我也觉得不可思议，怎么快了那么多，所以今天复盘一下。

正文

注：这篇文章只涉及原始数组的索引遍历，不涉及包装数据结构以及foreach

测试代码

• for

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static void textFor(){
        int[] data=new int[1000];
        int i=0;
        for(;i<1000;i++){
            data[i]=i;
        }
        i=0;
        long start=System.currentTimeMillis();
        for(;i<1000;i++){
            System.out.print(data[i]+" ");
        }
        long end=System.currentTimeMillis();
        System.out.println();
        System.out.println("for use:"+(end-start)+"ms");
    }

• while

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static void textWhile(){
        int[] data=new int[1000];
        int i=0;
        for(;i<1000;i++){
            data[i]=i;
        }
        i=0;
        long start=System.currentTimeMillis();
        while(i<1000){
            System.out.print(data[i++]+" ");
        }
        long end=System.currentTimeMillis();
        System.out.println();
        System.out.println("while use:"+(end-start)+"ms");
    }

结果

1
2
3
4
5
6
7
8
9
10
11

for use:35ms
while use:15ms

for use:14ms
while use:6ms

for use:14ms
while use:8ms

for use:20ms
while use:5ms

所用时间可能不一样，但是大概比例应该跟我的差不多

有点意外的是，while比for竟然要少一倍(大概)的时间，颠覆了我之前的认知。

结果分析

虽然我没有debug代码，但是我猜测是循环执行语句的多少差别。

for中，执行顺序是

• 判断循环变量是否越界
• 执行打印语句
• 循环变量自增

while中，执行顺序是

• 判断循环变量是否越界
• 执行打印语句，循环变量自增

与for相比，while所执行的语句量少掉1/3，所以我觉得这就是原因。(如果有更好的原因可以评论或者发起Issue)

后话

生命不息，技术不止。

很多时候我也为了代码量的减少不理会运行时间的差异，这次吸收教训，之后在实际开发会更加注意时间。

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/object%E7%9A%84%E6%88%90%E5%91%98%E6%96%B9%E6%B3%95%E4%BB%A5%E5%8F%8A%E4%BD%9C%E7%94%A8/

前言

对的。这次也是面试题，又是有点懵逼的一道题，记得当时只答出了wait跟notify。。。

正文

学java的都知道，Object是所有类的父类，但是相信很多人都忽略掉Object中的成员方法(包括我)。

翻过官方文档后，发现其实Object类成员方法可以总结为以下几类

后话

其实Object类的很多方法都很实用，多线程同步，对象比较等等，但是平时自己比较少关注，可能是我菜鸡吧。

希望看到文章的你们能有所收获，也希望我以后被问到这个不会再懵逼。

    本文首发于cartoon的博客
    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/java实现克隆的方法

前言

这也是昨天的面试题。

当时只说了深拷贝以及浅拷贝，面试官问了两遍还有吗，我很肯定的说就这两种了，面试结束之后查了一下，啪啪打脸。

正文

JAVA实现克隆有两种形式

• 浅克隆
• 深克隆

浅克隆与深克隆的区别

JAVA将数据类型分为基本数据类型以及引用数据类型，我认为浅克隆与深克隆的区别主要在于对引用类型的成员属性的操作。深度克隆应该递归克隆引用类型的成员属性。

浅克隆实现

• 实现Cloneable接口
• 重写clone方法，调用父类的clone方法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public class Text implements Cloneable{

    private int age;

    private Name name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public Name getName() {
        return name;
    }

    public void setName(Name name) {
        this.name = name;
    }

    @Override
    protected Object clone(){
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }
}

class Name{
    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

public class Main {

    public static void main(String[] args){
        Name name1=new Name();
        name1.setName("name1");
        Text t1=new Text();
        t1.setAge(12);
        t1.setName(name1);
        Text t2=(Text) t1.clone();
        System.out.println(t2.getName().getName());
        name1.setName("name2");
        System.out.println(t2.getName().getName());

    }

}

输出

1
2

name1
name2

结果分析

因为只是直接调用父类的clone方法，没有对成员属性进行处理，所以在修改t1属性name的值时，t2属性name的值也会随之改变。

优点

简单易实现

缺点

无法真正克隆对象

深克隆实现

通过递归克隆实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class Text implements Cloneable{

    private int age;

    private Name name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public Name getName() {
        return name;
    }

    public void setName(Name name) {
        this.name = name;
    }

    @Override
    protected Object clone(){
        Text text=null;
        try {
            text=(Text) super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        text.setName((Name) text.getName().clone());
        return text;
    }
}

class Name implements Cloneable{
    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    protected Object clone() {
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            e.printStackTrace();
        }
        return null;
    }
}

输出

1
2

name1
name1

通过序列化实现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

public class Text implements Serializable{

    private static final long serialVersionUID = 8723901148964L;

    private int age;

    private Name name;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public Name getName() {
        return name;
    }

    public void setName(Name name) {
        this.name = name;
    }

    public Object myClone(){
        Text text=null;
        ByteArrayOutputStream bos=new ByteArrayOutputStream();
        try {
            ObjectOutputStream oos=new ObjectOutputStream(bos);
            oos.writeObject(this);
            ByteArrayInputStream bis=new ByteArrayInputStream(bos.toByteArray());
            ObjectInputStream ois=new ObjectInputStream(bis);
            text=(Text)ois.readObject();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
        return text;
    }
}

class Name implements Serializable {

    private static final long serialVersionUID = 872390113109L;

    private String name;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return name;
    }
}

输出

1
2

name1
name1

结果分析

采用深克隆能有效隔离源对象与克隆对象的联系。

从实现过程来说，递归克隆存在克隆过程多且复杂的缺点，所以建议采用序列化的方式进行

深克隆。

总结

JAVA对象克隆共有两种形式，三种方法

• 浅克隆
  • 调用clone方法
• 深克隆
  • 递归调用clone方法
  • 序列化对象

三种方法之间互有优缺点，具体采用要根据实际情况。

    本文首发于cartoon的博客
    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/collections/

    推荐一篇不错的博文:https://gitee.com/SnailClimb/JavaGuide/blob/master/docs/java/Basis/Arrays,CollectionsCommonMethods.md

前言

就在刚刚面试，被问到了Collections工具类有什么功能，我懵了，很少涉及到Collections这个工具类，只答了对集合元素的操作以及将线程不同步的集合类转换成线程同步，下定决心复盘一下。

正文

Collections工具类是java.util包中的一个工具类，主要功能是对集合及其元素进行操作。虽然被问的有点懵，在结束查看官方文档时发现其实可以分成以下几大部分

对集合本体的操作

线程同步集合的包装

• 特征
  • 方法名为synchronizedXxx
• 适用范围
  • List
  • Collection
  • Set
  • Map
• 缺点
  • 每次读写都要加锁，锁的层级为对象，不利于多线程的同时操作
  • 在使用Iterator的遍历时修改元素ConcurrentModificationException
  • 建议使用java.util.concurrent的集合线程同步类

返回不可变集合

• 特征

  • 方法名为emptyXxx(空集合)/singletonXxx(包含传入元素的集合)/unmodifiableXxx(包含传入集合元素的集合)

• 适用范围

  • emptyXxx

    • Set
    • List
    • Map
    • Iterator
    • Enumeration

  • singletonXxx

    • Set
    • List
    • Map

  • unmodifiableXxx

    • Map

    • List

    • Set

返回指定集的动态类型安全视图

• 特征
  • 方法名为checkedXxx
• 适用范围
  • List
  • Map
  • Queue
  • Set
  • Collection

集合间的转换

• 特征

  • asLifoQueue(将传入的Deque转换成Queue)

  • list(将传入的Enumeration转换成ArrayList)

  • newSetFromMap(根据传入的空Map返回Set)

  • nCopies(根据传入的n返回含n个副本的List)

集合内元素的操作

添加元素到集合中

• 特征
  • addAll
  • copy(将源集合元素复制到目标集合中)
• 适用范围
  • addAll
    • Collection
  • copy
    • List

查找元素

• 特征
  • binarySearch(二分查找特定元素)
  • frequency(查找元素出现次数)
  • indexOfSubList(返回目标list在源list的开始位置)
  • subIndexOfSubList(返回目标list在源list的结束位置)
  • shuffle(返回随机索引元素)
• 适用范围
  • binarySearch
    • List
  • frequency
    • Collection
  • shuffle
    • List

替换

• 特征
  • fill(替换集合所有元素)
  • replaceAll(替换特定的值)
• 适用范围
  • fill
    • List
  • replaceAll
    • List

改变元素位置

• 特征
  • sort(排序)
  • swap
  • rotate(反转)
  • reverse
• 适用范围
  • List

对比元素

• 特征
  • min/max(寻找最大/小元素)
  • disJoint(判断两个集合元素是否全不同)
• 适用范围
  • Collection

总结

Collections工具类能对各接口以及实现类实现多种操作

• 集合类级操作
  • 返回线程安全集合
  • 返回不可变集合
  • 返回安全视图
  • 集合间的转换
• 涉及到内部元素的操作
  • 添加元素到集合中
  • 查找特定元素
  • 替换元素
  • 改变元素位置
  • 元素间的比较

虽然有些方法不如其他包内的工具类好用，但是总体来说功能还是非常强大的。

这篇文章算是对官方文档的总结和归纳，也加以自己的思考，也是面试题之一，希望自己能在之后不会再吃这道题的亏。

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/java/java%E9%81%8D%E5%8E%86%E6%9C%BA%E5%88%B6%E7%9A%84%E6%80%A7%E8%83%BD%E6%AF%94%E8%BE%83/

缘由

    近段时间在写leetcode的Lemonade Change时候，发现了for循环与forEach循环的耗时是不一致的，在提交记录上面差了一倍……

    平常开发绝大部分业务逻辑的实现都需要遍历机制的帮忙，虽说也有注意到各数据结构操作的性能比较，但是忽视了遍历机制性能的差异。原本前两天就开始动手写，拖延症……

正文

    现阶段我所知道JAVA遍历机制有三种

• for循环

• forEach循环

• Iterator循环

    JAVA数据结构千千万，但是大部分都是对基础数据结构的封装，比较HashMap依赖于Node数组，LinkedList底层是链表，ArrayList对数组的再封装……扯远了

    总结来说，JAVA的基础数据结构，我觉得有两种

• 数组
• 链表

    如果是加上Hash(Hash的操作与数组以及链表不太一致)，就是三种

    因为平常开发大部分都优先选择包装后的数据结构，所以下面我会使用

• ArrayList(包装后的数组)
• LinkedList(包装后的链表)
• HashSet(包装后的Hash类型数组)

    这三种数据结构在遍历机制不同的时候时间的差异

    可能有人对我为什么不对比HashMap呢，因为JAVA设计中，是先实现了Map，再实现Set。如果你有阅读过源码就会发现:每个Set子类的实现中，都有一个序列化后的Map对应属性实现，而因为Hash的查找时间复杂度为O(1)，得出key后查找value的时间大致是一致的，所以我不对比HashMap。

题外话

    我在阅读《疯狂JAVA》读到:JAVA的设计者将Map的内部entry数组中的value设为null进而实现了Set。因为我是以源码以及官方文档为准，具体我不清楚正确与否，但是因为Hash中的key互不相同，Set中元素也互不相同，所以我认为这个观点是正确的。

    为了测试的公平性，我会采取以下的限定

• 每种数据结构的大小都设置三种量级
  • 10
  • 100
  • 1000
• 元素都采用随机数生成
• 遍历进行操作都为输出当前元素的值

    注:时间开销受本地环境的影响，可能测量值会出现变化，但是总体上比例是正确的

ArrayList的比较

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112

  public class TextArray { private static Random random; private static List<Integer> list1; private static List<Integer> list2; private static List<Integer> list3; public static void execute(){ random=new Random(); initArray(); testForWith10Object(); testForEachWith10Object(); testIteratorWith10Object(); testForWith100Object(); testForEachWith100Object(); testIteratorWith100Object(); testForWith1000Object(); testForEachWith1000Object(); testIteratorWith1000Object(); } private static void testForWith10Object(){ printFor(list1); } private static void testForWith100Object(){ printFor(list2); } private static void testForWith1000Object(){ printFor(list3); } private static void testForEachWith10Object(){ printForeach(list1); } private static void testForEachWith100Object(){ printForeach(list2); } private static void testForEachWith1000Object(){ printForeach(list3); } private static void testIteratorWith10Object() { printIterator(list1); } private static void testIteratorWith100Object() { printIterator(list2); } private static void testIteratorWith1000Object() { printIterator(list3); } private static void printFor(List<Integer> list){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); for(int i=0,length=list.size();i<length;i++){ System.out.print(list.get(i)+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("for for "+list.size()+":"+(end-start)+"ms"); } private static void printForeach(List<Integer> list){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); for(int temp:list){ System.out.print(temp+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("foreach for "+list.size()+":"+(end-start)+"ms"); } private static void printIterator(List<Integer> list){ System.out.println(); System.out.print("data:"); Iterator<Integer> it=list.iterator(); long start=System.currentTimeMillis(); while(it.hasNext()){ System.out.print(it.next()+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("iterator for "+list.size()+":"+(end-start)+"ms"); } private static void initArray(){ list1=new ArrayList<>(); list2=new ArrayList<>(); list3=new ArrayList<>(); for(int i=0;i<10;i++){ list1.add(random.nextInt()); } for(int i=0;i<100;i++){ list2.add(random.nextInt()); } for(int i=0;i<1000;i++){ list3.add(random.nextInt()); } } }

• 输出(忽略对元素的输出)

  1 2 3 4 5 6 7 8 9 10 11

  for for 10:1ms foreach for 10:0ms iterator for 10:2ms for for 100:5ms foreach for 100:4ms iterator for 100:12ms for for 1000:33ms foreach for 1000:7ms iterator for 1000:16ms

  	10	100	1000
  for	1ms	5ms	33ms
  forEach	0ms	4ms	7ms
  Iterator	2ms	12ms	16ms

• 结论

      for的性能最不稳定，foreach次之，Iterator最好

• 使用建议

  1. 在数据量不明确的情况下(可能1w,10w或其他)，建议使用Iterator进行遍历

  2. 在数据量明确且量级小的时候，优先使用foreach

  3. 需要使用索引时，使用递增变量的开销比for的要小

LinkedList的比较

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

  public class TextLinkedList { private static Random random; private static List<Integer> list1; private static List<Integer> list2; private static List<Integer> list3; public static void execute(){ random=new Random(); initList(); testForWith10Object(); testForEachWith10Object(); testIteratorWith10Object(); testForWith100Object(); testForEachWith100Object(); testIteratorWith100Object(); testForWith1000Object(); testForEachWith1000Object(); testIteratorWith1000Object(); } private static void testForWith10Object() { printFor(list1); } private static void testForEachWith10Object() { printForeach(list1); } private static void testIteratorWith10Object() { printIterator(list1); } private static void testForWith100Object() { printFor(list2); } private static void testForEachWith100Object() { printForeach(list2); } private static void testIteratorWith100Object() { printIterator(list2); } private static void testForWith1000Object() { printFor(list3); } private static void testForEachWith1000Object() { printForeach(list3); } private static void testIteratorWith1000Object() { printIterator(list3); } private static void printFor(List<Integer> list){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); for(int i=0,size=list.size();i<size;i++){ System.out.print(list.get(i)); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("for for "+list.size()+":"+(end-start)+"ms"); } private static void printForeach(List<Integer> list){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); for(int temp:list){ System.out.print(temp+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("foreach for "+list.size()+":"+(end-start)+"ms"); } private static void printIterator(List<Integer> list){ System.out.println(); System.out.print("data:"); Iterator<Integer> it=list.iterator(); long start=System.currentTimeMillis(); while(it.hasNext()){ System.out.print(it.next()+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("iterator for "+list.size()+":"+(end-start)+"ms"); } private static void initList() { list1=new LinkedList<>(); list2=new LinkedList<>(); list3=new LinkedList<>(); for(int i=0;i<10;i++){ list1.add(random.nextInt()); } for(int i=0;i<100;i++){ list2.add(random.nextInt()); } for(int i=0;i<1000;i++){ list3.add(random.nextInt()); } } }

• 输出(忽略对元素的输出)

  1 2 3 4 5 6 7 8 9 10 11

  for for 10:0ms foreach for 10:1ms iterator for 10:0ms for for 100:1ms foreach for 100:0ms iterator for 100:3ms for for 1000:23ms foreach for 1000:25ms iterator for 1000:4ms

  	10	100	1000
  for	0ms	1ms	23ms
  forEach	1ms	0ms	25ms
  Iterator	0ms	3ms	4ms

• 结论

      foreach的性能最不稳定，for次之，Iterator最好

• 使用建议

  1. 尽量使用Iterator进行遍历

  2. 需要使用索引时，使用递增变量的开销比for的要小

HashSet的比较

    注：因Hash遍历算法与其他类型不一致，所以取消了for循环的比较

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

  public class TextHash { private static Random random; private static Set<Integer> set1; private static Set<Integer> set2; private static Set<Integer> set3; public static void execute(){ random=new Random(); initHash(); testIteratorWith10Object(); testForEachWith10Object(); testIteratorWith100Object(); testForEachWith100Object(); testIteratorWith1000Object(); testForEachWith1000Object(); } private static void testIteratorWith10Object() { printIterator(set1); } private static void testForEachWith10Object() { printForeach(set1); } private static void testIteratorWith100Object() { printIterator(set2); } private static void testForEachWith100Object() { printForeach(set2); } private static void testIteratorWith1000Object() { printIterator(set3); } private static void testForEachWith1000Object() { printForeach(set3); } private static void initHash() { set1=new HashSet<>(); set2=new HashSet<>(); set3=new HashSet<>(); for(int i=0;i<10;i++){ set1.add(random.nextInt()); } for(int i=0;i<100;i++){ set2.add(random.nextInt()); } for(int i=0;i<1000;i++){ set3.add(random.nextInt()); } } private static void printIterator(Set<Integer> data){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); Iterator<Integer> it=data.iterator(); while (it.hasNext()){ System.out.print(it.next()+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("iterator for "+data.size()+":"+(end-start)+"ms"); } private static void printForeach(Set<Integer> data){ System.out.println(); System.out.print("data:"); long start=System.currentTimeMillis(); for(int temp:data){ System.out.print(temp+" "); } System.out.println(); long end=System.currentTimeMillis(); System.out.println("foreach for "+data.size()+":"+(end-start)+"ms"); } }

• 输出(忽略对元素的输出)

  1 2 3 4 5 6 7 8

  iterator for 10:0ms foreach for 10:0ms iterator for 100:6ms foreach for 100:0ms iterator for 1000:30ms foreach for 1000:9ms

  	10	100	1000
  foreach	0ms	0ms	9ms
  Iterator	0ms	6ms	30ms

• 结论

      foreach性能遥遥领先于Iterator

• 使用建议

      以后就选foreach了，性能好，写起来也方便。

总结

1. for循环性能在三者的对比中总体落于下风，而且开销递增幅度较大。以后即使在需要使用索引时我宁愿使用递增变量也不会使用for了。
2. Iterator的性能在数组以及链表的表现都是最好的，应该是JAVA的设计者优化过了。在响应时间敏感的情况下(例如web响应)，优先考虑。
3. foreach的性能属于两者之间，写法简单，时间不敏感的情况下我会尽量选用。

    以上就是我对常见数据结构遍历机制的一点比较，虽然只是很初步，但是从中我也学到了很多东西，希望你们也有所收获。

    如果你喜欢本文章，可以收藏阅读，如果你对我的其他文章感兴趣，欢迎到我的博客查看。

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog/post/assorted/4种极大提升学习效率的工具

  近段时间发现身边很多人都在用TUDO List，但是我觉得TUDO List的效率还是不够高，所以就写一下提升学习效率的工具。

TUDO List

​ 因为这阵子真的很多东西做，持续的时间比较长。而且会有时候（大概率）忘掉做某几件事，所以学习效率偏低，直到遇到了TUDO List。

​ TUDO List，可以理解为一个任务清单，它包含了你一天所有要做的事情，而且过一段时间你会发现自己已经依赖上TUDO List管理你的日程。

​ 市面上TUDO List的APP很多，有小黄条，TickTick，Mircosoft To-Do,Google Keep(好像是叫这个名字)，还有很多很多，但是我还是喜欢TickTick。

​ 下面是我TickTick的收集箱。

​ 我觉得TickTick比其他TUDO List好的主要有三点

• 几乎全平台的支持
  • 安卓端是离线app加上联网更新形式，断网都可以继续用
  • 桌面端通过chrome插件提供服务
  • 苹果家的设备就不清楚了（穷）
• 在界面舒适度与易用性取得平衡
  • 小黄条的界面，我就是看了一眼简介的截图就没有下载的欲望
  • Mircosoft家的，我不知道界面怎么样，但是我体验过小娜，我觉得不会好用
  • Google家的，好的，根本不能正常用
• 自带番茄时钟
  • 我觉得现代人都摆脱不了手机（包括我），想认真看书的时候总是想看手机。所以番茄时钟能有效监督学习
  • 自带统计视图，能随时看到当周完成的情况

​ 有利也有弊，弊是有些功能需要付费使用，一个月10来块。始终还是要恰饭的嘛，能理解能理解。付费功能包括TUDO Task的统计，番茄时钟的统计建议。

​ 我对免费的功能已经满足了，所以我不是付费用户，付费解锁功能戳不到我的需求点。

思维导图

​ 不知道有多少读者是在做纸质笔记的，我的话已经很久没有做纸质笔记了。那么平常我在看书的时候，是怎么做笔记的呢。

​ 思维导图，我第一次接触已经爱上它了。

​ 下面是我学习帅张的git相关书籍做的思维导图，虽然过了三个月了，但是我还是可以根据思维导图讲出原书的大概内容。

​ 因为我是比较怕写字的（包括打字），所以我现在只会用思维导图做笔记了。

​ 市面上思维导图的软件很多，有XMind（开源，全平台支持），百度脑图（只有web端），MindMaster（苹果专属），MindLine（国人开发，支持云同步）等等。

​ 我说说我在用的XMind吧，优点有很多

• 模板简洁而且漂亮。即使免费版也内置很多模板，ZEN版本跟Pro版本会更多
• 操作简单。桌面端新建子分支或者兄弟分支会使用到快捷键（我比较少用，但是上手了非常方便），移动端（我常用）主要操作底下四颗按钮完成日常功能
• 支持导出多格式。免费版只支持导出图片以及pdf，PRO版支持更多，但是我觉得这方面日常使用免费版已经足够了。

​ 下面到缺点的部分了。

​ 其实在我看来缺点只有一个，就是不支持云同步，确实有点反人类。

​ 我记得上次我双清平板忘记备份思维导图了（因为平板上独占数据只有思维导图），结果除了之前上传到OneDrive的几个之外，全都没了。。。大概10个上面图片的规模的思维导图吧。。。。

​ 我断断续续找了一个月，找到一个MindLine符合我使用场景之余是支持云同步的，但是界面说实话还有待改进，所以我只能继续用XMind。

Markdown

​ 如果不习惯用思维导图但是又想摆脱纸张的限制，我也可以提供选择。

​ 可能有人已经注意到，这篇文章的风格有点怪怪的。确实，是有点朴素（打死都不承认是怪怪的），因为我是用markdown去写的，具体原因看第二条推文。

​ 效果不截图了，整篇文章都是效果，或者可以去我的博客逛一下，有时间我也会写搭建博客的教程放在博客上。

​ 首先先说一下，markdown是一种标记语言，不是什么软件。具体介绍可以点击查看

​ 在我看来，markdown浑身都是优点

• 操作简单。只需要掌握特定语法就可以写出比word整洁很多的文章，而且可以完全摆脱鼠标（纯文字文章的话）

• 花样很多。markdown原生支持html语言，就是如果你懂html，可以像写网页那样写文章

• 可选编辑器很多。微软家的VSCode，GitHub家的Sublime（实际上也是微软家的），Typora（我在用的，支持实时渲染），有道云笔记，印象笔记等等

• 将主要精力放在思考上。整体风格更加符合思考的习惯，而且摆脱了鼠标的使用，可以将主要精力放在思考上。

  缺点嘛，也有两个，但是都是面对新手的。

• 上手复杂。因为需要特定语法，所以上手需要一个阵痛期，但是practice makes prefect。习惯了之后效率会飞涨。我觉得这个教程不错

• 插入图片比较麻烦，markdown支持三种图片插入方式

  • （不推荐）插入相对目录下的图片，但是需要确保路径的正确
  • （还行，但是不推荐）插入转码后的图片。这个比较麻烦，首先需要将图片转换成Base64字符串，再将字符串复制到markdown底部(转码后的字符串会很长)，再利用语法引用。
  • （推荐）引用图床图片。图床这个不解释了，可以将它理解为一个网络的图片仓库。图床主要有三种
    • 免费的公有图床。百度一搜会很多。不推荐，容易出现图片丢失
    • 免费的私人图床。我所知道的只有微博图床，但是操作上有点麻烦，还行，但是不推荐。
    • 收费的私人图床。简单来说就是自己用OSS搭一个图床，本地上传到云端OSS。七牛云（一定容量免费），阿里云（我在用），腾讯云。七牛云就算了，需要拍身份证。个人推荐阿里云（9块/年）。

云盘

​ 可能很多人bb我：云盘谁没有，某度云盘几个T。

​ 是的，某度云盘确实占领了天朝大部分的市场。但是我想说的是，免费的是最贵的。想想某度的广告，想想几十K的下载速度，我不想吐槽了。

​ 云盘为什么能提升效率呢。

​ 我个人需求是

• 平板是Wifi版的，需要经常带出去，出去的地方大多没有网络或者网络很差
• 平常数据种类多而且量级比较大，而且需要多设备同步
• 需要在线或缓存中阅读pdf

​ 我日常使用情况

• 电脑下载需要看的电子书，直接放在OneDrive文件夹上，Win10自动上传

• 平板脱机缓存电子书，网络环境不允许时可以随时使用电子书

• 在平板上做好XMind之后，上传到OneDrive，需要再继续时下载

​ 所以我OneDrive是这样子的。

​ 通过OneDrive，我的数据能随时同步而且不丢失（再次为我丢失的思维导图伤心。。。）

​ 市面上有很多很多云盘。有我们能用到的，也有我们用不到的:OneDrive,某度云盘，亚马逊，iCloud，Google Drive，坚果云等等。

​ 苹果党，iCloud；

​ Win10党，OneDrive(虽然免费空间只有5G，但是好用，我愿意付费);

​ 有特殊手段的安卓党，Google Drive；

​ 数据量大且不常使用，某度还是可以选择一下的；

​ 以上几款软件都是开源或者免费+付费形式的。免费的部分基本上够用了，付费也在承受范围之内（真希望XMind出一个云同步的功能，我绝对付费）。

题外话：

​ 这段时间在混帅张的星球，受到了很多启发。关于软件跟知识是否付费的争论，我是站在付费的那一边。

​ 曾经在星球上面看到一个观点：免费是最贵的。软件都是程序猿一块块砖搬出来的，也是有成本的。免费使用，意味着在某些方面软件开发方是赚钱的，广告，流量，会员等等。

​ 自己本身也是学编程的，明白写程序是很辛苦的。免费产品我是不排斥的，没人嫌钱多。付费产品？我也愿意付费的，前提是有足够理由让我付费以及我能承担起这个费用。

​ 盗版我是不提倡的，但是有时候超出我的承受范围，我会选择某宝。而且盗版可能有一部分功能缺失掉了，恰好缺失的功能能极大提高你的效率。

​ 再次希望以上几款软件能对你们有帮助！

​

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog

当修改gitnore文件后，常常出现文件不生效的情况，是因为之前的修改已经提交到暂存区上了。
解决方法

1
2
3

git add .     //防止已有修改还没到暂存区的情况
git rm -r --cached .  //清除暂存区记录
git add . //提交修改记录到暂存区中

执行到第三步即能使gitnore文件生效，后续操作会按照gitnore规则执行

    本文首发于cartoon的博客

    转载请注明出处:https://cartoonyu.github.io/cartoon-blog

今天在做leetcode的时候，遇到了运算符的不同而导致结果不一致的问题。记录一下提醒自己

中文名称与英文名称

&：按位与(Bitwise and)
&&：逻辑与(logical and)
|：按位或(Bitwise or)
||：逻辑或(logical or)

区别

若第一个条件就可以决定表达式的值，逻辑运算符不会继续检查后续条件，而位运算符则会全部检查。