在 Joshua Bloch 的《Effective Java》一书中，讨论了一个类如何提供“明智选择的受保护方法”作为其内部工作的挂钩。
然后作者引用了以下文档AbstractList.removeRange()：
此方法由
clear对该列表及其子列表的操作调用。重写此方法以利用列表实现的内部结构可以显着提高clear对该列表及其子列表的操作性能。
我的问题是，重写此方法如何提高性能（不仅仅是不重写它）？谁能举个例子？
问问题
1343 次
3 回答
20
让我们举一个具体的例子 - 假设您的实现由动态数组支持（ArrayList例如，这是如何工作的）。现在，假设您要删除范围 [start, end) 中的元素。默认实现removeRange通过获取一个迭代器到 position start，然后调用remove()适当的次数来工作。
每次remove()调用时，动态数组实现都必须打乱位置处的所有元素，start + 1并向后移动一个点，以填补移除元素中留下的空白。这可能需要时间 O(n)，因为可能所有数组元素都可能需要重新排序。这意味着，如果您k要从列表中删除全部元素，那么天真的方法将花费时间 O(kn)，因为您正在做 O(n) 次工作 k 次。
现在考虑一种更好的方法：将位置的元素复制end到位置start，然后将元素复制end + 1到位置start + 1，等等，直到所有元素都被复制。这要求您总共只做 O(n) 的工作，因为每个元素最多移动一次。与朴素算法给出的 O(kn) 方法相比，这是一个巨大的性能提升。因此，重写removeRange以使用这种更有效的算法可以显着提高性能。
希望这可以帮助！
于 2013-03-12T02:57:42.973 回答
11
如方法的 javadocs 中所述：
此实现获取一个位于 fromIndex 之前的列表迭代器，并重复调用 ListIterator.next 后跟 ListIterator.remove，直到整个范围都被删除。
由于这个抽象类不知道其子类的内部结构，因此它依赖于这种通用算法，该算法的运行时间与被删除的项目数量成正比。
例如，如果您实现了一个将元素存储为链表的子类。然后您可以利用这一事实并覆盖此方法以使用在恒定时间内运行的特定于链表的算法（将指针移动fromIndex到指向）。toIndex您因此提高了性能，因为您利用了内部结构。
于 2013-03-12T03:00:37.157 回答
0
只需覆盖此方法，您就可以根据您的要求使用此通用算法作为索引问题。因为它是 AbstractList 以及 ArrayList 及其实现中的受保护方法，所以它作为对 remove() 的迭代调用，需要每次将已删除元素右侧的所有可用元素移动一个索引。显然它没有效果，所以你可以让它更好地工作。
于 2013-03-12T05:49:50.143 回答