有效的Java项目17：如何覆盖removeRange（）提高性能？

在Joshua Bloch的Effective Java一书中，讨论了一个类如何将“明智选择的受保护方法”提供为内部工作的钩子。
笔者则引用文档中AbstractList.removeRange()：有效的Java项目17：如何覆盖removeRange（）提高性能？

这种方法是通过此列表及其子列表上clear操作调用。重写此方法以利用的内部优势，列表实现可以显着提高此列表及其子列表上 ,clear操作的性能。

我的问题是，如何覆盖此方法提高性能（不仅仅是不覆盖它）？任何人都可以举个例子吗？

来源

2013-03-12 Atif

我们来举一个具体的例子 - 假设你的实现是由一个动态数组支持的（例如，这是ArrayList的工作方式）。现在，假设您想要移除范围[start，end）中的元素。 removeRange的默认实现通过获取迭代器来定位start，然后调用remove()适当的次数。

每次调用remove()时，动态数组实现必须对位置start + 1上的所有元素进行洗牌，然后向前返回一个点以填充已移除元素中留下的间隙。这可能需要O（n）的时间，因为可能需要对所有数组元素进行混洗。这意味着如果您从列表中删除总共k个元素，则由于您正在执行O（n）个工作k次，所以天真方法需要花费时间O（kn）。

现在考虑一个更好的方法：复制在end位置的元素定位start，那么，元件end + 1定位start + 1，等等，直到所有的元素都被复制。这要求你只做O（n）的工作，因为每个元素最多移动一次。与朴素算法给出的O（kn）方法相比，这是一个巨大的性能改进。因此，重写removeRange以使用此更高效的算法可以显着提高性能。

希望这会有所帮助！

来源

2013-03-12 02:57:42 templatetypedef

所以说，如果你的实现比默认的实现更好，你有机会提高性能。谢谢！ – Atif 2013-03-12 03:50:13

不一定“比”好，但“不同于”。 – user949300 2013-03-12 03:56:06

正如方法的Javadoc规定：

此实现变得定位的fromIndex之前的列表迭代和重复调用ListIterator.next其次ListIterator.remove直到整个范围内已被删除。

由于这个抽象类不知道它的子类的内部，所以它依赖于这个通用算法，它的运行时间与被删除的项目数量成正比。

例如，如果您实现了将元素存储为链接列表的子类。然后你可以利用这个事实并且重写这个方法来使用一个链接列表特定的算法（移动指针fromIndex指向toIndex），该算法在恒定时间内运行。您因此利用内部优势提高了性能。

来源

2013-03-12 03:00:37

只需重写此方法，就可以根据您的要求将这种通用算法用作索引问题。由于它是AbstractList中的受保护方法，并且在ArrayList及其实现中，它可以作为remove（）的迭代调用，每次需要移除被一个索引移除元素右侧的所有元素时。显然它不是有效的，所以你可以让它工作得更好。

来源

2013-03-12 05:49:50

有效的Java项目17：如何覆盖removeRange（）提高性能？

回答

相关问题