java - 有效的 Java 项目 17 : How can overriding removeRange() improve performance?

Question

在 Joshua Bloch 的 Effective Java 一书中，讨论了类如何提供“明智选择的 protected 方法”作为其内部工作的 Hook 。
然后作者引用了 AbstractList.removeRange() 中的文档:

This method is called by the clear operation on this list and its subLists. Overriding this method to take advantage of the internals of the list implementation can substantially improve the performance of the clear operation on this list and its subLists.

我的问题是，覆盖此方法如何提高性能(不仅仅是不覆盖它)？谁能举个例子？

Answer 1

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

每次 remove() 被调用时，动态数组实现必须打乱 start + 1 位置的所有元素，并向前移动一个位置以填补左边的空白在删除的元素中。这可能会花费 O(n) 的时间，因为可能所有的数组元素都需要打乱顺序。这意味着如果您要从列表中删除总共 k 元素，那么天真的方法将花费时间 O(kn)，因为您要执行 O(n) 次工作。

现在考虑一个更好的方法:将 end 位置的元素复制到 start 位置，然后将 end + 1 元素复制到 位置>start + 1 等，直到复制完所有元素。这要求你总共只做 O(n) 的工作，因为每个元素最多移动一次。与朴素算法给出的 O(kn) 方法相比，这是一个巨大的性能提升。因此，覆盖 removeRange 以使用这种更高效的算法可以显着提高性能。

希望这对您有所帮助!