我有一个操作非常大的列表的功能,超过大约250,000个项目.对于大多数这些项目,它只是替换位置x处的项目.但是,对于它们中的大约5%,它必须从列表中删除它们.
使用LinkedList似乎是避免昂贵删除的最明显的解决方案.然而,自然地,随着时间的推移,通过索引访问LinkedList变得越来越慢.这里的成本是几分钟(其中很多).
在LinkedList上使用Iterator也很昂贵,因为我似乎需要一个单独的副本来避免在编辑该列表时出现Iterator并发问题.这里的费用是几分钟.
然而,这是我的思绪被吹嘘的地方.如果我更改为ArrayList,它几乎立即运行.
对于包含297515个元素的列表,删除11958个元素并修改其他所有元素需要909ms.我确认结果列表的大小确实是285557,如预期的那样,并包含我需要的更新信息.
为什么这么快？我查看了JDK6中ArrayList的源代码,它似乎正在按预期使用arraycopy函数.我很想理解为什么ArrayList在这里工作得很好,当常识似乎表明这个任务的数组是一个可怕的想法,需要移动几十万个项目.