巨型链表的遍历
Traversal of Giant LinkedList
对于一个项目,我需要编写一个方法,使用 listIterator 遍历一个包含 500 万个随机整数的 LinkedList,然后使用 LinkedList 的 get(index) 方法。
我用 listIterator 遍历它没有问题,它在大约 75 毫秒内完成。但是,在尝试对 500 万个整数进行 get 方法遍历之后,我只是在 1.5 小时左右停止了 运行。
我使用的 getTraverse 方法类似于下面的代码(但是我的方法与 class 中的其他方法分组并且是非静态的,但工作方式相同)。
public static long getTraverse(LinkedList<Integer> list) {
long start = System.currentTimeMillis();
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i);
}
long stop = System.currentTimeMillis();
return stop - start;
}
这对于大小为 50、500、5000、50000 的整数链表非常有效,花了很长时间但完成了 500000。
我的教授在指导时往往非常含糊,在提出问题时非常无益。所以,我不知道我的代码是否被破坏,或者他是否被指南中的整数冲昏了头脑。欢迎任何意见。
一个LinkedList
针对插入进行了优化,这是一个常量时间操作。
搜索 LinkedList
需要您遍历每个元素以找到您想要的元素。您将索引提供给 get
方法,但在幕后它正在遍历列表到该索引。
如果您添加一些打印语句,您可能会发现前 X 个元素的检索速度非常快,并且随着时间的推移,随着您对列表中更靠下的元素进行索引,检索速度会变慢。
ArrayList
(由数组支持)针对检索进行了优化,可以在恒定时间内索引所需的元素。尝试更改您的代码以使用 ArrayList
并查看 get
运行速度有多快。
想想 LinkedList
是如何实现的——作为一个节点链——你会发现要到达一个特定的节点,你必须从头开始并遍历到那个节点。
您正在 LinkedList
n 次调用 .get()
,这需要遍历列表直到到达该索引。这意味着您的 getTraverse()
方法需要 O(n^2)(或二次)时间,因为对于每个元素,它必须遍历列表的(部分)。
正如 Elliott Frisch 所说,我怀疑您发现的正是您的导师希望您发现的东西 - 不同的算法可能具有截然不同的运行时间,即使原则上它们做同样的事情。
对于一个项目,我需要编写一个方法,使用 listIterator 遍历一个包含 500 万个随机整数的 LinkedList,然后使用 LinkedList 的 get(index) 方法。
我用 listIterator 遍历它没有问题,它在大约 75 毫秒内完成。但是,在尝试对 500 万个整数进行 get 方法遍历之后,我只是在 1.5 小时左右停止了 运行。
我使用的 getTraverse 方法类似于下面的代码(但是我的方法与 class 中的其他方法分组并且是非静态的,但工作方式相同)。
public static long getTraverse(LinkedList<Integer> list) {
long start = System.currentTimeMillis();
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i);
}
long stop = System.currentTimeMillis();
return stop - start;
}
这对于大小为 50、500、5000、50000 的整数链表非常有效,花了很长时间但完成了 500000。
我的教授在指导时往往非常含糊,在提出问题时非常无益。所以,我不知道我的代码是否被破坏,或者他是否被指南中的整数冲昏了头脑。欢迎任何意见。
一个LinkedList
针对插入进行了优化,这是一个常量时间操作。
搜索 LinkedList
需要您遍历每个元素以找到您想要的元素。您将索引提供给 get
方法,但在幕后它正在遍历列表到该索引。
如果您添加一些打印语句,您可能会发现前 X 个元素的检索速度非常快,并且随着时间的推移,随着您对列表中更靠下的元素进行索引,检索速度会变慢。
ArrayList
(由数组支持)针对检索进行了优化,可以在恒定时间内索引所需的元素。尝试更改您的代码以使用 ArrayList
并查看 get
运行速度有多快。
想想 LinkedList
是如何实现的——作为一个节点链——你会发现要到达一个特定的节点,你必须从头开始并遍历到那个节点。
您正在 LinkedList
n 次调用 .get()
,这需要遍历列表直到到达该索引。这意味着您的 getTraverse()
方法需要 O(n^2)(或二次)时间,因为对于每个元素,它必须遍历列表的(部分)。
正如 Elliott Frisch 所说,我怀疑您发现的正是您的导师希望您发现的东西 - 不同的算法可能具有截然不同的运行时间,即使原则上它们做同样的事情。