sorce来了,确实ArrayList是有交换操作,看swap(list, i, j);方法 public static void reverse(List<?> list) { int size = list.size(); if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) { for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) swap(list, i, j); } else { ListIterator fwd = list.listIterator(); ListIterator rev = list.listIterator(size); for (int i=0, mid=list.size()>>1; i<mid; i++) { Object tmp = fwd.next(); fwd.set(rev.previous()); rev.set(tmp); } } }
从我的实验,以及6F的代码来看,都应该是ArrayList,虽然和我的第一感觉相反。 int length = 1000000; List<Integer> list = new ArrayList<Integer>(length); // or new LinkedList<Integer>(); for (int i = 0; i < length; i++) { list.add(i); } long start = System.currentTimeMillis(); for (int i = 0; i < 100; i++) { Collections.reverse(list); } long end = System.currentTimeMillis(); System.out.println(end - start);ArrayList在我的电脑上平均在4秒左右,而LinkedList在5秒左右@Justlearn,ArrayList用Swap,其实LinkedList也是Swap,次数都是 size/2 次(每次一对) 但是,由于ArrayList只是简单的i++,j--,并调用set方法(基本上就是引用数组下标),而LinkedList基于两个ListIterator,且每次都必须调用fwd.next(), fwd.previous(),这两个操作本身就已经包含了iterator指针的swap操作 public E next() { checkForComodification(); if (nextIndex == size) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } public E previous() { if (nextIndex == 0) throw new NoSuchElementException(); lastReturned = next = next.previous; nextIndex--; checkForComodification(); return lastReturned.element; }由于这里没有涉及到插入,而逆序对于两者都是要对所有元素的位置/指针进行调整,所以ArrayList的速度并不慢。不知分析的有没有纰漏。
int size = list.size();
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
int length = 1000000;
List<Integer> list = new ArrayList<Integer>(length); // or new LinkedList<Integer>();
for (int i = 0; i < length; i++) {
list.add(i);
}
long start = System.currentTimeMillis();
for (int i = 0; i < 100; i++) {
Collections.reverse(list);
}
long end = System.currentTimeMillis();
System.out.println(end - start);ArrayList在我的电脑上平均在4秒左右,而LinkedList在5秒左右@Justlearn,ArrayList用Swap,其实LinkedList也是Swap,次数都是 size/2 次(每次一对)
但是,由于ArrayList只是简单的i++,j--,并调用set方法(基本上就是引用数组下标),而LinkedList基于两个ListIterator,且每次都必须调用fwd.next(), fwd.previous(),这两个操作本身就已经包含了iterator指针的swap操作 public E next() {
checkForComodification();
if (nextIndex == size)
throw new NoSuchElementException(); lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.element;
} public E previous() {
if (nextIndex == 0)
throw new NoSuchElementException(); lastReturned = next = next.previous;
nextIndex--;
checkForComodification();
return lastReturned.element;
}由于这里没有涉及到插入,而逆序对于两者都是要对所有元素的位置/指针进行调整,所以ArrayList的速度并不慢。不知分析的有没有纰漏。
or google
java arraylist linkedlist reverse performance
谢谢lz提这个问题。也谢谢高手的分析。
ArrayList 查快改慢逆序的话个人理解是linkedList快
link查慢改快
我觉得是linkedlist效率高
public static void reverse(List<?> list) {
int size = list.size();
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) 是数组实现或集合长度小于16时,第一个和最后一个交换,第二个和倒数第二个交换,以些类推。
RandomAccess:随机访问接口,数组的实现才支持随机访问。而链表的实现LinkedList是不支持此接口的。
链表的get(i)必须从头指针开始,移动i-1次到指定的位置,当然链表里元素个数较大的时候,不停的移动增加了复杂度。所以采用ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
前移后移来实现,是为了降低移动指针的复杂度。swap(list, i, j);是交换两个元素的引用
fwd.set(rev.previous()); rev.set(tmp);也是交换的元素的引用。所以前面很多说数组交换的是值,链表交换的是引用的说法是不正确的。
综合起来看数组reverse稍快些,但差别不太大,因为是同一个复杂度等级。
LinkedList 用链表实现;查找慢,插入或删除快;就这个问题,理论上应该是LinkedList快些;
你的理论有点错误,数组是采用内存首地址与索引偏移量决定的,这样的定位操作是非常快的。如果需要遍历整个 List,那使用下标迭代 ArrayList 的性能要超过迭代器迭代 LinkedList 的性能。逆转 List 这两种 List 的性能差别主要就体现在遍历的速度上。
果然ArrayList耗费时间要少一点
但是ArrayList只需要swap length/2次,而LinkedList则需要修改2*length个指针(LinkedList是双向链表)
后来才看你们的回复 结果就是差不多
那些移动数组的童鞋不知道写过算法没
可能还慢慢移动么 直接弄一个占空间(或可变空间) 然后每个轮着复制过去
速度很快
当然基于指针就是地址的值得 也不会很慢
两者都是一次赋值:一个是赋值去新地方 一个是赋新地址去LIST 速度能差很远
那个外国的不知道搞什么的 我就不去看了 不可能差150倍吧 除非底层对ARRAYLIST很给力
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}linkedList这个移动N次ArrayListl.set(i, l.set(j, l.get(i)));也是n次但是ArrayList的实现代码行少些,代码的多少也是决定速度的;