`
azvf
  • 浏览: 146453 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

JAVA容器效率深度分析List

 
阅读更多

本文中的测试代码来源于《think in java》第四版

附件中有测试代码

1、各种List的各种操作的耗时

size:每一个list的元素数量,从10到10W

 

操作:add增加到list末端,get随机访问,set修改某个元素值,insert在list中间插入(代码中只是插入到了第五个元素,放大了随机插入的操作时间),rmMiddle从list中间删除元素(代码中是删除了第五个元素,放大了从list.size()/2的操作时间,rmLast从list末端删除,rmFirst从list首部删除

 

操作时间:是指每一次操作所用的时间,单位纳秒

 

环境:64bit JDK7

 

ArrayList和Vector都是基于数组实现的,区别就是Vector是同步的,以下将统称为“数组list”

2、分析

2.1 add操作,数组和链表旗鼓相当

首先,当list仅有10个元素的add耗时,要大于100/1k/1w/10w元素的add耗时,这里可能是因为“JIT的热点优化”导致。可以通过增加循环次数来验证,在我的机器上:“往一个list增加10个元素”,循环13W次时,每次的操作耗时降到 2位数

其次,比较数组list和链表list,向末端增加时,操作耗时几乎不随着list元素数变化而变化。

 

数组元素add时的扩容动作最终调用的方法:

    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

 无疑,native方法System.arraycopy的效率是高的,几乎不随list.size()变化而变化。

 

因为System.arraycopy的高效,在这里不得不提到一点,链表在add操作时比数组list要复杂的多(LinkedList是双向链表),当list.size()数量超过百万时,链表的add可能就会比数组add要慢,这一点有待验证。

 

2.2get随机访问,数组完胜

数组list的get耗时,在list.size()增长时,无变化

链表list的get耗时,在list.size()增长时,性能下降。

 

值得一提的就是jdk5中遍历操作的foreach写法,如下:

 

   for (String x : list) { 
            System.out.println(x); 
        } 

此种写法是基于集合的iterator迭代器,只要是实现了Iterable接口的类,均可使用此种写法。数组的迭代器访问,本质还是基于数组的随机访问,和get随机访问比,将无变化。而链表的迭代器访问,与get随机访问相比,性能将有大幅度提升,应该和数组的随机访问差不多,而且不会因为list.size()的增长而导致系能下降

 

2.3set修改,数组完胜

修改操作,数组list不随size增大而导致效率降低,链表则随着list.size()增大导致效率降低,看链表set源码

 

    public E set(int index, E element) {
        //查找Entry
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
    }

    private Entry<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;//从header开始
        //index小于size一半,则向后遍历,否则向前遍历
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }
 

 

也就是说,每次set时候,都会从header向前或向后遍历链表。由此可以想到,修改第"list.size/2"个元素,则是代价最大的修改。

 

2.4 insert插入,链表完胜数组

1)无论链表还是数组,insert操作的效率将会随着list.size()的增大而降低

2)数组需要将insert元素,以后的元素,整体后移动

    public void add(int index, E element) {
	if (index > size || index < 0)
	    throw new IndexOutOfBoundsException(
		"Index: "+index+", Size: "+size);

	ensureCapacity(size+1);  // Increments modCount!!
	System.arraycopy(elementData, index, elementData, index + 1,
			 size - index);
	elementData[index] = element;
	size++;
    }

 

2.5 remove删除,链表小胜

    public E remove(int index) {
	RangeCheck(index);

	modCount++;
	E oldValue = (E) elementData[index];

	int numMoved = size - index - 1;
	if (numMoved > 0)
	    System.arraycopy(elementData, index+1, elementData, index,
			     numMoved);
	elementData[--size] = null; // Let gc do its work

	return oldValue;
    }

 数组list每次删除都有System.arraycopy操作,因此效率最低的应该是remove first删除list中的第一个元素。耗时最少的删除是remove last删除最后一个元素。

链表则无论是第一个删除、中间删除、末尾删除,都无需考虑效率问题,而且,删除效率不随list.size()增大而降低

如果是从末尾删除,数组甚至比链表要快。

 

结论:List中首选Arraylist,基于数组实现list平均性能是最好的,如果有大量的insert或者从首部/中部删除元素的操作,则应该选择LinkedList

其实LinkedList作为队列、堆栈来操作,无疑,应该是首选,效率够高

 

 

  • 大小: 278.3 KB
分享到:
评论

相关推荐

    java深度历险+深入java虚拟机

    《Java深度历险》与《深入Java虚拟机》是两本深受Java开发者喜爱的经典书籍,它们涵盖了Java编程语言和Java虚拟机(JVM)的高级主题,旨在帮助读者深入理解Java平台的工作原理。 《Java深度历险》这本书通常会涵盖...

    Java深度历险

    Java集合框架是处理数据结构和算法的关键,包括List、Set、Map等各种接口及其实现类,以及并发容器和Stream API。掌握这些内容,能有效提高代码的可读性和效率。 最后,JVM(Java虚拟机)的内部工作原理也是《Java...

    java容器超详细

    Java容器,也被称为Java集合框架(Java Collection Framework,...Java容器的深度学习需要理解每个接口和类的特点、适用场景以及它们之间的关系。通过熟练掌握Java容器,开发者可以编写出更高效、更易于维护的代码。

    王森 Java深度历险

    《王森 Java深度历险》是一本深受Java开发者喜爱的技术专著,旨在带领读者深入探索Java编程的世界。这本书详尽地讲解了Java的核心概念、高级特性以及实际开发中的最佳实践,帮助读者提升对Java语言的理解和应用能力...

    java深度历险_继

    《Java深度历险》是王森撰写的一本深入讲解Java编程技术的书籍,它旨在帮助读者从基础到高级,全面掌握Java的核心概念和技术。这里我们主要探讨Java编程中的关键知识点,包括但不限于类与对象、继承、多态性、异常...

    Java深度历险(重要必读)

    Java深度历险是一本专为Java开发者准备的深入学习书籍,尤其对于想要探索Java语言精髓的程序员来说,这本书无疑是一份宝贵的参考资料。虽然书中的文字是繁体字,但这并不影响我们理解其中所涵盖的丰富Java知识。在这...

    java深度体验

    《Java深度体验》一书,正如其标题所示,是一本旨在带领读者深入探索Java编程语言的著作。在Java的世界里,深度体验意味着不仅要掌握基本语法,还要理解其背后的原理,以及如何利用这些知识来解决实际问题。这本书...

    java 深度历险

    《Java深度历险》是王森撰写的一本深入探讨Java编程技术的书籍,它涵盖了Java语言的核心特性、高级特性和实战应用。这本书旨在帮助读者从初级程序员晋升为Java开发的高手,通过深入学习和理解,提升编程技能和解决...

    C、C++、JAVA数据结构与算法电子书

    - **STL(Standard Template Library)**:提供容器(如vector、list)、迭代器、算法和函数对象,极大地简化了数据结构和算法的实现。 - **模板**:允许创建泛型代码,适用于多种数据类型。 4. **Java特有**: ...

    清华大学 Java程序设计_郑莉老师_java课件

    Java程序设计是计算机科学中的重要课程,尤其在清华大学这样的顶级学府中,其教学质量与深度备受业界关注。郑莉老师是这门课程的主讲教师,她以其深厚的学术背景和丰富的教学经验,引领学生们深入理解Java语言的核心...

    thingking in java第三版

    《Thinking in Java》是Bruce Eckel的经典之作,被誉为学习Java编程的权威指南。...通过阅读和实践书中的例子,你可以提升自己的编程技能,理解Java编程的深度和广度,为解决实际问题打下坚实基础。

    很少见的Java经典代码

    "很少见的Java经典代码"这个主题可能包含了那些在实际开发中并不常见,但极具技术深度或者巧妙解决问题的代码示例。这些代码可能是解决特定问题的独特方法,或者是优化性能的关键技巧。下面我们将探讨一些可能包含在...

    Java开发手册1.5.rar

    这份压缩包包含的主要文件是《Java开发手册1.5.pdf》,这是一本全面且深度讲解Java编程的电子书。 在Java开发过程中,遵循一定的规范至关重要,因为这直接影响到代码的可读性、可维护性和团队协作效率。手册中可能...

    非常全的java面试题+编程题(2个文档)

    在IT行业中,Java是一种广泛应用的高级编程语言,尤其在企业级应用开发中占据了主导地位。这份压缩包包含的“JAVA编程题全集(50题及答案).doc”和“Java面试题(附答案).doc”是针对Java程序员准备的面试资源,涵盖了...

    Java疯狂讲义教程

    《Java疯狂讲义教程》是一本深度探讨Java编程语言的教材,主要针对初学者和有一定基础的开发者。这本书涵盖了从基础语法到高级特性的全面内容,旨在帮助读者深入理解Java编程,提升技能水平。源码和课后习题解析的...

    Java编程艺术.rar

    《Java编程艺术》是一本深度探讨Java编程技术与实践的书籍,旨在提升程序员的设计和代码编写技巧。在Java这个广泛使用的编程语言中,理解和掌握这些艺术对于任何开发者来说都至关重要。下面,我们将深入讨论Java编程...

    thinking in java(一本学java必看的书)

    六、Java集合框架深度探索 1. Map接口:HashMap、TreeMap等实现了键值对存储,各有其性能特点和适用场景。 2. Set接口:HashSet、LinkedHashSet、TreeSet等提供了不同的元素唯一性保证和排序规则。 3. List接口:...

    Java算法题,数据结构分析和实现.zip

    7. **集合(Collection)**:Java的`java.util.Collection`接口是所有集合类的父接口,包括单值容器如`Set`和多值容器如`List`。`Set`不允许重复元素,而`List`保持元素顺序。 8. **树(Tree)**:二叉树是一种重要...

Global site tag (gtag.js) - Google Analytics