Ati*_*tif 12 java overriding list effective-java data-structures
在Joshua Bloch撰写的Effective Java一书中,讨论了一个类如何提供"明智选择的受保护方法"作为其内部工作的钩子.
然后,作者引用了以下文档AbstractList.removeRange():
此方法
clear由此列表及其子列表上的操作调用.重写此方法以利用列表实现的内部可以显着提高clear此列表及其子列表上的操作的性能.
我的问题是,如何覆盖这种方法可以提高性能(而不仅仅是覆盖它)？谁能举个例子？
tem*_*def 20
让我们举一个具体的例子 - 假设您的实现由动态数组支持(ArrayList例如,这是有效的).现在,假设您要删除[start,end]范围内的元素.默认的实现方法removeRange是通过获取迭代器来定位start,然后调用remove()适当的次数.
每次remove()调用时,动态数组实现都必须将位置上的所有元素混洗start + 1并向前移回一个点以填充移除元素中留下的间隙.这可能需要花费时间O(n),因为可能所有的数组元素都需要被拖垮.这意味着如果你k从列表中删除了总共元素,那么天真的方法需要花费时间O(kn),因为你正在做O(n)次k次.
现在考虑一个更好的方法:将元素复制end到位置start,然后复制元素end + 1到位置start + 1等,直到复制所有元素.这要求您只执行O(n)工作,因为每个元素最多移动一次.与朴素算法给出的O(kn)方法相比,这是一个巨大的性能提升.因此,重写removeRange使用这种更高效的算法可以显着提高性能.
希望这可以帮助!
Edw*_*son 11
正如方法的javadocs中所指定的:
此实现获取一个位于fromIndex之前的列表迭代器,并重复调用ListIterator.next,然后调用ListIterator.remove,直到删除整个范围.
由于此抽象类不了解其子类的内部,因此它依赖于此通用算法,该算法将在时间上与要删除的项目数成比例.
例如,如果您实现了将元素存储为链接列表的子类.然后,你可以利用这个事实,并重写此方法使用链表特定的算法(移动指针fromIndex指向toIndex),这在固定时间内运行.因此,您可以利用内部优势提高性能.