为什么Java ArrayLists不会自动缩小
很久以前,我观看了普林斯顿Coursera MOOC:算法简介的视频讲座,可以找到
here.它解释了在添加或删除元素时调整类似ArrayList结构的成本.事实证明,如果我们想要为我们的数据结构提供调整大小,我们将从O(n)转到摊销的O(n)以进行添加和删除操作.
我已经使用Java ArrayList几年了.我一直都很确定它们会自动增长和缩小.就在最近,令我惊讶的是,我在this post年被证明是错误的.Java ArrayLists不会自动缩小(当然,它们会增长). 这是我的问题: >在我看来,在ArrayLists中提供收缩不会造成任何损害,因为性能已经摊销了O(n).为什么Java创建者没有将此功能包含在设计中? 解决方法
评论已经涵盖了您要求的大部分内容.这里有一些关于你问题的想法:
>在Java中创建类似ArrayList的结构时,开发人员会对运行时/性能做出某些决定.他们显然决定将“正常”操作中的收缩排除在外,以避免需要额外的运行时间.>问题是为什么你想要自动收缩. ArrayList不会增长那么多(因为大约是1.5; newCapacity = oldCapacity(oldCapacity>> 1),确切地说).也许你也插入中间而不只是追加到最后.然后,LinkedList(不基于数组 – >不需要收缩)可能会更好.这真的取决于你的用例.如果你认为你确实需要ArrayList所做的一切,但是在删除元素时它必须缩小(我怀疑你真的需要这个),只需扩展ArrayList并覆盖这些方法.不过要小心!如果每次移除都缩小,则返回O(n).> C#List和C向量在删除元素时缩小列表的行为相同.但自动增长的因素各不相同.甚至一些Java实现也使用不同的因素. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- Tomcat环境的建立
- Clojure的STM模型可以在多个JVM上运行吗?
- java – Hibernate中的transaction.commit()是什么?
- java – 使用System.out.print vs println的多线程问题
- java – 当jar文件从URL打开为InputStream时,JarEntry.getS
- java – 了解Hibernate的hibernate.max_fetch_depth和hiber
- java – JPA实体扩展类包含@Id
- 在java中解析装甲ECC公钥/私钥(由gpg cli生成)
- java – 有什么方法可以看到原始类型的HashCode吗?
- java – 是否可以覆盖-XX HeapDumpOnOutOfMemoryError生成