- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章浅谈普通for循环遍历LinkedList弊端由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
java开发过程中,用到的最多的List集合就属ArrayList与LinkedList。对于ArrayList的遍历,通常是下面的方法:
1
2
3
4
5
6
7
8
9
10
|
public
static
void
main(String[] args)
{
List<Integer> arrayList =
new
ArrayList<Integer>();
for
(
int
i =
0
; i <
100
; i++)
arrayList.add(i);
for
(
int
i =
0
; i <
100
; i++)
System.out.println(arrayList.get(i));
}
|
假如集合换成LinkedList,可能我们就会用相同得方法进行遍历,如下:
1
2
3
4
5
6
7
8
9
10
|
public
static
void
main(String[] args)
{
List<Integer> linkedList =
new
LinkedList<Integer>();
for
(
int
i =
0
; i <
100
; i++)
linkedList.add(i);
for
(
int
i =
0
; i <
100
; i++)
System.out.println(linkedList.get(i));
}
|
请记住:这是一种非常糟糕的做法。这其实已经不是Java的问题,而是数据结构的问题了,我相信语言从Java换成其他的也都一样.
下面对ArrayList和LinkedList的普通for循环效率进行测试以及分析原因.
ArrayList和LinkedList使用普通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
|
public
class
ListIteratorTest
{
private
final
static
int
LIST_SIZE =
1000
;
public
static
void
main(String[] args)
{
List<Integer> arrayList =
new
ArrayList<Integer>();
List<Integer> linkedList =
new
LinkedList<Integer>();
for
(
int
i =
0
; i < LIST_SIZE; i++)
{
arrayList.add(i);
linkedList.add(i);
}
long
startTime = System.currentTimeMillis();
for
(
int
i =
0
; i < arrayList.size(); i++)
arrayList.get(i);
System.out.println(
"ArrayList遍历速度:"
+ (System.currentTimeMillis() - startTime) +
"ms"
);
startTime = System.currentTimeMillis();
for
(
int
i =
0
; i < linkedList.size(); i++)
linkedList.get(i);
System.out.println(
"LinkedList遍历速度:"
+ (System.currentTimeMillis() - startTime) +
"ms"
);
}
}
|
不断增大LIST_SIZE,我用表格表示一下运行结果:
。
1000 | 5000 | 10000 | 50000 | 100000 | |
ArrayList | 0ms | 1ms | 2ms | 3ms | 3ms |
LinkedList | 3ms | 16ms | 88ms | 2446ms | 18848ms |
。
下面解释一下产生此现象的原因。从运行结果我们看到,按倍数增大List容量,ArrayList的遍历显得比较稳定,而LinkedList的遍历几乎是爆发式的增长,再测试下去已经没有必要了.
。
ArrayList使用普通for循环遍历快的原因 。
。
先看一下ArrayList的get方法源代码:
1
2
3
4
5
|
public
E get(
int
index) {
RangeCheck(index);
return
(E) elementData[index];
}
|
看到ArrayList的get方法只是从数组里面拿一个位置上的元素罢了。我们有结论,ArrayList的get方法的时间复杂度是O(1),O(1)的意思也就是说时间复杂度是一个常数,和数组的大小并没有关系,只要给定数组的位置,直接就能定位到数据.
其实熟悉C、C++或者对指针理解的朋友一定很好理解为什么,我解释一下为什么对数组使用get就快.
在计算机底层,数据都是有地址的,就像人有住址一样。假设我写了这么一句代码:
1
|
int
[
3
] ints = {
1
,
3
,
5
};
|
在Java中一个int型数据是4个字节,此时计算机内部做的事情是,在内存空间中找到一块连续的、足以存放3个4字节也就是12字节的数组的内存空间,并返回该内存空间的首地址。比方说该内存空间的首地址是0x00吧,那么那么1就放在0x00~0x03中、3就放在0x04~0x07中、5就放在0x08~0x0B中.
这时就很简单了,取ints[1]的时候,计算机就会算出ints[1]的数据是存放在以0x04开头,占据4个字节空间的内存中,因此,计算机会从0x04~0x07这块地址空间中读取数据出来.
整个过程,和数组有多大,并没有关系,计算机做的只是算出起始地址-->去该地址中取数据而已,因此我们看到使用普通for循环遍历ArrayList的速度很快,也很稳定.
LinkedList使用普通for循环遍历慢的原因 。
再看一下LinkedList的get方法做了什么:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public
E get(
int
index) {
return
entry(index).element;
}
Node<E> node(
int
index) {
// assert isElementIndex(index);
if
(index < (size >>
1
)) {
Node<E> x = first;
for
(
int
i =
0
; i < index; i++)
x = x.next;
return
x;
}
else
{
Node<E> x = last;
for
(
int
i = size -
1
; i > index; i--)
x = x.prev;
return
x;
}
}
|
由于LinkedList是双向链表,因此第4行的意思是算出i在一半前还是一半后,一半前正序遍历、一半后倒序遍历,这样会快很多,当然,先不管这个,分析一下为什么使用普通for循环遍历LinkedList会这么慢.
原因就在第6~第7行,第11~第12行的两个for循里面,以前者为例:
1、get(0),直接拿到0位的Node0的地址,拿到Node0里面的数据 。
2、get(1),直接拿到0位的Node0的地址,从0位的Node0中找到下一个1位的Node1的地址,找到Node1,拿到Node1里面的数据 。
3、get(2),直接拿到0位的Node0的地址,从0位的Node0中找到下一个1位的Node1的地址,找到Node1,从1位的Node1中找到下一个2位的Node2的地址,找到Node2,拿到Node2里面的数据.
后面的以此类推.
也就是说,LinkedList在get任何一个位置的数据的时候,都会把前面的数据走一遍。假如我有10个数据,那么将要查询1+2+3+4+5+5+4+3+2+1=30次数据,相比ArrayList,却只需要查询10次数据就行了,随着LinkedList的容量越大,差距会越拉越大。其实使用LinkedList到底要查询多少次数据,大家应该已经很明白了,来算一下:按照前一半算应该是(1 + 0.5N) * 0.5N / 2,后一半算上即乘以2,应该是(1 + 0.5N) * 0.5N = 0.25N2 + 0.5N,忽略低阶项和首项系数,得出结论,LinikedList遍历的时间复杂度为O(N2),N为LinkedList的容量.
时间复杂度有以下经验规则:
O(1) < O(log2N) < O(n) < O(N * log2N) < O(N2) < O(N3) < 2N < 3N < N.
前四个比较好、中间两个一般、后3个很烂。也就是说O(N2)是相对糟糕的一种时间复杂度了,N大一点,程序就会执行得比较慢.
后记 。
切记一定不要使用普通for循环去遍历LinkedList。使用迭代器或者foreach循环(foreach循环的原理就是迭代器)去遍历LinkedList即可,这种方式是直接按照地址去找数据的,将会大大提升遍历LinkedList的效率.
以上这篇浅谈普通for循环遍历LinkedList弊端就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我.
最后此篇关于浅谈普通for循环遍历LinkedList弊端的文章就讲到这里了,如果你想了解更多关于浅谈普通for循环遍历LinkedList弊端的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 5 年前。
DBMS 供应商使用 SQL 方言特性来区分他们的产品,同时声称支持 SQL 标准。 'Nuff 说。 您编写的任何 SQL 示例是否无法转换为 SQL:2008 标准 SQL? 具体来说,我说的是
多年来,我一直在考虑这个问题,但从未成功实现过。我说的是一个快速、高效的 C 函数,它在输入中接受一个整数值(例如 16 位),并在输出中给出完全不同的相同位大小的数字,但“考虑到”所有数字已经给出了
当标准 iPhone UI 控件变得过于平淡,并且您希望简单的记分应用程序通过颜色、动画、非标准 GUI 字体和背景壁纸等流行时。 ,为这样的事情集成游戏引擎有意义吗? 我对 Unity3D 和 To
这是我的第一个问题,所以如果我没有正确地标记标签,我很抱歉。我尝试过...这是我的问题:我希望有人能告诉我如何为普通的表格 View 创建 2 行节标题。我遇到的问题是:1)我找不到可以模仿默认 1
所以我一直在开发一个仅使用普通 JavaScript 的“非常简单”的计算器。但我不知道为什么它现在起作用了。 这是我的 JavaScript 和 HTML 代码: (function() { "
我正在尝试编写一个函数来满足以下要求: 给定一个对象和一个键,“getElementsThatEqual10AtProperty”返回一个数组,其中包含位于给定键处等于 10 的数组的所有元素。 注释
[最终编辑:我觉得有必要做出回应,因为我从这篇文章中学到了很多东西(主要是通过你们,我花了更多的时间来理解CSS..但最后,我真的不知道如何为了使这项工作有效..除了真正破坏html的基本结构..我不
我希望能够将一个函数附加到一个元素上,该函数只有在该元素上单击指定时间后才会运行。 有几个( 1 、 2 、 3 )与在 javascript 中处理鼠标保持相关的问题;但这些问题要么使用 jQuer
我想将泛型函数保存为变量: (defvar *gf* (make-instance 'standard-generic-function) 但是在添加方法时,我必须自己定义call-next-meth
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 7 年前。
我有一个普通的 tableView——一个部分——当我滚动时,行出现在标题后面。像这样: 有没有简单的方法来防止这种情况?我认为它与 contentInset 有关,但这也会移动标题,这不是我想要的。
你好,我有一个ajax表单,它返回一个控制“发送”动画的脚本。然而,当淡入开始时,它会停止在 0.1 不透明度。我不确定脚本中有什么问题。任何帮助将不胜感激。 quote_form = documen
这是演示我的问题的代码笔:http://codepen.io/PiotrBerebecki/pen/yaWQwZ 目标是当用户点击时有滚动动画 顶部导航链接,以及 Back to Top 按钮在右下角
在我重新发明轮子之前,纯Java中有类似主题的并发队列吗?我有以下要求: 多个读者/消费者 多名作家/制片人 每条消息都必须由每个(活跃的)消费者消费 在每个消费者阅读一条消息后,它应该变成垃圾(即不
这个问题与 Do MySQL tables need an ID? 有一个无意义的auto_incremental ID作为一个表的PRIMARY KEY,那么我创建其他KEY时,我是否应该在KEY中
我有一个普通 UITableView 并且我想隐藏分隔符。为了隐藏它,我尝试使用以下属性: 我也在 viewDidLoad 中设置了它。 self.tableView.separatorStyle =
var vettore = document.getElementById(id_form).elements; for (var i = 0; i '+vettore_nomi_file[i]; 最
我已经构建了一个非常简单的轮播,但有一个问题。在我的轮播中,我有三张幻灯片,一个上一个按钮和一个下一个按钮。我想要的是当我单击下一个按钮并在最后一张幻灯片上转到第一张幻灯片时。此外,当我单击上一个按钮
我是 javascript 的新手,所以我需要一些帮助。 我正在尝试制作一个简单的插件(当然只是为了学习,以便更好地理解事物),但我遇到了一些麻烦,我将不胜感激。 我的插件是基本的,我正在尝试为 sc
我是一名优秀的程序员,十分优秀!