【优雅代码】13-linkedList插入真的比arrayList快么

2022年01月14日 阅读数:1
这篇文章主要向大家介绍【优雅代码】13-linkedList插入真的比arrayList快么,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

【优雅代码】13-linkedList插入真的比arrayList快么

欢迎关注b站帐号/公众号【六边形战士夏宁】,一个要把各项指标拉满的男人。该文章已在github目录收录。
屏幕前的大帅比大漂亮若是有帮助到你的话请顺手点个赞、加个收藏这对我真的很重要。别下次必定了,都不关注上哪下次必定。java

1.背景

在学习中,常规的方法老是先去模仿,硬性的接收知识,可是实际状况每每出人意料,等到构建起大致框架后再去探寻实际状况git

1.插入比较

为了不其它差别,以一样的方式进行循环github

public static void addCompare() {
    List<Integer> listArray = IntStream.range(0, 10000).boxed().collect(Collectors.toList());
    // 由于链表数组没有初始大小的因此不建立
    ArrayList<Integer> arraysListHeadNon = new ArrayList<>();
    ArrayList<Integer> arraysListHead = new ArrayList<>(listArray.size());
    ArrayList<Integer> arraysListTailNon = new ArrayList<>();
    ArrayList<Integer> arraysListTailHead = new ArrayList<>(listArray.size());
    LinkedList<Integer> linkedListHeadNon = new LinkedList<>();
    LinkedList<Integer> linkedListTailNon = new LinkedList<>();
    StopWatch sw = new StopWatch();
    sw.start("不带初始化大小arrayList的尾插");
    listArray.stream().forEach(s -> arraysListTailNon.add(s));
    sw.stop();
    sw.start("带初始化大小arrayList的尾插");
    listArray.stream().forEach(s -> arraysListTailHead.add(s));
    sw.stop();

    sw.start("链表头插");
    listArray.stream().forEach(s -> linkedListHeadNon.addFirst(s));
    sw.stop();
    sw.start("链表尾插");
    listArray.stream().forEach(s -> linkedListTailNon.add(s));
    sw.stop();
    System.out.println(sw.prettyPrint());
}

能够看到,头插的arrayList太慢了直接去掉,而后发现带初始化的arrayList仍是要快一点json

001411100  035%  不带初始化大小arrayList的尾插
000776200  020%  带初始化大小arrayList的尾插
000952100  024%  链表头插
000840500  021%  链表尾插

2.addAll比较

我的认为addAll的状况出现主要源于,ArrayList走的是native的复制因此更快数组

public static void addAllCompare(){
    List<Integer> listArray = IntStream.range(0, 10000).boxed().collect(Collectors.toList());
    List<Integer> listLinked= new LinkedList<>(listArray);

    StopWatch sw = new StopWatch();
    sw.start("arrayListAddAllArray");
    new ArrayList<>(listArray);
    sw.stop();

    sw.start("linkedListAddAllArray");
    new LinkedList<>(listArray);
    sw.stop();

    sw.start("arrayListAddAllLinked");
    new ArrayList<>(listLinked);
    sw.stop();

    sw.start("linkedListAddAllLinked");
    new LinkedList<>(listLinked);
    sw.stop();
    // 我的认为addAll的状况出现主要源于,ArrayList走的是native的复制因此更快
    System.out.println(sw.prettyPrint());
}
000037172  002%  arrayListAddAllArray
000811717  041%  linkedListAddAllArray
000237292  012%  arrayListAddAllLinked
000913354  046%  linkedListAddAllLinked

3.循环速度比较

能够看出不一样的方式循环速度上略有差别,整体上链表的确是要更快,但随着数据量的增长arrayStream的方式优点愈来愈明显最终最快。
而在循环方式上迭代器基本都是最优的框架

public static void foreachCompare() {
    List<Integer> listArray = IntStream.range(0, 10000).boxed().collect(Collectors.toList());
    ArrayList<Integer> arrays = new ArrayList<>(listArray);
    LinkedList<Integer> linked = new LinkedList<>(listArray);
    StopWatch sw = new StopWatch();
    sw.start("arraysStream");
    arrays.forEach(Integer::getClass);
    sw.stop();

    sw.start("linkedStream");
    linked.forEach(Integer::getClass);
    sw.stop();

    sw.start("arraysForEach");
    for (Integer array : arrays) {
        array.getClass();
    }
    sw.stop();
    sw.start("linkedForEach");
    for (Integer array : linked) {
        array.getClass();
    }
    sw.stop();
    sw.start("arraysIterator");
    Iterator<Integer> iteratorArray = arrays.iterator();
    while (iteratorArray.hasNext()){
        iteratorArray.next().getClass();
    }
    sw.stop();
    sw.start("arraysLinked");
    Iterator<Integer> iteratorLinked = arrays.iterator();
    while (iteratorLinked.hasNext()){
        iteratorLinked.next().getClass();
    }
    sw.stop();
    System.out.println(sw.prettyPrint());
}
006974600  012%  arraysStream
011748900  019%  linkedStream
015315300  025%  arraysForEach
009445800  016%  linkedForEach
008187400  014%  arraysIterator
008792100  015%  arraysLinked

10000的输出状况less

001787856  020%  arraysStream
002100260  023%  linkedStream
001649966  018%  arraysForEach
001189238  013%  linkedForEach
001229047  014%  arraysIterator
001111209  012%  arraysLinked

100的输出状况ide

000372500  050%  arraysStream
000265300  035%  linkedStream
000037700  005%  arraysForEach
000027500  004%  linkedForEach
000024800  003%  arraysIterator
000023100  003%  arraysLinked